Queue

Write a program to implement the queue using two stacks

Pinterest LinkedIn Tumblr

A queue can be implemented using two stacks. The queue supports enqueue and dequeue operations using head and tail nodes.

Write a program to implement the queue using two stacks.

Queue Stack

Algorithm Explanation

Enqueue operation retrieve the element from queue.
If the stack1 is empty, push everything from stack1 to stack2. Push the element to stack1 and push everything from stack1.
Dequeue operation remove the element from queue.
If stack2 is empty, move the stack1 element to stack2. Pop the element from stock2.
Display check empty in stack1 and stack2. If stack1 is not empty, display element from stack1. If stack2 is not empty, display element from stack2.

Source Code

package com.dsacode.DataStructre.queue;
 
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Stack;
 
public class queueUsingStack < Item >{
     
    private Stack < Item > stack1 = null;   
    private Stack < Item > stack2 = null;   
     
    public queueUsingStack() {
        stack1 = new Stack < Item >();
        stack2 = new Stack < Item >();
    }
     
    private void moveStack1ToStack2() {
        while (!stack1.isEmpty())
            stack2.push(stack1.pop());
    }
     
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
 
    public int size() {
        return stack1.size() + stack2.size();    
    }
     
    public Item peek() {
        if (isEmpty())
            throw new NoSuchElementException("Queue underflow");
         
        if (stack2.isEmpty())
            moveStack1ToStack2();
        return stack2.peek();
    }
     
    public void enqueue(Item item) {
        stack1.push(item);
    }
     
    public void display(){
            if(!stack1.isEmpty())
                System.out.println(Arrays.toString(stack1.toArray()));
          
            if(!stack2.isEmpty())
                System.out.println(Arrays.toString(stack2.toArray()));
    }
     
    public Item dequeue() {
        if (isEmpty())
            throw new NoSuchElementException("Queue underflow");
         
        if (stack2.isEmpty())
            moveStack1ToStack2();
         
        return stack2.pop();
    }
 
 
public static void main(String[] args) {
         
        queueUsingStack < String > q = new queueUsingStack < String >();
        String[] array={"hello","kid","test"};
 
        System.out.println("Enqueue itmes to the queue: "+ Arrays.toString(array));
        for( String str : array)
            q.enqueue(str);
 
        System.out.println("Size of the Queue: " + q.size() );
        System.out.print("Items in the Queue: ");
        q.display();
 
         
        System.out.println("Dequeue itme from queue: "+ q.dequeue());
        System.out.println("Dequeue itme from queue: "+ q.dequeue() );
         
        System.out.print("Items in the Queue: ");
        q.display();
    }
}

Output

Enqueue itmes to the queue: [hello, kid, test]
Size of the Queue: 3
Items in the Queue: [hello, kid, test]
Dequeue itme from queue: hello
Dequeue itme from queue: kid
Items in the Queue: [test]

Write A Comment