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 problemA min-stack is a pair of stacks . Stacks are written as sequences with the rightmost entry on top. Both start empty. The operations are and are defined only when is nonempty.
1. Prove that after every legal operation is empty if and only if is empty, and that if is nonempty then . In particular, identify as the subsequence of bottom-to-top entries of that are weakly left-to-right minima.
2. Execute , , , . Record , , and after each push. Then execute three times. Prove that after the first is popped one still has , and that after the second is popped one has .
3. Repeat the same seven operations with the comparison in changed from to . Show exactly where the invariant first fails, and compute the false after the first -pop.
4. Audit a one-field implementation that stores only a running minimum and, on every pop, either leaves unchanged or has no recorded predecessor with which to restore . 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
HintThe second satisfies , so it must be pushed onto . The later 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
- Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…Abstract data types, representation, and invariants
- A ring buffer (circular array) of fixed capacity C ≥ 1 stores a sequence of at most C…Abstract data types, representation, and invariants
- Let L be the doubly linked list with values [10, 20, 30, 40, 50], and let I be a…Arrays, linked structures, stacks, queues, and amortization
- Consider BST deletion of a node zSearch trees and balanced trees
- Let T be a BST whose nodes contain only key, left, and right fields (no parent…Search trees and balanced trees
- Consider a hash table T of size m = 11 that resolves collisions by chainingHash tables and probabilistic performance
- Throw n balls independently and uniformly into n binsHash tables and probabilistic performance
- `Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…Heaps, priority queues, and disjoint sets
- The fat-node method of partial persistence stores, in each field of each node, a…Graph representations and traversals