From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation
Jump to search
|
|
Line 1: |
Line 1: |
− | If we are allowed to maintain a second stack on the side, this should be possible.
| |
− | The main stack is a regular stack that can be implemented using an array and an index to the top of the stack.
| |
− | The second stack will stack each entry when it becomes the new minimum, only.
| |
− | When an entry is popped from the main stack, it will be poped from the second stack only if identical.
| |
− | The minimum item is the top of the second stack.
| |
| | | |
| | | |
− | I think the actual question was about ability of building the stack that has push/pop/extract-min operations as in the queues - the extract removes element. This is impossible - that would give us an opportunity to sort in O(n) time (n O(1) pushes to the data structure, and then n extract-min's)
| + | Back to [[Chapter 9]] |
− | --[[User:Kubek2k|Kubek2k]] 05:00, 6 November 2011 (EST)
| |
− | | |
− | | |
− | Back to [[Chapter 4]] | |
Latest revision as of 14:00, 21 September 2020