{"id":200,"date":"2019-01-31T15:51:52","date_gmt":"2019-01-31T20:51:52","guid":{"rendered":"https:\/\/resrvoir.com\/?page_id=200"},"modified":"2019-03-17T13:49:13","modified_gmt":"2019-03-17T17:49:13","slug":"stacks-as-queue","status":"publish","type":"page","link":"https:\/\/resrvoir.com\/?page_id=200","title":{"rendered":"Stacks as Queue"},"content":{"rendered":"\n<p>Implement a queue using stacks.<br><br>This uses two stacks to represent a queue, one for the enqueueing operation and another for the dequeuing operation.<br><br>All elements are transferred from one stack to another any time the queue operation switches. In other words, if the current operation is enqueue and the previous operation was dequeue, then all elements must first be transferred to the enqueue stack before the current element can be added. Likewise, if the current operation is dequeue and the previous operation was enqueue, then all elements must first be transferred to the dequeue stack before removing the current element.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"kotlin\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Queue&lt;T> {\n  var nqStack = Stack&lt;T>()\n  var dqStack = Stack&lt;T>()\n\n  func enqueue&lt;T>(item: T) {\n    while (let i = dqStack.pop()) {\n      nqStack.push(item: i)\n    }\n    nqStack.push(item: item)\n  }\n\n  func dequeue&lt;T>() -> T? {\n    while (let i = nqStack.pop()) {\n      dqStack.push(item: i)\n    }\n    return dqStack.pop()\n  }\n}<\/pre>\n\n\n\n<p>The runtime is most efficient when either:<br><\/p>\n\n\n\n<ul><li>all elements are enqueued first, then all elements are dequeued<\/li><li>each element is enqueued and dequeued before another element is introduced<\/li><\/ul>\n\n\n\n<p>In both cases, each element is<\/p>\n\n\n\n<ul><li>enqueued, requiring 1 push<\/li><li>transferred, requiring 1 pop and 1 push<\/li><li>dequeued, requiring 1 pop<\/li><\/ul>\n\n\n\n<p>This data structure takes 4n = O(n) push\/pop operations, for a collection of n elements.<br><br>The runtime is very inefficient when n\/2 elements are enqueued first, then operations alternate between dequeue and enqueue for the remaining n\/2 elements. In terms of pushing\/popping operations, it has:<br><br>enqueues = n \/ 2 pushes<br>dequeue followed by enqueue = <br>n \/ 2 ((n \/ 2 pops + n \/ 2 pushes + 1 pop) + ((n &#8211; 1) \/ 2 pops + (n &#8211; 1) \/ 2 pushes + 1 pushes))<br>dequeues = n \/ 2 pops<br><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"matlab\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"false\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">= n\/2 + n\/2((n\/2 + n\/2 + 1) + (n - 1)\/2 + (n - 1)\/2 + 1) + n\/2\n= 2n\/2 + n\/2(2n\/2 + 1) + 2(n - 1)\/2 + 1)\n= n + n\/2((n + 1) + (n - 1) + 1)\n= n + n\/2(2n + 1)\n= n + (2n^2 + n)\/2\n= n + n^2 + n\/2\n= n^2 + 3n\/2\n= O(n^2)<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Implement a queue using stacks. This uses two stacks to represent a queue, one for the enqueueing operation and another for the dequeuing operation. All elements are transferred from one stack to another any time the queue operation switches. In other words, if the current operation is enqueue and the previous operation was dequeue, then [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2,"menu_order":11,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/200"}],"collection":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=200"}],"version-history":[{"count":50,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/200\/revisions"}],"predecessor-version":[{"id":799,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/200\/revisions\/799"}],"up":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/2"}],"wp:attachment":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}