How to implement a Queue data structure using Stack?
We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.
To quickly refresh Stacks, and Queues knowledge;
Stacks are the LIFO (LastInFirstOut) list in which the last element inserted is the first to be removed.(Example: stack of plates kept in a cafeteria)
Queue is a FIFO ( FirstInFirstOut) list in which the first element inserted is the first to be removed (Example: Line of people waiting for a ticket at any counter)
The trick here is to use two stacks, one for adding the data(pushstack), and one for removing the data(popstack). So we have to implement enqueue() and dequeue() operations in terms of only stack methods.
enqueue():
First check if the popstack is empty. If it is empty, we directly push the element onto the pushstack.
Otherwise We pop all the elements from the popstack onebyone and push them onto the pushstack. Then we push the current element.
dequeue():
First check if the pushstack is empty. If it is empty, we directly pop the element from the popstack.
Otherwise we pop all the element from the pushstack onebyone and push them onto the popstack.
Then we pop the element from the popstack and return that.
Let us understand this logic with an example. Let us represent the stacks from left to right assuming that the rightmost element is top.
The following table explains a series of enqueue() and dequeue() operations and the status of push and popstacks.
Observe that order of the removed elements. They are in the order of insertion. Performing a series of only enqueue/dequeue operations does not cause any performance problems, as it does not require the elements to be copied between the two stacks.
At any point of time, only one stack is occupied
The worst case occurs when enqueue, and dequeue operations are performed alternatively.
*Abstract Data type: A specification which gives the methods that should be supported by a data structure.
Following is the implementation in Java. I have omitted some exception handling to keep the code simple and clear.
We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.
To quickly refresh Stacks, and Queues knowledge;
Stacks are the LIFO (LastInFirstOut) list in which the last element inserted is the first to be removed.(Example: stack of plates kept in a cafeteria)
Queue is a FIFO ( FirstInFirstOut) list in which the first element inserted is the first to be removed (Example: Line of people waiting for a ticket at any counter)
The trick here is to use two stacks, one for adding the data(pushstack), and one for removing the data(popstack). So we have to implement enqueue() and dequeue() operations in terms of only stack methods.
enqueue():
First check if the popstack is empty. If it is empty, we directly push the element onto the pushstack.
Otherwise We pop all the elements from the popstack onebyone and push them onto the pushstack. Then we push the current element.
dequeue():
First check if the pushstack is empty. If it is empty, we directly pop the element from the popstack.
Otherwise we pop all the element from the pushstack onebyone and push them onto the popstack.
Then we pop the element from the popstack and return that.
Let us understand this logic with an example. Let us represent the stacks from left to right assuming that the rightmost element is top.
The following table explains a series of enqueue() and dequeue() operations and the status of push and popstacks.
Operation

Pushstack

Popstack

Comment

Enqueue(1)

1

1 added to pushstack


Enqueue(2)

1, 2

2 added to pushstack


Dequeue()

2

1 removed from queue


Enqueue(3)

2, 3

3 added to pushstack


Enqueue(4)

2, 3, 4

4 added to pushstack


Dequeue()

4, 3

2 removed from queue


Enqueue(5)

3, 4, 5

5 added to pushstack


Dequeue()

5, 4

3 removed from queue

Observe that order of the removed elements. They are in the order of insertion. Performing a series of only enqueue/dequeue operations does not cause any performance problems, as it does not require the elements to be copied between the two stacks.
At any point of time, only one stack is occupied
The worst case occurs when enqueue, and dequeue operations are performed alternatively.
*Abstract Data type: A specification which gives the methods that should be supported by a data structure.
Following is the implementation in Java. I have omitted some exception handling to keep the code simple and clear.
/** * Created with IntelliJ IDEA. * User: Ravi * Date: 8/23/13 * Time: 1:20 PM * To change this template use File  Settings  File Templates. */ import java.util.Stack; public class Main { public static void main(String[] args) { Q2Stacks intQueue = new Q2Stacks(); intQueue.enqueue(1); intQueue.enqueue(2); System.out.println(intQueue.dequeue()); intQueue.enqueue(3); System.out.println(intQueue.dequeue()); intQueue.enqueue(4); intQueue.enqueue(5); System.out.println(intQueue.dequeue()); intQueue.enqueue(6); System.out.println(intQueue.dequeue()); System.out.println(intQueue.dequeue()); System.out.println(intQueue.dequeue()); } static class Q2Stacks { private Stack<Integer> pushStack; private Stack<Integer> popStack; public Q2Stacks() { pushStack = new Stack<Integer>(); popStack = new Stack<Integer>(); } public void enqueue(int data) { if( !popStack.empty() ) { while( !popStack.empty()) { pushStack.push(popStack.pop()); } } pushStack.push(data); } public int dequeue() { if( !pushStack.empty() ) { while( !pushStack.empty() ) { popStack.push( pushStack.pop() ); } } return popStack.pop(); } } }