https://algorist.com/algowiki_v2/index.php?action=history&feed=atom&title=TADM2E_4.44 2026-05-01T02:53:59Z Revision history for this page on the wiki MediaWiki 1.28.0 https://algorist.com/algowiki_v2/index.php?title=TADM2E_4.44&diff=102&oldid=prev 2014-09-11T18:14:16Z

<p>Recovering wiki</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 poped 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) push'es to the data structure, and then n extract-min's)<br /> --[[User:Kubek2k|Kubek2k]] 05:00, 6 November 2011 (EST)</div>

Algowikiadmin