Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 225 ยท Stacks and Queues

Stack Puzzles: Permutations, Recursive Sort and Reverse, k Stacks in One Array

Solve classic stack puzzles in Python: check stack permutations, sort and reverse a stack with recursion only, and share one array between k stacks efficiently.

Stacks look simple (push, pop, peek), and that is exactly why teachers and interviewers like to put constraints on them: "no loops", "no extra container", "only one array". Under those rules you have to think about what the stack really guarantees, which is last in, first out and nothing else.

This lesson covers four puzzles. First, stack permutations: which output orders can a stack produce from an input sequence? Then two recursion-only tricks, sorting a stack and reversing a stack, where the call stack itself becomes your temporary storage. Finally, k stacks in one array, a memory-sharing design that wastes no space. You should know the basics from Stacks and the patterns in Stack Applications, and be comfortable with recursion.

Stack permutations

Feed the numbers 1, 2, 3, ... into a stack in order. You may push the next input or pop the top to the output at any time. Which output sequences are possible? With input 1 2 3, the output 3 1 2 is impossible: to emit 3 first you must push 1, 2 and 3, but then 2 sits on top of 1, so 2 leaves before 1.

To test a target sequence, simulate it greedily. For each target value, push input numbers until the target is on top, then pop it; if the top is not the target, the sequence is impossible.

Python Can this output order be produced?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Count the valid outputs for each n and you get 1, 2, 5, 14, 42, 132, 429: the Catalan numbers (see Lucas, Stirling and Catalan). That is no coincidence; the push/pop sequences are exactly balanced bracket sequences.

A quick rule for the impossible ones: an output is achievable exactly when it never contains the pattern 3 1 2 as a subsequence, that is, a large value, later a small value, and later still a medium value.

Reverse a stack with recursion only

The stack-reversal puzzle: reverse a stack without loops and without any container besides the stack itself. The recursion stack is the free storage.

The solution needs two recursive helpers:

  • insert_at_bottom(stack, x): pop everything off by recursion, push x, then push everything back.
  • reverse(stack): pop the top element, reverse the rest, then insert_at_bottom the element you held.
Python Reverse a stack using recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cost: insert_at_bottom is O(n), and it is called n times, so the whole reversal is O(n^2) time and O(n) recursion depth. Python's default recursion limit is around 1000, so this is a teaching tool for small stacks.

Sort a stack with recursion only

The same pattern sorts a stack. Pop the top, sort the rest recursively, then insert the element into its correct place in the now-sorted stack. Insertion pops items that are bigger than the element, places it, and pushes the popped items back.

Python Sort a stack using recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions are O(n^2) in the worst case. The recursion-only one simply uses the call stack as the second stack.

k stacks in one array

Suppose you have one array of size n and need k stacks. The naive plan, giving each stack n / k slots, wastes memory when one stack is full and the others are empty. A better design lets the stacks share all free slots using three arrays:

  • data[i]: the value stored in slot i.
  • nxt[i]: for a used slot, the slot below it in its stack (or -1); for a free slot, the next free slot.
  • top[s]: the slot index of stack s's top (or -1 when empty).
  • free: head of the free list.

Pushing takes the first free slot and links it above the old top. Popping returns the slot to the free list. Every operation is O(1), and a push only fails when all n slots are used.

Python k stacks sharing one array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A second, simpler variant stores the stacks interleaved: stack s lives at positions s, s + k, s + 2k, .... That is fast to write but wastes space when the stacks are uneven.

Two stacks in one array is the easy special case: start one stack at index 0 and growing up, and the other at the last index growing down. They only collide when the array is truly full.

Common mistakes

  • Testing a permutation by brute force over every push/pop plan. The greedy simulation above is O(n).
  • Forgetting the base case of the recursive helpers, which gives infinite recursion.
  • Recursing deeply on big inputs. Python limits the recursion depth; use loops and a second stack for large data.
  • In KStacks, forgetting to return a popped slot to the free list, which leaks capacity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With input 1, 2, 3 pushed in order, which output order can a stack NOT produce?

    To output 3 first you must push 1, 2 and 3; then 2 is above 1 and must leave first, so 3 1 2 is impossible.
  2. 2. How many different output orders can a stack produce from n distinct inputs pushed in order?

    Push/pop sequences correspond to balanced bracket sequences, which are counted by the Catalan numbers (1, 2, 5, 14, 42 ...).
  3. 3. What is the time complexity of reversing a stack with the two recursive helpers?

    insert_at_bottom costs O(n) and is called once per element.
  4. 4. Why does the free-list design for k stacks in one array beat giving each stack n/k slots?

    Fixed partitions overflow as soon as one stack exceeds n/k, even if other stacks are empty. The shared free list uses every slot.

Summary

  • Stack-permutation tests are greedy: push until the target is on top, then pop; the counts follow the Catalan numbers.
  • Reverse and sort a stack with recursion by popping, recursing, then inserting (at the bottom or in order); each is O(n^2).
  • The call stack acts as the temporary storage when you may not use another container.
  • k stacks in one array use data, nxt, top and a free list for O(1) push/pop with no wasted space.

Next: Queue Puzzles, the same kind of constraints applied to queues.