Skip to main content

Data Structures · Arrays, linked structures, stacks, queues, and amortization

A duplicate minimum must sit on the min-stack, or one pop forgets the other

Problem

Data Structures practice problem

A min-stack is a pair of stacks (S,M)(S,M). Stacks are written as sequences with the rightmost entry on top. Both start empty. The operations arePUSH(x):{push x on M if M is empty or x≤top(M),then push x on S,POP():{if top(S)=top(M), pop M,then pop S,MIN():return top(M).\begin{align*} \mathrm{PUSH}(x)&: \begin{cases} \text{push $x$ on $M$ if $M$ is empty or $x\le\mathrm{top}(M)$},\\ \text{then push $x$ on $S$}, \end{cases}\\ \mathrm{POP}()&: \begin{cases} \text{if $\mathrm{top}(S)=\mathrm{top}(M)$, pop $M$},\\ \text{then pop $S$}, \end{cases}\\ \mathrm{MIN}()&:\text{return }\mathrm{top}(M). \end{align*}POP\mathrm{POP} and MIN\mathrm{MIN} are defined only when SS is nonempty.

1. Prove that after every legal operation MM is empty if and only if SS is empty, and that if SS is nonempty then top(M)=min⁡S\mathrm{top}(M)=\min S. In particular, identify MM as the subsequence of bottom-to-top entries of SS that are weakly left-to-right minima.

2. Execute PUSH(5)\mathrm{PUSH}(5), PUSH(2)\mathrm{PUSH}(2), PUSH(2)\mathrm{PUSH}(2), PUSH(4)\mathrm{PUSH}(4). Record SS, MM, and MIN\mathrm{MIN} after each push. Then execute POP\mathrm{POP} three times. Prove that after the first 22 is popped one still has MIN=2\mathrm{MIN}=2, and that after the second 22 is popped one has MIN=5\mathrm{MIN}=5.

3. Repeat the same seven operations with the comparison in PUSH\mathrm{PUSH} changed from x≤top(M)x\le\mathrm{top}(M) to x<top(M)x<\mathrm{top}(M). Show exactly where the invariant top(M)=min⁡S\mathrm{top}(M)=\min S first fails, and compute the false MIN\mathrm{MIN} after the first 22-pop.

4. Audit a one-field implementation that stores only a running minimum mm and, on every pop, either leaves mm unchanged or has no recorded predecessor with which to restore 55. Explain why the companion stack is not a search tree and not a heap.

Do not replace the structure by a balanced tree or by a dynamic table, and do not treat duplicate keys as a single occupancy.

Hint

Hint

The second 22 satisfies 2≤22\le 2, so it must be pushed onto MM. The later 44 does not.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.

More Data Structures practice problems

Back to Data Structures

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.