# How to implement a queue using stack?

A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the 2 stacks for implementing q. We know that stack supports push, pop, peek operations and using these operations, we need to emulate the operations of queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)):

By making enqueue operation costly:
Here, the oldest element is always at the top of stack1 which ensures dequeue operation to occur in O(1) time complexity.
To place element at top of stack1, stack2 is used.

``````    Pseudocode:
Enqueue: Here time complexity will be O(n)

enqueue(q, data):
While stack1 is not empty:
Push everything from stack1 to stack2.
Push data to stack1
Push everything back to stack1.

Dequeue: Here time complexity will be O(1)

deQueue(q):
If stack1 is empty then error
else
Pop an item from stack1 and return it
``````

By making dequeue operation costly:
Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the enqueue operation time complexity is O(1).
In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top of stack2 is the result. Basically, reversing the list by pushing to a stack and returning the first enqueued element. This operation of pushing all elements to new stack takes O(n) complexity.
Pseudocode:
Enqueue: Time complexity: O(1)

``````        enqueue(q, data):
Push data to stack1

Dequeue: Time complexity: O(n)

dequeue(q):
If both stacks are empty then raise error.
If stack2 is empty:
While stack1 is not empty:
push everything from stack1 to stack2.
Pop the element from stack2 and return it.``````

You can implement queue by different ways using stacks.

By making enQueue process costly

``````void enQueue(int x)
{

while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}

s1.push(x);

while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}``````