https://algorist.com//algowiki/index.php?title=4.51&feed=atom&action=history4.51 - Revision history2024-03-28T11:03:02ZRevision history for this page on the wikiMediaWiki 1.34.2https://algorist.com//algowiki/index.php?title=4.51&diff=332&oldid=prevAlgowikiadmin: Created page with "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..."2020-09-20T18:36:56Z<p>Created page with "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..."</p>
<p><b>New page</b></p><div>If we are allowed to maintain a second stack on the side, this should be possible.<br />
The main stack is a regular stack that can be implemented using an array and an index to the top of the stack.<br />
The second stack will stack each entry when it becomes the new minimum, only.<br />
When an entry is popped from the main stack, it will be poped from the second stack only if identical.<br />
The minimum item is the top of the second stack.<br />
<br />
<br />
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)<br />
--[[User:Kubek2k|Kubek2k]] 05:00, 6 November 2011 (EST)<br />
<br />
<br />
Back to [[Chapter 4]]</div>Algowikiadmin