{"id":3903,"date":"2021-11-19T11:35:25","date_gmt":"2021-11-19T06:05:25","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3903"},"modified":"2021-11-19T11:35:26","modified_gmt":"2021-11-19T06:05:26","slug":"stack-using-2-queues","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/stack-using-2-queues\/","title":{"rendered":"Stack Using 2 Queues"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><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-push-operation-costly\">Approach 1 (Push 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-2pop-operation-costly\">Approach 2(Pop 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=\"#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>Implement a class Stack, using 2 Queues, which can perform the following operations:<\/p>\n\n\n\n<ul><li><strong>Push():<\/strong> Push a value into the stack.<\/li><li><strong>Pop():<\/strong> Pop last inserted element from the stack.<\/li><li><strong>Top():<\/strong> Display the top element of the stack.<\/li><li><strong>getSize():<\/strong> Return the current size of the stack.<\/li><\/ul>\n\n\n\n<p id=\"-sample-test-cases--\"><strong>Sample Test Cases:<\/strong><\/p>\n\n\n\n<p>Input 1:<br>push(1)<br>push(2)<br>push(3)<br>top()<br>pop()<br>top()<br>pop()<br>top()<br>pop()<\/p>\n\n\n\n<p>Output 1:<br>3<br>2<br>1<\/p>\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<p>Stack follows a <strong>last in first out<\/strong> rule, so the elements which are inserted first are popped out last from the stack.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"959\"  height=\"593\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Stack Operations\"  class=\"wp-image-4037 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 959px) 100vw, 959px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations.png 959w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations-300x186.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations-768x475.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations-380x235.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations-550x340.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Stack-Operations-800x495.png 800w\" ><\/figure>\n\n\n\n<h2 id=\"approach-1-push-operation-costly\">Approach 1 (Push Operation costly)<\/h2>\n\n\n\n<p>Using <strong>2 queues<\/strong>, we can make a stack, which can perform <strong>push<\/strong> operations in <strong>O(n)<\/strong> and all other functionalities in <strong>O(1)<\/strong> time. Let the queues be called <strong>firstQ<\/strong> and <strong>secondQ. <\/strong>We will ensure that the pop operation will only pop from the <strong>firstQ. secondQ <\/strong>is used to put every new element to the front of <strong>firstQ.<\/strong><\/p>\n\n\n\n<p>The implementation of the functions are described as follows:<\/p>\n\n\n\n<ul><li>push(val):&nbsp;<ul><li>Push <strong>val <\/strong>to <strong>secondQ.<\/strong><\/li><li>Using a while loop, pop all the contents from <strong>firstQ<\/strong> and push them into <strong>secondQ<\/strong> in order.<\/li><li>Swap the 2 Queues.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul><li>pop():&nbsp;<ul><li>Pop from the <strong>firstQ<\/strong> and reduce its size by 1.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul><li>top():<ul><li>Return the top element from <strong>firstQ<\/strong> if it is not empty.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul><li>getSize():<ul><li>Return the <strong>currentSize<\/strong> of the queue.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p id=\"-code--implementation-\"><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/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=\"\">class Stack {\n  public:\n    queue &amp;lt; int &amp;gt; firstQ, secondQ;\n  int currentSize;\n  Stack() {\n    currentSize = 0;\n  }\n  int top() {\n    return firstQ.empty() ? -1 : firstQ.front();\n  }\n  int getSize() {\n    return currentSize;\n  }\n  void push(int val) {\n    secondQ.push(val);\n    currentSize += 1;\n    while (!firstQ.empty()) {\n      int x = firstQ.front();\n      secondQ.push(x);\n      firstQ.pop();\n    }\n    swap(firstQ, secondQ);\n  }\n  void pop() {\n    if (!firstQ.empty()) {\n      firstQ.pop();\n      currentSize -= 1;\n    }\n    return;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/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=\"\">public static class Stack {\n  static Queue &amp;lt; Integer &amp;gt; firstQ = new LinkedList &amp;lt; Integer &amp;gt; ();\n  static Queue &amp;lt; Integer &amp;gt; secondQ = new LinkedList &amp;lt; Integer &amp;gt; ();\n  static int currentSize = 0;\n  Stack() {\n    currentSize = 0;\n  }\n  static int top() {\n    return firstQ.isEmpty() ? -1 : firstQ.peek();\n  }\n  static int getSize() {\n    return currentSize;\n  }\n  static void push(int val) {\n    secondQ.add(val);\n    currentSize += 1;\n    while (!firstQ.isEmpty()) {\n      int x = firstQ.peek();\n      secondQ.add(x);\n      firstQ.remove();\n    }\n    Queue &amp;lt; Integer &amp;gt; tempQ = firstQ;\n    firstQ = secondQ;\n    secondQ = tempQ;\n  }\n  static void pop() {\n    if (!firstQ.isEmpty()) {\n      firstQ.remove();\n      currentSize -= 1;\n    }\n    return;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/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=\"\">from queue import Queue\n\n\nclass Stack:\n    def __init__(self):\n        self.firstQ = Queue()\n        self.secondQ = Queue()\n        self.currentSize = 0\n\n    def top(self):\n        if self.firstQ.empty():\n            return -1\n        return self.firstQ.queue[0]\n\n    def getSize(self):\n        return self.currentSize\n\n    def push(self, val):\n        self.secondQ.put(val)\n        self.currentSize += 1\n        while not self.firstQ.empty():\n            self.secondQ.put(self.firstQ.queue[0])\n            self.firstQ.get()\n\n        self.tempQ = self.firstQ\n        self.firstQ = self.secondQ\n        self.secondQ = self.tempQ\n\n    def pop(self):\n        if not self.firstQ.empty():\n            self.firstQ.get()\n            self.currentSize -= 1<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n) for push(), O(1) for the rest.<\/li><li>Space Complexity: O(n) for push(), O(1) for the rest.<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2pop-operation-costly\">Approach 2(Pop Operation Costly)<\/h2>\n\n\n\n<p>We can also form a Stack with 2 Queues, where the <strong>pop()<\/strong> and the <strong>top()<\/strong> operation works in <strong>O(n)<\/strong> and the other functionalities work in <strong>O(1)<\/strong>. Our target will be that for each push operation, the element is just pushed to <strong>firstQ.<\/strong> For our pop operation, if the <strong>secondQ<\/strong> is currently empty, all but the last element from the <strong>firstQ<\/strong> will be moved to the <strong>secondQ.<\/strong> The last element from the <strong>secondQ <\/strong>can then be returned.<\/p>\n\n\n\n<p>The algorithm for each function is as follows:<\/p>\n\n\n\n<ul><li>push(val):&nbsp;<ul><li>Push <strong>val<\/strong> to the front of <strong>firstQ.<\/strong><\/li><\/ul><\/li><li>pop():<ul><li>Other than the very last element in the <strong>firstQ<\/strong>, pop everything out of it and push into the <strong>secondQ. <\/strong>The last element in the <strong>firstQ<\/strong> is the result.<\/li><li>Swap <strong>firstQ<\/strong> and <strong>secondQ.<\/strong><\/li><\/ul><\/li><li>top():<ul><li>Perform the same steps as described in the pop operation, but return the value of the last element remaining in <strong>firstQ<\/strong> before swapping, unless the queue is empty.<\/li><\/ul><\/li><li>getSize():&nbsp;<ul><li>Return the current Stack size.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\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=\"\">class Stack {\n  public:\n    queue &amp;lt; int &amp;gt; firstQ, secondQ;\n  int currentSize;\n  Stack() {\n    currentSize = 0;\n  }\n  int top() {\n    if (firstQ.empty()) {\n      return -1;\n    }\n    int topEle = -1;\n    while (firstQ.size() &amp;gt; 0) {\n      int x = firstQ.front();\n      if (firstQ.size() == 1) {\n        topEle = x;\n      }\n      secondQ.push(x);\n      firstQ.pop();\n    }\n    swap(firstQ, secondQ);\n    return topEle;\n  }\n  int getSize() {\n    return currentSize;\n  }\n  void push(int val) {\n    firstQ.push(val);\n    currentSize += 1;\n  }\n  void pop() {\n    if (!firstQ.empty()) {\n      while (firstQ.size() != 1) {\n        int x = firstQ.front();\n        secondQ.push(x);\n        firstQ.pop();\n      }\n      firstQ.pop();\n      currentSize -= 1;\n      swap(firstQ, secondQ);\n    }\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 Stack {\n  static Queue &amp;lt; Integer &amp;gt; firstQ = new LinkedList &amp;lt; &amp;gt; ();\n  static Queue &amp;lt; Integer &amp;gt; secondQ = new LinkedList &amp;lt; &amp;gt; ();\n  static int currentSize = 0;\n  Stack() {\n    currentSize = 0;\n  }\n  static int top() {\n    if (firstQ.isEmpty()) {\n      return -1;\n    }\n    int topEle = -1;\n    while (firstQ.size() &amp;gt; 0) {\n      int x = firstQ.peek();\n      if (firstQ.size() == 1) {\n        topEle = x;\n      }\n      secondQ.add(x);\n      firstQ.remove();\n    }\n    Queue &amp;lt; Integer &amp;gt; tempQ = firstQ;\n    firstQ = secondQ;\n    secondQ = tempQ;\n  return topEle;\n  }\n  static int getSize() {\n    return currentSize;\n  }\n  static void push(int val) {\n    firstQ.add(val);\n    currentSize += 1;\n  }\n  static void pop() {\n    if (!firstQ.isEmpty()) {\n      while (firstQ.size() != 1) {\n        int x = firstQ.peek();\n        secondQ.add(x);\n        firstQ.remove();\n      }\n      firstQ.remove();\n      currentSize -= 1;\n      Queue &amp;lt; Integer &amp;gt; tempQ = firstQ;\n      firstQ = secondQ;\n      secondQ = tempQ;\n    }\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=\"\">from queue import Queue\n\n\nclass Stack:\n    def __init__(self):\n        self.firstQ = Queue()\n        self.secondQ = Queue()\n        self.currentSize = 0\n\n    def top(self):\n        if self.firstQ.empty():\n            return -1\n        while self.firstQ.qsize() != 1:\n            x = self.firstQ.get()\n            self.secondQ.put(x)\n        topEle = self.firstQ.get()\n  self.secondQ.put(topEle)\n        self.tempQ = self.firstQ\n        self.firstQ = self.secondQ\n        self.secondQ = self.tempQ\n        return topEle\n\n    def getSize(self):\n        return self.currentSize\n\n    def push(self, val):\n        self.firstQ.put(val)\n        self.currentSize += 1\n\n    def pop(self):\n        if not self.firstQ.empty():\n            while self.firstQ.qsize() != 1:\n                x = self.firstQ.get()\n                self.secondQ.put(x)\n            last = self.firstQ.get()\n            self.currentSize -= 1\n            self.tempQ = self.firstQ\n            self.firstQ = self.secondQ\n            self.secondQ = self.tempQ\n        else:\n            return<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n) for top() and pop() operations, O(1) for the rest<\/li><li>Space Complexity: O(n) for top() and pop() operations, O(1) for the rest<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>1. What is the minimum number of Queues required to implement a Stack?<\/strong><\/p>\n\n\n\n<p>A. A minimum of 2 queues is required to implement a Stack.<\/p>\n\n\n\n<p><strong>2. Other than queues, what data structures can be used to implement Stacks?<\/strong><\/p>\n\n\n\n<p>A. Other than queues, stacks can also be implemented using <strong>LinkedList<\/strong> and\/or <strong>Arrays<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Implement a class Stack, using 2 Queues, which can perform the following operations: Push(): Push a&hellip;\n","protected":false},"author":5,"featured_media":4038,"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":[583],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3903"}],"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=3903"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3903\/revisions"}],"predecessor-version":[{"id":4039,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3903\/revisions\/4039"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4038"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3903"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3903"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3903"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}