AlgoVerse

Two stacks in one array

Two stacks grow toward each other from the two ends of one array; neither is full until the whole array is.

Giving each stack its own fixed-size array lets one fill up while the other sits empty. Putting two stacks in one array, growing toward each other from the two ends, means neither is full until the whole array is.

Read the full explanation ↓
Input:
ops 7×2PDF export

Each row is [stack, value], and a value of 0 means POP. The stacks grow from the two ends, then each pops one item.

  1. def two_stacks(ops):
  2. # ops: rows [stack (1 or 2), value]; a value of 0 pops. Stack 1 grows from the left, stack 2 from the right.
  3. n = 8
  4. arr = ["·"] * n
  5. cells = [arr] # for the picture: the shared array as one table row
  6. top1, top2 = -1, n
  7. popped = []
  8. for which, value in ops:
  9. if value != 0:
  10. if top1 + 1 == top2:
  11. continue
  12. if which == 1:
  13. top1 = top1 + 1
  14. arr[top1] = value
  15. else:
  16. top2 = top2 - 1
  17. arr[top2] = value
  18. elif which == 1:
  19. if top1 == -1:
  20. continue
  21. popped.append(arr[top1])
  22. arr[top1] = "·"
  23. top1 = top1 - 1
  24. else:
  25. if top2 == n:
  26. continue
  27. popped.append(arr[top2])
  28. arr[top2] = "·"
  29. top2 = top2 + 1
  30. return popped

Invariant: Cells 0 to top1 hold stack 1 and cells top2 to n−1 stack 2; always top1 < top2.

Start

top1—
top2—
popped—

The table is still empty.

Local variables

Orange = changed in this step

ops list

[1, 10][1, 20][2, 70][2, 80][1, 30][2, 0][1, 0]

Call stack

  1. two_stacks()line 1
Step 1 of 52
Black = push, pop · Orange = key steppush: 0/5 · pop: 0/2
    Explanation

    The idea

    Giving each stack its own fixed-size array lets one fill up while the other sits empty. Putting two stacks in one array, growing toward each other from the two ends, means neither is full until the whole array is.

    • Stack 1: top1 starts at −1 and grows by one with each PUSH.
    • Stack 2: top2 starts at n and shrinks by one with each PUSH.
    • The array is full when top1 + 1 = top2.

    More than two stacks

    For m stacks (as in Horowitz–Sahni) the array is first split into m equal parts; when a stack reaches the next part's boundary, the neighbouring stacks are shifted to bring it free space. With two stacks no shifting is ever needed.

    The input

    Each row is [stack, value], and a value of 0 means POP. The array has 8 cells.