Difference between pages "4.53" and "9.19"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
(Created page with " Back to Chapter 9")
 
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


Back to Chapter 9