Data Structures and Algorithms
On an empty stack, the operations push 1, push 2, pop, push 3, push 4, pop, pop are performed in this order. In what order are the values removed by pop?
- A1, 2, 3
- B2, 3, 4
- C2, 4, 3
Show answer and explanation
Answer: C. 2, 4, 3
A stack is a last-in, first-out (LIFO) structure: the item added last is removed first. After push 1 and push 2, pop removes the top value 2, leaving 1. Pushing 3 and 4 then gives 4, 3, 1 from the top, so the next two pops remove 4 and then 3. The values therefore come out as 2, 4, 3, and 1 remains on the stack. 1, 2, 3 is the order you would get from a queue (first-in, first-out, FIFO), which removes the earliest item first.
- A. This is the order for a queue (FIFO), which removes items in the order they were added.
- B. 4 and 3 are reversed. The 4, pushed later, comes out first.
- C. Correct. The item added last comes out first, giving 2, 4, 3.