Code Destine

Problem Statement

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

1. push(N) :- It insert element N onto the top of the stack.
2. pop() :- It removes and returns the element from the top of the stack.
3. peek() :- It returns (not remove) the element from the top of the stack.
4. empty() :- It checks whether the stack is empty.

Note: Only standard operations of a queue are allowed like enqueue an element to back of a queue, dequeue or peek an element from the front of a queue and, empty operation.

Example 

MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30); 
stack.peek();   // returns 30
stack.pop();   // returns 30
stack.empty(); // returns false

Solution

Two Queue (backed by linked list) data structure can be used to implement a Stack data structure. Implementation can be done in two different ways:

Push in O(1) And Pop & Peek in O(n) :

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

1. push(N) :- It enqueue an element N to the back of queue A
2. pop() :- If queue A is empty, then it dequeue n-1 (n is the size of queue B) elements from queue B and enqueue them to queue A and return the last element of queue B. If queue A is not empty, then it dequeue n-1 elements from queue A and enqueue them to queue B and returns the last element of queue A
3. peek() :- If queue A is empty, then it dequeue all (save last element in temporary variable) elements from queue B and enqueue them to queue A and return the last element of queue B. If queue A is not empty, then it dequeue all elements from queue A and enqueue them to queue B and returns the last element of queue A.
4. empty() :- It returns true if queue A and B are empty otherwise, it returns false.

Program

import java.util.LinkedList;
import java.util.Queue;

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

	public Queue<Integer> queueA = null;
    public Queue<Integer> queueB = null;
    
    public MyStack() {
        this.queueA = new LinkedList<>();
        this.queueB = new LinkedList<>();
    }
    
    public void push(int x) {
        queueA.add(x);
    }
    
    public int pop() {
        if(queueA.size() == 0){
            while(queueB.size() >1){
                queueA.add(queueB.poll());
            }
            return queueB.poll();
        }else {
            while(queueA.size() >1){
                queueB.add(queueA.poll());
            }
            return queueA.poll();
        }        
    }
    
    public int peek() {
        if(queueA.size() == 0){
            while(queueB.size() >1){
                queueA.add(queueB.poll());
            }
            int value = queueB.peek();
            queueA.add(queueB.poll());
            return value;
        }else {
            while(queueA.size() >1){
                queueB.add(queueA.poll());
            }
            int value = queueA.peek();
            queueB.add(queueA.poll());
            return value;
        } 
    }
    
    public boolean empty() {
        return (this.queueA.size() == 0 && this.queueB.size() == 0);
    }	
}

Push in O(n) And Pop & Peek in O(1) :

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

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

Program

import java.util.LinkedList;
import java.util.Queue;

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

	public Queue<Integer> queueA = null;
    public Queue<Integer> queueB = null;
    
    public MyStack() {
        this.queueA = new LinkedList<>();
        this.queueB = new LinkedList<>();
    }
    
    public void push(int x) {
        if(queueA.size() == 0){
            queueA.add(x);
            while(queueB.size() >0){
                queueA.add(queueB.poll());
            }
        }else {
            queueB.add(x);
            while(queueA.size() >0){
                queueB.add(queueA.poll());
            }
        }
    }
    
    public int pop() {
        if(queueB.size() == 0){
            return queueA.poll();
        } else {
            return queueB.poll();
        }
    }
    
    public int peek() {
        if(queueB.size() == 0){
            return queueA.peek();
        } else {
            return queueB.peek();
        }
    }
    
    public boolean empty() {
        return (this.queueA.size() == 0 && this.queueB.size() == 0);
    }	
}

Result

Peek: 30
Pop: 30

Similar Post

1. Implement Queue using Stacks
2. Design Stack using Linked List
3. Design Queue using Linked List

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