{"id":4302,"date":"2021-11-26T11:12:38","date_gmt":"2021-11-26T05:42:38","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4302"},"modified":"2021-11-26T11:13:09","modified_gmt":"2021-11-26T05:43:09","slug":"implement-queue-using-stack","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/implement-queue-using-stack\/","title":{"rendered":"Implement Queue Using Stack"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-making-enqueue-operation-costly\">Approach 1: Making enqueue operation costly<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-making-dequeue-operation-costly\">Approach 2: Making dequeue operation costly<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>The task here is to implement a First In First Out queue using Stacks. The queue should support all functions such as push, pop, peek.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input<\/strong><br>[&#8220;MyQueue&#8221;, &#8220;push&#8221;, &#8220;push&#8221;, &#8220;peek&#8221;, &#8220;pop&#8221;, &#8220;empty&#8221;]<br>[[], [1], [2], [], [], []]\n\n\n\n<p><strong>Output<\/strong><br>[null, null, null, 1, 1, false]\n\n\n\n<p><strong>Explanation<\/strong><\/p>\n\n\n\n<p>MyQueue myQueue = new MyQueue();<br>myQueue.push(1); \/\/ queue is: [1]<br>myQueue.push(2); \/\/ queue is: [1, 2] (leftmost is front of the queue)<br>myQueue.peek(); \/\/ return 1<br>myQueue.pop(); \/\/ return 1, queue is [2]<br>myQueue.empty(); \/\/ return false<strong>\u00a0<\/strong><\/p>\n\n\n\n<p>Before diving into the solution, let us first understand the basic difference between <strong>Stack <\/strong>and <strong>Queue.<\/strong><\/p>\n\n\n\n<p><strong>Stack <\/strong>is Last in First Out data structure. Push and pop operations take place only through one end of the stack i.e. <strong>top(). <\/strong>It supports push, pop, peek operations.<\/p>\n\n\n\n<p><strong>Queue <\/strong>is First In First Out data structure. Push and pop operations take place through two ends of the queue. It supports enqueue, dequeue, peek operations.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"640\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4471 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-1024x640.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-1024x640.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-768x480.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-1536x960.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-550x344.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-800x500.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example-1160x725.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Example.png 1600w\" ><\/figure>\n\n\n\n<p>So, if you clearly observe, we would require <strong>two stacks<\/strong> to implement the queue, one for en queue and another for de queue operation.<\/p>\n\n\n\n<h2 id=\"approach-1-making-enqueue-operation-costly\">Approach 1: Making enqueue operation costly<\/h2>\n\n\n\n<p id=\"as-discussed-above-we-know-in-the-queue-it-follows-a-fifo-order-ie-the-element-which-gets-in-first-gets-out-first-therefore-we-need-to-devise-a-technique-using-stacks-such-that-the-element-which-will-be-pushed-will-remain-at-the-top-therefore-we-will-use-a-second-stack-for-the-same-----algorithm-\">As discussed above, we know, in the queue, it follows a FIFO order, i.e., the element which gets in first, gets out first. Therefore, we need to devise a technique using stacks, such that the element which will be pushed will remain at the top.<br>Therefore, we will use a second stack for the same.<strong><br><\/strong><br><strong>Algorithm<\/strong><\/p>\n\n\n\n<p><strong>For enqueue<\/strong><\/p>\n\n\n\n<ul><li>Initialise two stacks <strong>S1<\/strong> and <strong>S2<\/strong>.<\/li><li>If <strong>S1<\/strong> is empty, insert the element into <strong>S2<\/strong>.<\/li><li>Else, push all the elements from <strong>S1<\/strong> to <strong>S2<\/strong>.<\/li><li>Push the element that needs to be inserted into <strong>S1<\/strong>.<\/li><li>Push all the elements from <strong>S2<\/strong> back to<strong> S1<\/strong>.<\/li><\/ul>\n\n\n\n<p><strong>For dequeue<\/strong><\/p>\n\n\n\n<ul><li>If the stack <strong>S1<\/strong> is empty, return <strong>-1<\/strong>.<\/li><li>Else, return the top element of the stack.\u00a0<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Queue {\n  stack &amp;lt; int > s1, s2;\n \n  void enQueue(int x) {\n    while (!s1.empty()) {\n      s2.push(s1.top());\n      s1.pop();\n    }\n    s1.push(x);\n    while (!s2.empty()) {\n      s1.push(s2.top());\n      s2.pop();\n    }\n  }\n  int deQueue() {\n    if (s1.empty()) {\n      cout &amp;lt;&amp;lt; \"Q is Empty\";\n      exit(0);\n    }\n    int x = s1.top();\n    s1.pop();\n    return x;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static class Queue {\n  static Stack &amp;lt; Integer > s1 = new Stack &amp;lt; Integer > ();\n  static Stack &amp;lt; Integer > s2 = new Stack &amp;lt; Integer > ();\n \n  static void enQueue(int x) {\n    while (!s1.isEmpty()) {\n      s2.push(s1.pop());\n    }\n    s1.push(x);\n    while (!s2.isEmpty()) {\n      s1.push(s2.pop());\n    }\n  }\n  static int deQueue() {\n    if (s1.isEmpty()) {\n      System.out.println(\"Q is Empty\");\n      System.exit(0);\n    }\n    int x = s1.peek();\n    s1.pop();\n    return x;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Queue:\n    def __init__(self):\n        self.s1 = []\n        self.s2 = []\n \n    def enQueue(self, x):\n \n        while len(self.s1) != 0:\n            self.s2.append(self.s1[-1])\n            self.s1.pop()\n \n        self.s1.append(x)\n \n        while len(self.s2) != 0:\n            self.s1.append(self.s2[-1])\n            self.s2.pop()\n \n    def deQueue(self):\n \n        if len(self.s1) == 0:\n            print(\"Q is Empty\")\n \n        x = self.s1[-1]\n        self.s1.pop()\n        return x<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) for enqueue operation, O(1) for pop\u00a0<br><strong>Space Complexity:<\/strong> O(N)<\/p>\n\n\n\n<h2 id=\"approach-2-making-dequeue-operation-costly\">Approach 2: Making dequeue operation costly<\/h2>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<p><strong>For enqueue<\/strong><\/p>\n\n\n\n<ul><li>Initialise two stacks <strong>S1<\/strong> and <strong>S2<\/strong>.<\/li><li>Push all the elements into <strong>S1<\/strong>.<\/li><\/ul>\n\n\n\n<p><strong>For dequeue<\/strong><\/p>\n\n\n\n<ul><li>If the size of <strong>S1<\/strong> and <strong>S2<\/strong> is 0, return <strong>-1<\/strong>.<\/li><li>Push all the elements to <strong>S2<\/strong> from <strong>S1<\/strong>.<\/li><li>Remove the top element of the stack <strong>S1.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">struct Queue {\n  stack &amp;lt; int > s1, s2;\n  void enQueue(int x) {\n    s1.push(x);\n  }\n  int deQueue() {\n    if (s1.empty() &amp;amp;&amp;amp; s2.empty()) {\n      cout &amp;lt;&amp;lt; \"Q is empty\";\n      exit(0);\n    }\n    if (s2.empty()) {\n      while (!s1.empty()) {\n        s2.push(s1.top());\n        s1.pop();\n      }\n    }\n    int x = s2.top();\n    s2.pop();\n    return x;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static class Queue {\n  Stack &amp;lt; Integer > stack1;\n  Stack &amp;lt; Integer > stack2;\n}\nstatic void push(Stack &amp;lt; Integer > top_ref, int new_data) {\n  top_ref.push(new_data);\n}\nstatic int pop(Stack &amp;lt; Integer > top_ref) {\n  if (top_ref.isEmpty()) {\n    System.out.println(\"Stack Underflow\");\n    System.exit(0);\n  }\n  return top_ref.pop();\n}\nstatic void enQueue(Queue q, int x) {\n  push(q.stack1, x);\n}\nstatic int deQueue(Queue q) {\n  int x;\n  if (q.stack1.isEmpty() &amp;amp;&amp;amp; q.stack2.isEmpty()) {\n    System.out.println(\"Q is empty\");\n    System.exit(0);\n  }\n  if (q.stack2.isEmpty()) {\n    while (!q.stack1.isEmpty()) {\n      x = pop(q.stack1);\n      push(q.stack2, x);\n    }\n  }\n  x = pop(q.stack2);\n  return x;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class Queue:\n    def __init__(self):\n        self.s1 = []\n        self.s2 = []\n \n    def enQueue(self, x):\n        self.s1.append(x)\n \n    def deQueue(self):\n        if len(self.s1) == 0 and len(self.s2) == 0:\n            print(\"Q is Empty\")\n            return\n \n        elif len(self.s2) == 0 and len(self.s1) > 0:\n            while len(self.s1):\n                temp = self.s1.pop()\n                self.s2.append(temp)\n            return self.s2.pop()\n \n        else:\n            return self.s2.pop()<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(1) for enqueue operation, O(N) for pop\u00a0<br><strong>Space Complexity:<\/strong> O(N)<\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. Which approach is more efficient? Making enqueue operation costly or dequeue operation costly?<br><\/strong>A. Both the problems have the same time complexity, hence, we are free to use any one of them.<\/p>\n\n\n\n<p><strong>Q. What is a queue?<\/strong><br>A. A queue is a data structure that follows the FIFO<strong>(first in first out) <\/strong>method, i.e. element which goes in first, comes out first.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement The task here is to implement a First In First Out queue using Stacks. The queue&hellip;\n","protected":false},"author":5,"featured_media":4472,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[614],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4302"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4302"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4302\/revisions"}],"predecessor-version":[{"id":4475,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4302\/revisions\/4475"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4472"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}