DSA Factory
Free lessonsStacks and queues · Stage 0 · Last in, first out · Step 1

An undo button

The newest item comes off first. About 8 minutes.

A stack: last in, first out

Think of a pile of plates. You put a plate on top, and you take a plate from the top. The last plate you put down is the first one you pick up. An undo button works the same way: it takes back your newest change first.

Push: puts an item on top.
Pop: takes the top item off. Both happen at the same end.
Actions [3, 8, 0, 6, 2, 0], where 0 means undo
3
0
8
1
0
2
6
3
2
4
0
5
i

3: push it. Stack: [3].

Move 1 of 6

The stack in each language

In Python and JavaScript, a plain list is a stack: append (push in JS) adds at the end, and pop removes from the end. Both take about one step. C++ has stack<int> with push, pop and top. In Java, use ArrayDeque with push, pop and peek. Popping an empty stack is an error, so check first.

Python list · JS array: append / push and pop, at the end.
C++ stack · Java ArrayDeque: push, pop, and top / peek.
Check before you pop: an empty stack has nothing to take.
Quick check

What's left after these actions?

actions = [5, 9, 1, 0, 0]
  1. A[5]
  2. B[1]
  3. C[5, 9]
Show the answer

[5]. The first undo takes 1, the newest. The second takes 9. Only 5 is left.

Your problem

Undo button

A tiny editor gets a list of actions. A positive number means "add this number to the end of the document". A 0 means "undo": remove the most recently added number that's still in the document. If the document is empty, a 0 does nothing. Return the numbers left in the document, oldest first.

Example
actions = [3, 8, 0, 6, 2, 0] → [3, 6]

0 ≤ n ≤ 100,000 · 0 ≤ each value ≤ 1,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding