Given an empty stack, after performing push(1), push(2), pop, push(3),…
2012
Given an empty stack, after performing push(1), push(2), pop, push(3), push(4), pop, pop, push(5), pop, what is the value at the top of the stack?
Answer: D. 1 — Concept — a stack is last-in, first-out. In a stack, push(x) places x above every element the stack currently holds, and pop removes and returns the element…
- A.
4
- B.
3
- C.
2
- D.
1
Attempted by 187 students.
Show answer & explanation
Correct answer: D
Concept — a stack is last-in, first-out. In a stack, push(x) places x above every element the stack currently holds, and pop removes and returns the element that was pushed most recently among those still present. Consequently, after any sequence of operations the top of the stack is the most recently pushed element that has not yet been popped, and the order in which elements leave is the reverse of the order in which they entered.
Application — trace the nine operations in order. Each row shows the stack written from bottom to top after the operation has been carried out, and the value that the operation returned.
Operation | Stack (bottom to top) | Value removed |
|---|---|---|
push(1) | 1 | — |
push(2) | 1, 2 | — |
pop | 1 | 2 |
push(3) | 1, 3 | — |
push(4) | 1, 3, 4 | — |
pop | 1, 3 | 4 |
pop | 1 | 3 |
push(5) | 1, 5 | — |
pop | 1 | 5 |
Cross-check — count pushes against pops. The sequence contains five pushes and four pops, so exactly one element must survive. Because every pop takes the most recently pushed element still present, the elements leave in the order 2, 4, 3, 5. The element pushed first is never the most recent one while any later element is still in the stack, so no pop in this sequence ever reaches it, and it remains after the final pop.
The value at the top of the stack is 1.