How to implement a queue using two stacks. In this tutorial, I am going to discuss how to implement a first in first out (FIFO) queue using only two stacks.
In this problem, we are going to implement following methods of QueueUsingStack class:
void push(int x) – Insert an element x.
int pop() – Removes the element (In FIFO order).
int peek() – Returns the element which is present at the front of the queue.
boolean empty() – Returns true if no element is present else false.
For example –
|
1 2 3 4 5 6 |
QueueUsingStack qu = new QueueUsingStack(); qu.push(5); // Element in queue is : [5] qu.push(4); // elements are : [5, 4] qu.peek(); // return 5 qu.pop(); // return 5, queue is [4] qu.empty(); // return false |
Before solving this problem let’s first understand the difference between queue and stack data structure.
Queue
Queue is a First-In, First-Out (FIFO) data structure. The element which we enqueued first is the first element to be dequeued.
In queue, inserting an element is called as enqueue and deleting an element is called as dequeue. Insertion happens at one end called rear and deletion happens at other end called front.
Programming questions on queue
Stack
Stack is a Last-In, First-Out (LIFO) data structure. The element which we pushed at last is the first element to be popped out.
Inserting an element in a stack is called as push and deleting an element is called as pop.
Programming questions on stack
Programming video tutorials on stack
Java program to check for balanced parentheses using stack
Implement Queue using Two Stacks – Java Code
Let’s discuss how we can impelement a queue using two stacks and write it’s java code.
The idea here is to push the element in a first stack. When the pop operation is called pop the element from second stack. If second stack is empty and first stack is not empty then pop all the elements from first stack and push them in a second stack.
It ensures that whenever we pop from the second stack, we get the element which is inserted first (FIFO order).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
/** * Java Code to implement a queue using two stacks */ class QueueUsingTwoStacks { Stack<Integer> st1; Stack<Integer> st2; private int front; public QueueUsingTwoStacks() { st1 = new Stack<>(); st2 = new Stack<>(); } //Push the element in first stack public void push(int x) { st1.push(x); } /* Pop the element from second stack, If second stack is empty and first stack is not empty then pop all the elements from first stack and push them in a second stack. */ public int pop() { shiftStackElement(); return st2.pop(); } public int peek() { shiftStackElement(); return st2.peek(); } public boolean empty() { return st1.isEmpty() && st2.isEmpty(); } private void shiftStackElement() { if(st2.isEmpty() && !st1.isEmpty()) { while(!st1.isEmpty()) { st2.push(st1.pop()); } } } public static void main(String[] args) { QueueUsingTwoStacks qu = new QueueUsingTwoStacks(); qu.push(3); qu.push(4); qu.peek(); qu.pop(); qu.empty(); } } |
