Code Destine

Problem Statement

Design a Queue (FIFO) data structure using Stack (LIFO). The Queue data structure will supports the following operations:

1. enqueue(N) :- It insert element N to the back of the queue.
2. dequeue() :- It removes and returns the element from the front of the queue.
3. peek() :- It returns (not remove) the element from the front of the queue.
4. empty() :- It checks whether the queue is empty.

Note: Only standard operations of a stack are allowed like push an element to top of the stack, pop or peek an element from the top of a stack and, empty operation.

Example 

MyQueue queue = new MyQueue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);  
queue.peek();  // returns 10
queue.dequeue();   // returns 10
queue.empty(); // returns false

Solution

Two Stack data structure can be used to implement a Queue data structure. Implementation can be done in two different ways:

Enqueue in O(1) And Dequeue & Peek in O(n) :

Each operation of the queue will work in the following way:

1. enqueue(N) :- It push an element N on the top of the stack A
2. dequeue() :- If stack A is empty, then it pop all elements from stack B and push them to stack A and remove and return (pop) the top element from stack A. Otherwise if stack B is empty, then it pop all elements from stack A and push them to stack B and remove and return (pop) the top element from stack B.
3. peek() :- If stack A is empty, then it pop all elements from stack B and push them to stack A and return (peek) the top element from stack A. Otherwise if stack B is empty, then it pop all elements from stack A and push them to stack B and return (peek) the top element from stack B.
4. empty() :- It returns true if stack A and B are empty otherwise, it returns false.

Program

import java.util.Stack;

public class MyQueue {
	
	public static void main(String[] args) {		
		MyQueue queue = new MyQueue();		
		queue.push(10);
		queue.push(20);
		queue.push(30);
		System.out.println("Peek: " + queue.peek());
		System.out.println("Pop: " + queue.pop());							
	}

	private Stack<Integer> stackA = null;
    private Stack<Integer> stackB = null;

    public MyQueue() {
        this.stackA = new Stack<>();
        this.stackB = new Stack<>();
    }
    
    public void push(int x) {
        stackA.push(x);
    }
    
    public int pop() {
        if(stackB.size() == 0){
            while(stackA.size() > 0){
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }
    
    public int peek() {
        if(stackB.size() == 0){
            while(stackA.size() > 0){
                stackB.push(stackA.pop());
            }
        }
        return stackB.peek();
    }
    
    public boolean empty() {
        return (stackA.size() == 0 && stackB.size() == 0);
    }	
}

Enqueue in O(n) And Dequeue & Peek in O(1) :

Each operation of the queue will work in the following way:

1. enqueue(N) :- It pop and push all elements of stack A into stack B, then push an element N on the top of the stack A. In the end, it pop and push all elements of stack B into stack A
2. dequeue() :- It removes and return the top element of stack A
3. peek() :- It returns the top element of stack A
4. empty() :- It returns true if stack A is empty otherwise, it returns false.

Program

import java.util.Stack;

public class MyQueue {
	
	public static void main(String[] args) {		
		MyQueue queue = new MyQueue();		
		queue.push(10);
		queue.push(20);
		queue.push(30);
		System.out.println("Peek: " + queue.peek());
		System.out.println("Pop: " + queue.pop());							
	}

	private Stack<Integer> stackA = null;
    private Stack<Integer> stackB = null;
    
    public MyQueue() {
        this.stackA = new Stack<>();
        this.stackB = new Stack<>();
    }
    
    public void push(int x) {        
        while(stackA.size() > 0){
            stackB.push(stackA.pop());
        }
        stackA.push(x);
        while(stackB.size() > 0){
            stackA.push(stackB.pop());
        }
    }
    
    public int pop() {
        return stackA.pop();
    }
    
    public int peek() {
        return stackA.peek();
    }
    
    public boolean empty() {
        return stackA.size() == 0;
    }
}

Result

Peek: 10
Pop: 10

Similar Post

1. Design Stack using Linked List
2. Design Queue using Linked List
3. Design Stack using Dynamic Array

That’s all for Implement Queue using Stacks in Java, If you liked it, please share your thoughts in a comments section and share it with others too.