<p>Suppose we have two stacks and no other temporary variable.</p>

<p>Is to possible to "construct" a queue data structure using only the two stacks?</p>

[{'answer_id': 69206, 'author': 'Tyler', 'author_id': 3561, 'author_profile': 'https://Stackoverflow.com/users/3561', 'pm_score': 4, 'selected': False, 'text': "<p>The time complexities would be worse, though.  A good queue implementation does everything in constant time.</p>\n\n<p><strong>Edit</strong></p>\n\n<p>Not sure why my answer has been downvoted here.  If we program, we care about time complexity, and using two standard stacks to make a queue is inefficient.  It's a very valid and relevant point.  If someone else feels the need to downvote this more, I would be interested to know why.</p>\n\n<p><em>A little more detail</em>: on why using two stacks is worse than just a queue: if you use two stacks, and someone calls dequeue while the outbox is empty, you need linear time to get to the bottom of the inbox (as you can see in Dave's code).</p>\n\n<p>You can implement a queue as a singly-linked list (each element points to the next-inserted element), keeping an extra pointer to the last-inserted element for pushes (or making it a cyclic list).  Implementing queue and dequeue on this data structure is very easy to do in constant time.  That's worst-case constant time, not amortized.  And, as the comments seem to ask for this clarification, worst-case constant time is strictly better than amortized constant time.</p>\n"}, {'answer_id': 69377, 'author': 'user11055', 'author_id': 11055, 'author_profile': 'https://Stackoverflow.com/users/11055', 'pm_score': 2, 'selected': False, 'text': '<p>You\'ll have to pop everything off the first stack to get the bottom element. Then put them all back onto the second stack for every "dequeue" operation.</p>\n'}, {'answer_id': 69436, 'author': 'Dave L.', 'author_id': 3093, 'author_profile': 'https://Stackoverflow.com/users/3093', 'pm_score': 10, 'selected': False, 'text': '<p>Keep 2 stacks, let\'s call them <code>inbox</code> and <code>outbox</code>.</p>\n\n<p><strong>Enqueue</strong>:</p>\n\n<ul>\n<li>Push the new element onto <code>inbox</code></li>\n</ul>\n\n<p><strong>Dequeue</strong>:</p>\n\n<ul>\n<li><p>If <code>outbox</code> is empty, refill it by popping each element from <code>inbox</code> and pushing it onto <code>outbox</code></p></li>\n<li><p>Pop and return the top element from <code>outbox</code></p></li>\n</ul>\n\n<p>Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.</p>\n\n<p>Here\'s an implementation in Java:</p>\n\n<pre class="lang-java prettyprint-override"><code>public class Queue&lt;E&gt;\n{\n\n    private Stack&lt;E&gt; inbox = new Stack&lt;E&gt;();\n    private Stack&lt;E&gt; outbox = new Stack&lt;E&gt;();\n\n    public void queue(E item) {\n        inbox.push(item);\n    }\n\n    public E dequeue() {\n        if (outbox.isEmpty()) {\n            while (!inbox.isEmpty()) {\n               outbox.push(inbox.pop());\n            }\n        }\n        return outbox.pop();\n    }\n\n}\n</code></pre>\n'}, {'answer_id': 77010, 'author': 'pythonquick', 'author_id': 6225, 'author_profile': 'https://Stackoverflow.com/users/6225', 'pm_score': 6, 'selected': False, 'text': '<p>You can even simulate a queue using only one stack. The second (temporary) stack can be simulated by the call stack of recursive calls to the insert method. </p>\n\n<p>The principle stays the same when inserting a new element into the queue: </p>\n\n<ul>\n<li>You need to transfer elements from one stack to another temporary stack, to reverse their order. </li>\n<li>Then push the new element to be inserted, onto the temporary stack</li>\n<li>Then transfer the elements back to the original stack</li>\n<li>The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)</li>\n</ul>\n\n<p>A Queue class using only one Stack, would be as follows:</p>\n\n<pre><code>public class SimulatedQueue&lt;E&gt; {\n    private java.util.Stack&lt;E&gt; stack = new java.util.Stack&lt;E&gt;();\n\n    public void insert(E elem) {\n        if (!stack.empty()) {\n            E topElem = stack.pop();\n            insert(elem);\n            stack.push(topElem);\n        }\n        else\n            stack.push(elem);\n    }\n\n    public E remove() {\n        return stack.pop();\n    }\n}\n</code></pre>\n'}, {'answer_id': 10111315, 'author': 'PradGar', 'author_id': 1028292, 'author_profile': 'https://Stackoverflow.com/users/1028292', 'pm_score': -1, 'selected': False, 'text': '<pre class="lang-java prettyprint-override"><code>public class QueueUsingStacks&lt;T&gt;\n{\n    private LinkedListStack&lt;T&gt; stack1;\n    private LinkedListStack&lt;T&gt; stack2;\n\n    public QueueUsingStacks()\n    {\n        stack1=new LinkedListStack&lt;T&gt;();\n        stack2 = new LinkedListStack&lt;T&gt;();\n\n    }\n    public void Copy(LinkedListStack&lt;T&gt; source,LinkedListStack&lt;T&gt; dest )\n    {\n        while(source.Head!=null)\n        {\n            dest.Push(source.Head.Data);\n            source.Head = source.Head.Next;\n        }\n    }\n    public void Enqueue(T entry)\n    {\n\n       stack1.Push(entry);\n    }\n    public T Dequeue()\n    {\n        T obj;\n        if (stack2 != null)\n        {\n            Copy(stack1, stack2);\n             obj = stack2.Pop();\n            Copy(stack2, stack1);\n        }\n        else\n        {\n            throw new Exception("Stack is empty");\n        }\n        return obj;\n    }\n\n    public void Display()\n    {\n        stack1.Display();\n    }\n\n\n}\n</code></pre>\n\n<p>For every enqueue operation, we add to the top of the stack1. For every dequeue, we empty the content\'s of stack1 into stack2, and remove the element at top of the stack.Time complexity is O(n) for dequeue, as we have to copy the stack1 to stack2. time complexity of enqueue is the same as a regular stack</p>\n'}, {'answer_id': 14078077, 'author': 'Harry He', 'author_id': 1092195, 'author_profile': 'https://Stackoverflow.com/users/1092195', 'pm_score': 2, 'selected': False, 'text': '<p>Two stacks in the queue are defined as <i>stack1</i> and <i>stack2</i>.</p>\n\n<p><strong>Enqueue:</strong>\nThe euqueued elements are always pushed into <i>stack1</i></p>\n\n<p><strong>Dequeue:</strong>\nThe top of <i>stack2</i> can be popped out since it is the first element inserted into queue when <i>stack2</i> is not empty. When <i>stack2</i> is empty, we pop all elements from <i>stack1</i> and push them into <i>stack2</i> one by one. The first element in a queue is pushed into the bottom of <i>stack1</i>. It can be popped out directly after popping and pushing operations since it is on the top of <i>stack2</i>.</p>\n\n<p>The following is same C++ sample code:</p>\n\n<pre><code>template &lt;typename T&gt; class CQueue\n{\npublic:\n    CQueue(void);\n    ~CQueue(void);\n\n    void appendTail(const T&amp; node); \n    T deleteHead();                 \n\nprivate:\n    stack&lt;T&gt; stack1;\n    stack&lt;T&gt; stack2;\n};\n\ntemplate&lt;typename T&gt; void CQueue&lt;T&gt;::appendTail(const T&amp; element) {\n    stack1.push(element);\n} \n\ntemplate&lt;typename T&gt; T CQueue&lt;T&gt;::deleteHead() {\n    if(stack2.size()&lt;= 0) {\n        while(stack1.size()&gt;0) {\n            T&amp; data = stack1.top();\n            stack1.pop();\n            stack2.push(data);\n        }\n    }\n\n\n    if(stack2.size() == 0)\n        throw new exception("queue is empty");\n\n\n    T head = stack2.top();\n    stack2.pop();\n\n\n    return head;\n}\n</code></pre>\n\n<p>This solution is borrowed from <a href="http://codercareer.blogspot.com/2011/10/no-17-queue-implemented-with-two-stacks.html" rel="nofollow">my blog</a>. More detailed analysis with step-by-step operation simulations is available in my blog webpage.</p>\n'}, {'answer_id': 22750794, 'author': 'Rahul Gandhi', 'author_id': 2860486, 'author_profile': 'https://Stackoverflow.com/users/2860486', 'pm_score': 3, 'selected': False, 'text': '<p>Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. </p>\n\n<p>q can be implemented in <strong>two</strong> ways:</p>\n\n<p><strong>Method 1 (By making enQueue operation costly)</strong></p>\n\n<p>This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.</p>\n\n<pre><code>enQueue(q, x)\n1) While stack1 is not empty, push everything from stack1 to stack2.\n2) Push x to stack1 (assuming size of stacks is unlimited).\n3) Push everything back to stack1.\ndeQueue(q)\n1) If stack1 is empty then error\n2) Pop an item from stack1 and return it.\n</code></pre>\n\n<p><strong>Method 2 (By making deQueue operation costly)</strong></p>\n\n<p>In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.</p>\n\n<pre><code>enQueue(q,  x)\n 1) Push x to stack1 (assuming size of stacks is unlimited).\n\ndeQueue(q)\n 1) If both stacks are empty then error.\n 2) If stack2 is empty\n   While stack1 is not empty, push everything from stack1 to stack2.\n 3) Pop the element from stack2 and return it.\n</code></pre>\n\n<p>Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.</p>\n'}, {'answer_id': 33095936, 'author': 'imvp', 'author_id': 4092635, 'author_profile': 'https://Stackoverflow.com/users/4092635', 'pm_score': 0, 'selected': False, 'text': '<pre><code>// Two stacks s1 Original and s2 as Temp one\n    private Stack&lt;Integer&gt; s1 = new Stack&lt;Integer&gt;();\n    private Stack&lt;Integer&gt; s2 = new Stack&lt;Integer&gt;();\n\n    /*\n     * Here we insert the data into the stack and if data all ready exist on\n     * stack than we copy the entire stack s1 to s2 recursively and push the new\n     * element data onto s1 and than again recursively call the s2 to pop on s1.\n     * \n     * Note here we can use either way ie We can keep pushing on s1 and than\n     * while popping we can remove the first element from s2 by copying\n     * recursively the data and removing the first index element.\n     */\n    public void insert( int data )\n    {\n        if( s1.size() == 0 )\n        {\n            s1.push( data );\n        }\n        else\n        {\n            while( !s1.isEmpty() )\n            {\n                s2.push( s1.pop() );\n            }\n            s1.push( data );\n            while( !s2.isEmpty() )\n            {\n                s1.push( s2.pop() );\n            }\n        }\n    }\n\n    public void remove()\n    {\n        if( s1.isEmpty() )\n        {\n            System.out.println( "Empty" );\n        }\n        else\n        {\n            s1.pop();\n\n        }\n    }\n</code></pre>\n'}, {'answer_id': 37376579, 'author': 'John Leidegren', 'author_id': 58961, 'author_profile': 'https://Stackoverflow.com/users/58961', 'pm_score': 0, 'selected': False, 'text': '<p>I\'ll answer this question in Go because Go does not have a rich a lot of collections in its standard library.</p>\n\n<p>Since a stack is really easy to implement I thought I\'d try and use two stacks to accomplish a double ended queue. To better understand how I arrived at my answer I\'ve split the implementation in two parts, the first part is hopefully easier to understand but it\'s incomplete.</p>\n\n<pre><code>type IntQueue struct {\n    front       []int\n    back        []int\n}\n\nfunc (q *IntQueue) PushFront(v int) {\n    q.front = append(q.front, v)\n}\n\nfunc (q *IntQueue) Front() int {\n    if len(q.front) &gt; 0 {\n        return q.front[len(q.front)-1]\n    } else {\n        return q.back[0]\n    }\n}\n\nfunc (q *IntQueue) PopFront() {\n    if len(q.front) &gt; 0 {\n        q.front = q.front[:len(q.front)-1]\n    } else {\n        q.back = q.back[1:]\n    }\n}\n\nfunc (q *IntQueue) PushBack(v int) {\n    q.back = append(q.back, v)\n}\n\nfunc (q *IntQueue) Back() int {\n    if len(q.back) &gt; 0 {\n        return q.back[len(q.back)-1]\n    } else {\n        return q.front[0]\n    }\n}\n\nfunc (q *IntQueue) PopBack() {\n    if len(q.back) &gt; 0 {\n        q.back = q.back[:len(q.back)-1]\n    } else {\n        q.front = q.front[1:]\n    }\n}\n</code></pre>\n\n<p>It\'s basically two stacks where we allow the bottom of the stacks to be manipulated by each other. I\'ve also used the STL naming conventions, where the traditional push, pop, peek operations of a stack have a front/back prefix whether they refer to the front or back of the queue.</p>\n\n<p>The issue with the above code is that it doesn\'t use memory very efficiently. Actually, it grows endlessly until you run out of space. That\'s really bad. The fix for this is to simply reuse the bottom of the stack space whenever possible. We have to introduce an offset to track this since a slice in Go cannot grow in the front once shrunk.</p>\n\n<pre><code>type IntQueue struct {\n    front       []int\n    frontOffset int\n    back        []int\n    backOffset  int\n}\n\nfunc (q *IntQueue) PushFront(v int) {\n    if q.backOffset &gt; 0 {\n        i := q.backOffset - 1\n        q.back[i] = v\n        q.backOffset = i\n    } else {\n        q.front = append(q.front, v)\n    }\n}\n\nfunc (q *IntQueue) Front() int {\n    if len(q.front) &gt; 0 {\n        return q.front[len(q.front)-1]\n    } else {\n        return q.back[q.backOffset]\n    }\n}\n\nfunc (q *IntQueue) PopFront() {\n    if len(q.front) &gt; 0 {\n        q.front = q.front[:len(q.front)-1]\n    } else {\n        if len(q.back) &gt; 0 {\n            q.backOffset++\n        } else {\n            panic("Cannot pop front of empty queue.")\n        }\n    }\n}\n\nfunc (q *IntQueue) PushBack(v int) {\n    if q.frontOffset &gt; 0 {\n        i := q.frontOffset - 1\n        q.front[i] = v\n        q.frontOffset = i\n    } else {\n        q.back = append(q.back, v)\n    }\n}\n\nfunc (q *IntQueue) Back() int {\n    if len(q.back) &gt; 0 {\n        return q.back[len(q.back)-1]\n    } else {\n        return q.front[q.frontOffset]\n    }\n}\n\nfunc (q *IntQueue) PopBack() {\n    if len(q.back) &gt; 0 {\n        q.back = q.back[:len(q.back)-1]\n    } else {\n        if len(q.front) &gt; 0 {\n            q.frontOffset++\n        } else {\n            panic("Cannot pop back of empty queue.")\n        }\n    }\n}\n</code></pre>\n\n<p>It\'s a lot of small functions but of the 6 functions 3 of them are just mirrors of the other.</p>\n'}, {'answer_id': 38801986, 'author': 'realPK', 'author_id': 853001, 'author_profile': 'https://Stackoverflow.com/users/853001', 'pm_score': -1, 'selected': False, 'text': '<p>Queue implementation using two java.util.Stack objects:</p>\n\n<pre><code>public final class QueueUsingStacks&lt;E&gt; {\n\n        private final Stack&lt;E&gt; iStack = new Stack&lt;&gt;();\n        private final Stack&lt;E&gt; oStack = new Stack&lt;&gt;();\n\n        public void enqueue(E e) {\n            iStack.push(e);\n        }\n\n        public E dequeue() {\n            if (oStack.isEmpty()) {\n                if (iStack.isEmpty()) {\n                    throw new NoSuchElementException("No elements present in Queue");\n                }\n                while (!iStack.isEmpty()) {\n                    oStack.push(iStack.pop());\n                }\n            }\n            return oStack.pop();\n        }\n\n        public boolean isEmpty() {\n            if (oStack.isEmpty() &amp;&amp; iStack.isEmpty()) {\n                return true;\n            }\n            return false;\n        }\n\n        public int size() {\n            return iStack.size() + oStack.size();\n        }\n\n}\n</code></pre>\n'}, {'answer_id': 39089983, 'author': 'Levent Divilioglu', 'author_id': 3128926, 'author_profile': 'https://Stackoverflow.com/users/3128926', 'pm_score': 8, 'selected': False, 'text': '<h1>A - How To Reverse A Stack</h1>\n\n<p>To understand how to construct a queue using two stacks, you should understand how to reverse a stack crystal clear. Remember how stack works, it is very similar to the dish stack on your kitchen. The last washed dish will be on the top of the clean stack, which is called as <strong>L</strong>ast <strong>I</strong>n <strong>F</strong>irst <strong>O</strong>ut (LIFO) in computer science.</p>\n\n<p>Lets imagine our stack like a bottle as below;</p>\n\n<p><a href="https://i.stack.imgur.com/MwjaI.png"><img src="https://i.stack.imgur.com/MwjaI.png" alt="enter image description here"></a></p>\n\n<p>If we push integers 1,2,3 respectively, then 3 will be on the top of the stack. Because 1 will be pushed first, then 2 will be put on the top of 1. Lastly, 3 will be put on the top of the stack and latest state of our stack represented as a bottle will be as below;</p>\n\n<p><a href="https://i.stack.imgur.com/J7ec0.png"><img src="https://i.stack.imgur.com/J7ec0.png" alt="enter image description here"></a></p>\n\n<p>Now we have our stack represented as a bottle is populated with values 3,2,1. And we want to reverse the stack so that the top element of the stack will be 1 and bottom element of the stack will be 3. What we can do ? We can take the bottle and hold it upside down so that all the values should reverse in order ?</p>\n\n<p><a href="https://i.stack.imgur.com/WZNxS.png"><img src="https://i.stack.imgur.com/WZNxS.png" alt="enter image description here"></a></p>\n\n<p>Yes we can do that, but that\'s a bottle. To do the same process, we need to have a second stack that which is going to store the first stack elements in reverse order. Let\'s put our populated stack to the left and our new empty stack to the right. To reverse the order of the elements, we are going to pop each element from left stack, and push them to the right stack. You can see what happens as we do so on the image below;</p>\n\n<p><a href="https://i.stack.imgur.com/1YfMo.png"><img src="https://i.stack.imgur.com/1YfMo.png" alt="enter image description here"></a></p>\n\n<p>So we know how to reverse a stack.</p>\n\n<h1>B - Using Two Stacks As A Queue</h1>\n\n<p>On previous part, I\'ve explained how can we reverse the order of stack elements. This was important, because if we push and pop elements to the stack, the output will be exactly in reverse order of a queue. Thinking on an example, let\'s push the array of integers <code>{1, 2, 3, 4, 5}</code> to a stack. If we pop the elements and print them until the stack is empty, we will get the array in the reverse order of pushing order, which will be <code>{5, 4, 3, 2, 1}</code> Remember that for the same input, if we dequeue the queue until the queue is empty, the output will be <code>{1, 2, 3, 4, 5}</code>. So it is obvious that for the same input order of elements, output of the queue is exactly reverse of the output of a stack. As we know how to reverse a stack using an extra stack, we can construct a queue using two stacks.</p>\n\n<p>Our queue model will consist of two stacks. One stack will be used for <code>enqueue</code> operation (stack #1 on the left, will be called as Input Stack), another stack will be used for the <code>dequeue</code> operation (stack #2 on the right, will be called as Output Stack). Check out the image below;</p>\n\n<p><a href="https://i.stack.imgur.com/xyWPR.png"><img src="https://i.stack.imgur.com/xyWPR.png" alt="enter image description here"></a></p>\n\n<p>Our pseudo-code is as below;</p>\n\n<hr>\n\n<h3>Enqueue Operation</h3>\n\n<pre><code>Push every input element to the Input Stack\n</code></pre>\n\n<h3>Dequeue Operation</h3>\n\n<pre><code>If ( Output Stack is Empty)\n    pop every element in the Input Stack\n    and push them to the Output Stack until Input Stack is Empty\n\npop from Output Stack\n</code></pre>\n\n<hr>\n\n<p>Let\'s enqueue the integers <code>{1, 2, 3}</code> respectively. Integers will be pushed on the <strong>Input Stack</strong> (<strong>Stack #1</strong>) which is located on the left;</p>\n\n<p><a href="https://i.stack.imgur.com/lX1EP.png"><img src="https://i.stack.imgur.com/lX1EP.png" alt="enter image description here"></a></p>\n\n<p>Then what will happen if we execute a dequeue operation? Whenever a dequeue operation is executed, queue is going to check if the Output Stack is empty or not(see the pseudo-code above) If the Output Stack is empty, then the Input Stack is going to be extracted on the output so the elements of Input Stack will be reversed. Before returning a value, the state of the queue will be as below;</p>\n\n<p><a href="https://i.stack.imgur.com/9f03R.png"><img src="https://i.stack.imgur.com/9f03R.png" alt="enter image description here"></a></p>\n\n<p>Check out the order of elements in the Output Stack (Stack #2). It\'s obvious that we can pop the elements from the Output Stack so that the output will be same as if we dequeued from a queue. Thus, if we execute two dequeue operations, first we will get <code>{1, 2}</code> respectively. Then element 3 will be the only element of the Output Stack, and the Input Stack will be empty. If we enqueue the elements 4 and 5, then the state of the queue will be as follows;</p>\n\n<p><a href="https://i.stack.imgur.com/CXQZB.png"><img src="https://i.stack.imgur.com/CXQZB.png" alt="enter image description here"></a></p>\n\n<p>Now the Output Stack is not empty, and if we execute a dequeue operation, only 3 will be popped out from the Output Stack. Then the state will be seen as below;</p>\n\n<p><a href="https://i.stack.imgur.com/hOPu3.png"><img src="https://i.stack.imgur.com/hOPu3.png" alt="enter image description here"></a></p>\n\n<p>Again, if we execute two more dequeue operations, on the first dequeue operation, queue will check if the Output Stack is empty, which is true. Then pop out the elements of the Input Stack and push them to the Output Stack unti the Input Stack is empty, then the state of the Queue will be as below;</p>\n\n<p><a href="https://i.stack.imgur.com/vuLsw.png"><img src="https://i.stack.imgur.com/vuLsw.png" alt="enter image description here"></a></p>\n\n<p>Easy to see, the output of the two dequeue operations will be <code>{4, 5}</code></p>\n\n<h1>C - Implementation Of Queue Constructed with Two Stacks</h1>\n\n<p>Here is an implementation in Java. I\'m not going to use the existing implementation of Stack so the example here is going to reinvent the wheel;</p>\n\n<h1>C - 1) MyStack class : A Simple Stack Implementation</h1>\n\n<pre><code>public class MyStack&lt;T&gt; {\n\n    // inner generic Node class\n    private class Node&lt;T&gt; {\n        T data;\n        Node&lt;T&gt; next;\n\n        public Node(T data) {\n            this.data = data;\n        }\n    }\n\n    private Node&lt;T&gt; head;\n    private int size;\n\n    public void push(T e) {\n        Node&lt;T&gt; newElem = new Node(e);\n\n        if(head == null) {\n            head = newElem;\n        } else {\n            newElem.next = head;\n            head = newElem;     // new elem on the top of the stack\n        }\n\n        size++;\n    }\n\n    public T pop() {\n        if(head == null)\n            return null;\n\n        T elem = head.data;\n        head = head.next;   // top of the stack is head.next\n\n        size--;\n\n        return elem;\n    }\n\n    public int size() {\n        return size;\n    }\n\n    public boolean isEmpty() {\n        return size == 0;\n    }\n\n    public void printStack() {\n        System.out.print("Stack: ");\n\n        if(size == 0)\n            System.out.print("Empty !");\n        else\n            for(Node&lt;T&gt; temp = head; temp != null; temp = temp.next)\n                System.out.printf("%s ", temp.data);\n\n        System.out.printf("\\n");\n    }\n}\n</code></pre>\n\n<h1>C - 2) MyQueue class : Queue Implementation Using Two Stacks</h1>\n\n<pre><code>public class MyQueue&lt;T&gt; {\n\n    private MyStack&lt;T&gt; inputStack;      // for enqueue\n    private MyStack&lt;T&gt; outputStack;     // for dequeue\n    private int size;\n\n    public MyQueue() {\n        inputStack = new MyStack&lt;&gt;();\n        outputStack = new MyStack&lt;&gt;();\n    }\n\n    public void enqueue(T e) {\n        inputStack.push(e);\n        size++;\n    }\n\n    public T dequeue() {\n        // fill out all the Input if output stack is empty\n        if(outputStack.isEmpty())\n            while(!inputStack.isEmpty())\n                outputStack.push(inputStack.pop());\n\n        T temp = null;\n        if(!outputStack.isEmpty()) {\n            temp = outputStack.pop();\n            size--;\n        }\n\n        return temp;\n    }\n\n    public int size() {\n        return size;\n    }\n\n    public boolean isEmpty() {\n        return size == 0;\n    }\n\n}\n</code></pre>\n\n<h1>C - 3) Demo Code</h1>\n\n<pre><code>public class TestMyQueue {\n\n    public static void main(String[] args) {\n        MyQueue&lt;Integer&gt; queue = new MyQueue&lt;&gt;();\n\n        // enqueue integers 1..3\n        for(int i = 1; i &lt;= 3; i++)\n            queue.enqueue(i);\n\n        // execute 2 dequeue operations \n        for(int i = 0; i &lt; 2; i++)\n            System.out.println("Dequeued: " + queue.dequeue());\n\n        // enqueue integers 4..5\n        for(int i = 4; i &lt;= 5; i++)\n            queue.enqueue(i);\n\n        // dequeue the rest\n        while(!queue.isEmpty())\n            System.out.println("Dequeued: " + queue.dequeue());\n    }\n\n}\n</code></pre>\n\n<h1>C - 4) Sample Output</h1>\n\n<pre><code>Dequeued: 1\nDequeued: 2\nDequeued: 3\nDequeued: 4\nDequeued: 5\n</code></pre>\n'}, {'answer_id': 40602980, 'author': 'Jaydeep Shil', 'author_id': 3428626, 'author_profile': 'https://Stackoverflow.com/users/3428626', 'pm_score': 2, 'selected': False, 'text': '<p><strong>for c# developer here is the complete program :</strong></p>\n\n<pre><code>using System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Text;\nusing System.Threading.Tasks;\n\nnamespace QueueImplimentationUsingStack\n{\n    class Program\n    {\n        public class Stack&lt;T&gt;\n        {\n            public int size;\n            public Node&lt;T&gt; head;\n            public void Push(T data)\n            {\n                Node&lt;T&gt; node = new Node&lt;T&gt;();\n                node.data = data;\n                if (head == null)\n                    head = node;\n                else\n                {\n                    node.link = head;\n                    head = node;\n                }\n                size++;\n                Display();\n            }\n            public Node&lt;T&gt; Pop()\n            {\n                if (head == null)\n                    return null;\n                else\n                {\n                    Node&lt;T&gt; temp = head;\n                    //temp.link = null;\n                    head = head.link;\n                    size--;\n                    Display();\n                    return temp;\n                }\n            }\n            public void Display()\n            {\n                if (size == 0)\n                    Console.WriteLine("Empty");\n                else\n                {\n                    Console.Clear();\n                    Node&lt;T&gt; temp = head;\n                    while (temp!= null)\n                    {\n                        Console.WriteLine(temp.data);\n                        temp = temp.link;\n                    }\n                }\n            }\n        }\n\n        public class Queue&lt;T&gt;\n        {\n            public int size;\n            public Stack&lt;T&gt; inbox;\n            public Stack&lt;T&gt; outbox;\n            public Queue()\n            {\n                inbox = new Stack&lt;T&gt;();\n                outbox = new Stack&lt;T&gt;();\n            }\n            public void EnQueue(T data)\n            {\n                inbox.Push(data);\n                size++;\n            }\n            public Node&lt;T&gt; DeQueue()\n            {\n                if (outbox.size == 0)\n                {\n                    while (inbox.size != 0)\n                    {\n                        outbox.Push(inbox.Pop().data);\n                    }\n                }\n                Node&lt;T&gt; temp = new Node&lt;T&gt;();\n                if (outbox.size != 0)\n                {\n                    temp = outbox.Pop();\n                    size--;\n                }\n                return temp;\n            }\n\n        }\n        public class Node&lt;T&gt;\n        {\n            public T data;\n            public Node&lt;T&gt; link;\n        }\n\n        static void Main(string[] args)\n        {\n            Queue&lt;int&gt; q = new Queue&lt;int&gt;();\n            for (int i = 1; i &lt;= 3; i++)\n                q.EnQueue(i);\n           // q.Display();\n            for (int i = 1; i &lt; 3; i++)\n                q.DeQueue();\n            //q.Display();\n            Console.ReadKey();\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 44273758, 'author': 'Santhosh', 'author_id': 6851131, 'author_profile': 'https://Stackoverflow.com/users/6851131', 'pm_score': 2, 'selected': False, 'text': '<p>A solution in c#</p>\n\n<pre><code>public class Queue&lt;T&gt; where T : class\n{\n    private Stack&lt;T&gt; input = new Stack&lt;T&gt;();\n    private Stack&lt;T&gt; output = new Stack&lt;T&gt;();\n    public void Enqueue(T t)\n    {\n        input.Push(t);\n    }\n\n    public T Dequeue()\n    {\n        if (output.Count == 0)\n        {\n            while (input.Count != 0)\n            {\n                output.Push(input.Pop());\n            }\n        }\n\n        return output.Pop();\n    }\n}\n</code></pre>\n'}, {'answer_id': 46390588, 'author': 'Irshad ck', 'author_id': 8276943, 'author_profile': 'https://Stackoverflow.com/users/8276943', 'pm_score': -1, 'selected': False, 'text': '<p>here is my solution in Java using linkedlist.</p>\n<pre class="lang-java prettyprint-override"><code>class queue&lt;T&gt;{\n    static class Node&lt;T&gt;{\n        private T data;\n        private Node&lt;T&gt; next;\n        Node(T data){\n            this.data = data;\n            next = null;\n        }\n    }\n    Node firstTop;\n    Node secondTop;\n    \n    void push(T data){\n        Node temp = new Node(data);\n        temp.next = firstTop;\n        firstTop = temp;\n    }\n    \n    void pop(){\n        if(firstTop == null){\n            return;\n        }\n        Node temp = firstTop;\n        while(temp != null){\n            Node temp1 = new Node(temp.data);\n            temp1.next = secondTop;\n            secondTop = temp1;\n            temp = temp.next;\n        }\n        secondTop = secondTop.next;\n        firstTop = null;\n        while(secondTop != null){\n            Node temp3 = new Node(secondTop.data);\n            temp3.next = firstTop;\n            firstTop = temp3;\n            secondTop = secondTop.next;\n        }\n    }\n    \n}\n</code></pre>\n<p><strong>Note:</strong> In this case, pop operation is very time consuming. So I won\'t suggest to create a queue using two stacks.</p>\n'}, {'answer_id': 46724770, 'author': 'hIpPy', 'author_id': 58678, 'author_profile': 'https://Stackoverflow.com/users/58678', 'pm_score': 0, 'selected': False, 'text': '<p>With <code>O(1)</code> <code>dequeue()</code>, which is same as pythonquick\'s <a href="https://stackoverflow.com/a/77010/58678">answer</a>:</p>\n\n<pre><code>// time: O(n), space: O(n)\nenqueue(x):\n    if stack.isEmpty():\n        stack.push(x)\n        return\n    temp = stack.pop()\n    enqueue(x)\n    stack.push(temp)\n\n// time: O(1)\nx dequeue():\n    return stack.pop()\n</code></pre>\n\n<p>With <code>O(1)</code> <code>enqueue()</code> (this is not mentioned in this post so this answer), which also uses backtracking to bubble up and return the bottommost item.</p>\n\n<pre><code>// O(1)\nenqueue(x):\n    stack.push(x)\n\n// time: O(n), space: O(n)\nx dequeue():\n    temp = stack.pop()\n    if stack.isEmpty():\n        x = temp\n    else:\n        x = dequeue()\n        stack.push(temp)\n    return x\n</code></pre>\n\n<p>Obviously, it\'s a good coding exercise as it inefficient but elegant nevertheless.</p>\n'}, {'answer_id': 46796061, 'author': 'davejlin', 'author_id': 5464788, 'author_profile': 'https://Stackoverflow.com/users/5464788', 'pm_score': 1, 'selected': False, 'text': '<p>An implementation of a queue using two stacks in Swift:</p>\n\n<pre class="lang-swift prettyprint-override"><code>struct Stack&lt;Element&gt; {\n    var items = [Element]()\n\n    var count : Int {\n        return items.count\n    }\n\n    mutating func push(_ item: Element) {\n        items.append(item)\n    }\n\n    mutating func pop() -&gt; Element? {\n        return items.removeLast()\n    }\n\n    func peek() -&gt; Element? {\n        return items.last\n    }\n}\n\nstruct Queue&lt;Element&gt; {\n    var inStack = Stack&lt;Element&gt;()\n    var outStack = Stack&lt;Element&gt;()\n\n    mutating func enqueue(_ item: Element) {\n        inStack.push(item)\n    }\n\n    mutating func dequeue() -&gt; Element? {\n        fillOutStack() \n        return outStack.pop()\n    }\n\n    mutating func peek() -&gt; Element? {\n        fillOutStack()\n        return outStack.peek()\n    }\n\n    private mutating func fillOutStack() {\n        if outStack.count == 0 {\n            while inStack.count != 0 {\n                outStack.push(inStack.pop()!)\n            }\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 50548677, 'author': 'Radioactive', 'author_id': 5670939, 'author_profile': 'https://Stackoverflow.com/users/5670939', 'pm_score': 1, 'selected': False, 'text': '<p>While you will get a lot of posts related to implementing a queue with two stacks :\n1. Either by making the enQueue process a lot more costly\n2. Or by making the deQueue process a lot more costly</p>\n\n<p><a href="https://www.geeksforgeeks.org/queue-using-stacks/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/queue-using-stacks/</a></p>\n\n<p>One important way I found out from the above post was constructing queue with only stack data structure and the recursion call stack.</p>\n\n<p>While one can argue that literally this is still using two stacks, but then ideally this is using only one stack data structure.</p>\n\n<p>Below is the explanation of the problem:</p>\n\n<ol>\n<li><p>Declare a single stack for enQueuing and deQueing the data and push the data into the stack.</p></li>\n<li><p>while deQueueing have a base condition where the element of the stack is poped when the size of the stack is 1. This will ensure that there is no stack overflow during the deQueue recursion.</p></li>\n<li><p>While deQueueing first pop the data from the top of the stack. Ideally this element will be the element which is present at the top of the stack. Now once this is done, recursively call the deQueue function and then push the element popped above back into the stack.</p></li>\n</ol>\n\n<p>The code will look like below:</p>\n\n<pre><code>if (s1.isEmpty())\nSystem.out.println("The Queue is empty");\n        else if (s1.size() == 1)\n            return s1.pop();\n        else {\n            int x = s1.pop();\n            int result = deQueue();\n            s1.push(x);\n            return result;\n</code></pre>\n\n<p>This way you can create a queue using a single stack data structure and the recursion call stack.</p>\n'}, {'answer_id': 54274637, 'author': 'Jyoti Prasad Pal', 'author_id': 3173123, 'author_profile': 'https://Stackoverflow.com/users/3173123', 'pm_score': 1, 'selected': False, 'text': '<p>Below is the solution in javascript language using ES6 syntax.</p>\n\n<p><strong>Stack.js</strong></p>\n\n<pre><code>//stack using array\nclass Stack {\n  constructor() {\n    this.data = [];\n  }\n\n  push(data) {\n    this.data.push(data);\n  }\n\n  pop() {\n    return this.data.pop();\n  }\n\n  peek() {\n    return this.data[this.data.length - 1];\n  }\n\n  size(){\n    return this.data.length;\n  }\n}\n\nexport { Stack };\n</code></pre>\n\n<p><strong>QueueUsingTwoStacks.js</strong></p>\n\n<pre><code>import { Stack } from "./Stack";\n\nclass QueueUsingTwoStacks {\n  constructor() {\n    this.stack1 = new Stack();\n    this.stack2 = new Stack();\n  }\n\n  enqueue(data) {\n    this.stack1.push(data);\n  }\n\n  dequeue() {\n    //if both stacks are empty, return undefined\n    if (this.stack1.size() === 0 &amp;&amp; this.stack2.size() === 0)\n      return undefined;\n\n    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty\n    if (this.stack2.size() === 0) {\n      while (this.stack1.size() !== 0) {\n        this.stack2.push(this.stack1.pop());\n      }\n    }\n\n    //pop and return the element from stack 2\n    return this.stack2.pop();\n  }\n}\n\nexport { QueueUsingTwoStacks };\n</code></pre>\n\n<p>Below is the usage:</p>\n\n<p><strong>index.js</strong></p>\n\n<pre><code>import { StackUsingTwoQueues } from \'./StackUsingTwoQueues\';\n\nlet que = new QueueUsingTwoStacks();\nque.enqueue("A");\nque.enqueue("B");\nque.enqueue("C");\n\nconsole.log(que.dequeue());  //output: "A"\n</code></pre>\n'}, {'answer_id': 58008554, 'author': 'Girish Rathi', 'author_id': 9785149, 'author_profile': 'https://Stackoverflow.com/users/9785149', 'pm_score': 3, 'selected': False, 'text': '<p>Implement the following operations of a queue using stacks.</p>\n\n<p>push(x) -- Push element x to the back of queue.</p>\n\n<p>pop() -- Removes the element from in front of queue.</p>\n\n<p>peek() -- Get the front element.</p>\n\n<p>empty() -- Return whether the queue is empty.  </p>\n\n<p><a href="https://i.stack.imgur.com/LQJBQ.png" rel="noreferrer"><img src="https://i.stack.imgur.com/LQJBQ.png" alt="enter image description here"></a></p>\n\n<pre><code>class MyQueue {\n\n  Stack&lt;Integer&gt; input;\n  Stack&lt;Integer&gt; output;\n\n  /** Initialize your data structure here. */\n  public MyQueue() {\n    input = new Stack&lt;Integer&gt;();\n    output = new Stack&lt;Integer&gt;();\n  }\n\n  /** Push element x to the back of queue. */\n  public void push(int x) {\n    input.push(x);\n  }\n\n  /** Removes the element from in front of queue and returns that element. */\n  public int pop() {\n    peek();\n    return output.pop();\n  }\n\n  /** Get the front element. */\n  public int peek() {\n    if(output.isEmpty()) {\n        while(!input.isEmpty()) {\n            output.push(input.pop());\n        }\n    }\n    return output.peek();\n  }\n\n  /** Returns whether the queue is empty. */\n  public boolean empty() {\n    return input.isEmpty() &amp;&amp; output.isEmpty();\n  }\n}\n</code></pre>\n'}, {'answer_id': 62305888, 'author': 'ASHISH R', 'author_id': 4259659, 'author_profile': 'https://Stackoverflow.com/users/4259659', 'pm_score': 1, 'selected': False, 'text': '<p>**Easy JS solution **</p>\n\n<ul>\n<li>Note: I took ideas from other people comment </li>\n</ul>\n\n<p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">\r\n<div class="snippet-code">\r\n<pre class="snippet-code-js lang-js prettyprint-override"><code>/*\r\n\r\nenQueue(q,  x)\r\n 1) Push x to stack1 (assuming size of stacks is unlimited).\r\n\r\ndeQueue(q)\r\n 1) If both stacks are empty then error.\r\n 2) If stack2 is empty\r\n   While stack1 is not empty, push everything from stack1 to stack2.\r\n 3) Pop the element from stack2 and return it.\r\n\r\n*/\r\nclass myQueue {\r\n    constructor() {\r\n        this.stack1 = [];\r\n        this.stack2 = [];\r\n    }\r\n\r\n    push(item) {\r\n        this.stack1.push(item)\r\n    }\r\n\r\n    remove() {\r\n        if (this.stack1.length == 0 &amp;&amp; this.stack2.length == 0) {\r\n            return "Stack are empty"\r\n        }\r\n\r\n        if (this.stack2.length == 0) {\r\n\r\n            while (this.stack1.length != 0) {\r\n                this.stack2.push(this.stack1.pop())\r\n            }\r\n        }\r\n        return this.stack2.pop()\r\n    }\r\n\r\n\r\n    peek() {\r\n        if (this.stack2.length == 0 &amp;&amp; this.stack1.length == 0) {\r\n            return \'Empty list\'\r\n        }\r\n\r\n        if (this.stack2.length == 0) {\r\n            while (this.stack1.length != 0) {\r\n                this.stack2.push(this.stack1.pop())\r\n            }\r\n        }\r\n\r\n        return this.stack2[0]\r\n    }\r\n\r\n    isEmpty() {\r\n        return this.stack2.length === 0 &amp;&amp; this.stack1.length === 0;\r\n    }\r\n\r\n}\r\n\r\nconst q = new myQueue();\r\nq.push(1);\r\nq.push(2);\r\nq.push(3);\r\nq.remove()\r\n\r\nconsole.log(q)</code></pre>\r\n</div>\r\n</div>\r\n</p>\n'}, {'answer_id': 67205990, 'author': 'Sarang', 'author_id': 1278758, 'author_profile': 'https://Stackoverflow.com/users/1278758', 'pm_score': 0, 'selected': False, 'text': '<p>My Solution with PHP</p>\n<pre><code>&lt;?php\n$_fp = fopen(&quot;php://stdin&quot;, &quot;r&quot;);\n/* Enter your code here. Read input from STDIN. Print output to STDOUT */\n    $queue = array();\n    $count = 0;\n    while($line = fgets($_fp)) {\n        if($count == 0) {\n            $noOfElement = $line;\n            $count++;\n            continue;\n        }\n        $action = explode(&quot; &quot;,$line);\n        $case = $action[0];\n        switch($case) {\n            case 1:\n                $enqueueValue = $action[1];\n                array_push($queue, $enqueueValue);\n                break;\n            case 2:\n                array_shift($queue);\n                break;\n            case 3:\n                $show = reset($queue);\n                print_r($show);\n                break;\n            default:\n                break;\n        }\n    }\n?&gt;\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/69192', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/7086/']