{"id":798,"date":"2025-07-26T13:27:47","date_gmt":"2025-07-26T07:57:47","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=798"},"modified":"2025-07-26T13:27:48","modified_gmt":"2025-07-26T07:57:48","slug":"implement-stack-using-queues","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/","title":{"rendered":"Implement Stack using Queues | Leetcode 225 | Complete Python Code"},"content":{"rendered":"\n<p>Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (<code>push<\/code>,&nbsp;<code>top<\/code>,&nbsp;<code>pop<\/code>, and&nbsp;<code>empty<\/code>).<\/p>\n\n\n\n<p>Implement the&nbsp;<code>MyStack<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>void push(int x)<\/code>&nbsp;Pushes element x to the top of the stack.<\/li>\n\n\n\n<li><code>int pop()<\/code>&nbsp;Removes the element on the top of the stack and returns it.<\/li>\n\n\n\n<li><code>int top()<\/code>&nbsp;Returns the element on the top of the stack.<\/li>\n\n\n\n<li><code>boolean empty()<\/code>&nbsp;Returns&nbsp;<code>true<\/code>&nbsp;if the stack is empty,&nbsp;<code>false<\/code>&nbsp;otherwise.<\/li>\n<\/ul>\n\n\n\n<p><strong>Notes:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You must use&nbsp;<strong>only<\/strong>&nbsp;standard operations of a queue, which means that only&nbsp;<code>push to back<\/code>,&nbsp;<code>peek\/pop from front<\/code>,&nbsp;<code>size<\/code>&nbsp;and&nbsp;<code>is empty<\/code>&nbsp;operations are valid.<\/li>\n\n\n\n<li>Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue&#8217;s standard operations.<\/li>\n<\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input<\/strong><br>[\"MyStack\", \"push\", \"push\", \"top\", \"pop\", \"empty\"]<br>[[], [1], [2], [], [], []]<br><br><strong>Output<\/strong><br>[null, null, null, 2, 2, false]<br><br><strong>Explanation<\/strong><br>MyStack myStack = new MyStack();<br>myStack.push(1);<br>myStack.push(2);<br>myStack.top(); \/\/ return 2<br>myStack.pop(); \/\/ return 2<br>myStack.empty(); \/\/ return False<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= x &lt;= 9<\/code><\/li>\n\n\n\n<li>At most&nbsp;<code>100<\/code>&nbsp;calls will be made to&nbsp;<code>push<\/code>,&nbsp;<code>pop<\/code>,&nbsp;<code>top<\/code>, and&nbsp;<code>empty<\/code>.<\/li>\n\n\n\n<li>All the calls to&nbsp;<code>pop<\/code>&nbsp;and&nbsp;<code>top<\/code>&nbsp;are valid.<\/li>\n<\/ul>\n\n\n\n<p><strong>Follow-up:<\/strong>&nbsp;Can you implement the stack using only one queue?<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-cd7cdac9-15b9-4e9f-a906-5691ac522c31\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#0-solution-1-normal-approach-using-two-queues\" style=\"\">Solution 1: Normal Approach (Using Two Queues)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#6-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#7-solution-2-optimal-approach-using-one-queue-with-rotation\" style=\"\">Solution 2: Optimal Approach (Using One Queue with Rotation)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#8-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#9-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#10-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#11-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#12-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#13-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#14-summary\" style=\"\">Summary<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/implement-stack-using-queues\/#15-key-takeaways\" style=\"\">Key Takeaways<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-normal-approach-using-two-queues\">Solution 1: Normal Approach (Using Two Queues)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Use two queues to mimic stack behavior. One queue holds the main elements, and the other helps reverse the order during push. When pushing a new element, we add it to the empty queue, then move all elements from the main queue to this new one. This puts the new element at the front, simulating &#8220;top&#8221; of stack. It&#8217;s like pouring items from one line to another to put the newest at the front!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>: Create two queues (q1 and q2) using deque.<\/li>\n\n\n\n<li><strong>Push(x)<\/strong>:\n<ul class=\"wp-block-list\">\n<li>Add x to q2 (temporary queue).<\/li>\n\n\n\n<li>Move all elements from q1 to q2 (reverses order, new x becomes front after swap).<\/li>\n\n\n\n<li>Swap q1 and q2 (now q1 has new x at front).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Pop()<\/strong>: Remove and return front of q1.<\/li>\n\n\n\n<li><strong>Top()<\/strong>: Return front of q1 without removing.<\/li>\n\n\n\n<li><strong>Empty()<\/strong>: Check if q1 is empty.<\/li>\n\n\n\n<li><strong>Why Normal?<\/strong>: Easy to understand, but push is O(n) due to moving elements. Pop\/top are O(1).<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"from collections import deque\n\nclass MyStack:\n    def __init__(self):\n        self.q1 = deque()  # Main queue\n        self.q2 = deque()  # Helper queue\n    \n    def push(self, x: int) -&gt; None:\n        self.q2.append(x)  # Add new element to helper\n        # Move all from main to helper\n        while self.q1:\n            self.q2.append(self.q1.popleft())\n        # Swap: helper becomes main\n        self.q1, self.q2 = self.q2, self.q1\n    \n    def pop(self) -&gt; int:\n        return self.q1.popleft()  # Remove front (top of stack)\n    \n    def top(self) -&gt; int:\n        return self.q1[0]  # Peek front\n    \n    def empty(self) -&gt; bool:\n        return len(self.q1) == 0  # Check if main is empty\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> collections <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> deque<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">MyStack<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1 = deque()  <\/span><span style=\"color: #6A9955\"># Main queue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q2 = deque()  <\/span><span style=\"color: #6A9955\"># Helper queue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">push<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">x<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q2.append(x)  <\/span><span style=\"color: #6A9955\"># Add new element to helper<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Move all from main to helper<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q2.append(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1.popleft())<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Swap: helper becomes main<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1, <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q2 = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q2, <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">pop<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1.popleft()  <\/span><span style=\"color: #6A9955\"># Remove front (top of stack)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">top<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Peek front<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">empty<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">bool<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.q1) == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Check if main is empty<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We maintain q1 as the &#8220;stack&#8221; where the front is the top. During push, we use q2 to temporarily hold the new element, then pour q1 into q2 (which puts old elements behind the new one). Swapping makes q1 the updated queue with new top at front. Pop and top directly use q1&#8217;s front (O(1)). Empty checks q1&#8217;s length.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>push()<\/strong>: O(n) &#8211; Moving n elements<\/li>\n\n\n\n<li><strong>pop()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>top()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>empty()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>Space<\/strong>: O(n) &#8211; Two queues holding up to n elements<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This is like having two lines: you add the new person to an empty line, then make everyone from the main line join behind them. Now the new person is first in line (top of stack). Simple but involves moving people each time you add someone!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-solution-2-optimal-approach-using-one-queue-with-rotation\">Solution 2: Optimal Approach (Using One Queue with Rotation)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-intuition\">Intuition<\/h3>\n\n\n\n<p>Use just one queue and &#8220;rotate&#8221; it during push to bring the new element to the front. After adding the new element to the end, we remove and re-add the front elements (n-1 times) to move them behind the new one. This makes the new element the front (top of stack). It&#8217;s like spinning a line of people so the newest joins at the end but then we cycle the others to put the new one first!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>: Create one queue using deque.<\/li>\n\n\n\n<li><strong>Push(x)<\/strong>:\n<ul class=\"wp-block-list\">\n<li>Add x to the end.<\/li>\n\n\n\n<li>Rotate: For (size-1) times, remove front and add to end (moves old elements behind new x).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Pop()<\/strong>: Remove and return front.<\/li>\n\n\n\n<li><strong>Top()<\/strong>: Return front without removing.<\/li>\n\n\n\n<li><strong>Empty()<\/strong>: Check if queue is empty.<\/li>\n\n\n\n<li><strong>Why Optimal?<\/strong>: Uses only one queue (less space), push is O(n), pop\/top O(1). Good for space-constrained scenarios.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"from collections import deque\n\nclass MyStack:\n    def __init__(self):\n        self.queue = deque()  # Single queue\n    \n    def push(self, x: int) -&gt; None:\n        self.queue.append(x)  # Add to end\n        # Rotate: move front elements to end (len-1 times)\n        for _ in range(len(self.queue) - 1):\n            self.queue.append(self.queue.popleft())\n    \n    def pop(self) -&gt; int:\n        return self.queue.popleft()  # Remove front (top)\n    \n    def top(self) -&gt; int:\n        return self.queue[0]  # Peek front\n    \n    def empty(self) -&gt; bool:\n        return len(self.queue) == 0  # Check if empty\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> collections <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> deque<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">MyStack<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue = deque()  <\/span><span style=\"color: #6A9955\"># Single queue<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">push<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">x<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue.append(x)  <\/span><span style=\"color: #6A9955\"># Add to end<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Rotate: move front elements to end (len-1 times)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue.append(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue.popleft())<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">pop<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue.popleft()  <\/span><span style=\"color: #6A9955\"># Remove front (top)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">top<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]  <\/span><span style=\"color: #6A9955\"># Peek front<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">empty<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">bool<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.queue) == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Check if empty<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>The single queue stores elements with front as top. Push adds x to end, then rotates by popping front and appending to end (len-1 times), which cycles old elements behind x, making x the new front. Pop and top use the front directly (O(1)). Empty checks length.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>push()<\/strong>: O(n) &#8211; Rotating n-1 elements<\/li>\n\n\n\n<li><strong>pop()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>top()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>empty()<\/strong>: O(1)<\/li>\n\n\n\n<li><strong>Space<\/strong>: O(n) &#8211; Single queue<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This is like a single line where you add the new person at the end, then have everyone in front step to the back one by one until the new person is first. No extra line needed, but still involves moving people when adding!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"14-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Push Time<\/th><th>Pop Time<\/th><th>Space<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Normal (Two Queues)<\/td><td>O(n)<\/td><td>O(1)<\/td><td>O(n)<\/td><td>Easy understanding<\/td><\/tr><tr><td>Optimal (One Queue)<\/td><td>O(n)<\/td><td>O(1)<\/td><td>O(n)<\/td><td>Space efficiency<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Both approaches achieve stack behavior using queues, with O(n) time for push and O(1) for pop\/top. The&nbsp;<strong>optimal (one queue)<\/strong>&nbsp;saves space by avoiding a second queue and is often preferred in interviews to show optimization. If pops are more frequent than pushes, these are good (since pop is fast).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"15-key-takeaways\">Key Takeaways<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Stacks (LIFO) can be made from queues (FIFO) by reversing order during operations.<\/li>\n\n\n\n<li>Tradeoff: Make push slow (O(n)) to keep pop fast (O(1)), or vice versa.<\/li>\n\n\n\n<li>In interviews, explain why you chose one vs. two queues (space vs. simplicity).<\/li>\n\n\n\n<li>Practice: Try implementing the reverse (queue using stacks) or add more methods like size!<\/li>\n<\/ul>\n\n\n\n<p>This should make implementing stack with queues clear and easy to remember!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push,&nbsp;top,&nbsp;pop, and&nbsp;empty). Implement the&nbsp;MyStack&nbsp;class: Notes: Example 1: Input[&#8220;MyStack&#8221;, &#8220;push&#8221;, &#8220;push&#8221;, &#8220;top&#8221;, &#8220;pop&#8221;, &#8220;empty&#8221;][[], [1], [2], [], [], []]Output[null, null, null, 2, 2, false]ExplanationMyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); \/\/ return 2myStack.pop(); \/\/ return 2myStack.empty(); \/\/<\/p>\n","protected":false},"author":1,"featured_media":799,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[8,37],"class_list":{"0":"post-798","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-easy","10":"tag-stack-and-queues"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/implement-stack-using-queues-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/798","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=798"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/798\/revisions"}],"predecessor-version":[{"id":803,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/798\/revisions\/803"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/799"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=798"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=798"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}