implementing queue using stack

 implementation of queue can be done using two stacks. Queue using stack can be done in two ways.

*By making the enqueue (insertion) operation costly.

*By making the dequeue (deletion) operation costly.

 

Queue using stacks by making enqueue operation costly:

1)Initialize stack1 and stack2 making top1 = top2 = -1.

2)To perform an enqueue operation,   time complexity will be O(n)

           While stack1 is not empty, Push all the elements from stack1 to stack2.

           Push the new element to stack2.

           Pop all the elements from stack2 to stack1.

3) To perform dequeue operation,          time complexity will be O(1)

          Pop and return the element from stack1.


c++:

// CPP program to implement Queue using
// two stacks with costly enQueue()
#include <bits/stdc++.h>
using namespace std;

struct Queue {
    stack<int> s1, s2;

    void enQueue(int x)
    {
        // Move all elements from s1 to s2
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        // Push item into s1
        s1.push(x);

        // Push everything back to s1
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }

    // Dequeue an item from the queue
    int deQueue()
    {
        // if first stack is empty
        if (s1.empty()) {
            cout << "Q is Empty";
            exit(0);
        }

        // Return top of s1
        int x = s1.top();
        s1.pop();
        return x;
    }
};

// Driver code
int main()
{
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);

    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';

    return 0;
}

java:


// Java program to implement Queue using 
// two stacks with costly enQueue() 
import java.util.*;

class awe
{ 
static class Queue 
{ 
    static Stack<Integer> s1 = new Stack<Integer>(); 
    static Stack<Integer> s2 = new Stack<Integer>(); 

    static void enQueue(int x) 
    { 
        // Move all elements from s1 to s2 
        while (!s1.isEmpty())
        { 
            s2.push(s1.pop()); 
            //s1.pop(); 
        } 

        // Push item into s1 
        s1.push(x); 

        // Push everything back to s1 
        while (!s2.isEmpty()) 
        { 
            s1.push(s2.pop()); 
            //s2.pop(); 
        } 
    } 

    // Dequeue an item from the queue 
    static int deQueue() 
    { 
        // if first stack is empty 
        if (s1.isEmpty()) 
        { 
            System.out.println("Q is Empty"); 
            System.exit(0); 
        } 

        // Return top of s1 
        int x = s1.peek(); 
        s1.pop(); 
        return x; 
    } 
}; 

// Driver code 
public static void main(String[] args) 
{ 
    Queue q = new Queue(); 
    q.enQueue(1); 
    q.enQueue(2); 
    q.enQueue(3); 

    System.out.println(q.deQueue()); 
    System.out.println(q.deQueue());
    System.out.println(q.deQueue());
} 
} 
output:
1 2 3 


Queue using stacks by making dequeue operation costly

1)Initialize stack1 and stack2 making top1 = top2 = -1.

2)To perform an enqueue operation,                   time complexity will be O(1)

       Push the element to be added to stack1.

3) To perform dequeue operation,

       If stack2 is empty While stack1 is not empty ,Push all the elements from stack1 to stack2.

       Pop and return the element from the stack2.            time complexity will be O(n)


Method 2 is better in performance than method 1. As Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 is empty.

c++:

// CPP program to implement Queue using
// two stacks with costly deQueue()
#include <bits/stdc++.h>
using namespace std;

struct Queue {
    stack<int> s1, s2;

    // Enqueue an item to the queue
    void enQueue(int x)
    {
        // Push item into the first stack
        s1.push(x);
    }

    // Dequeue an item from the queue
    int deQueue()
    {
        // if both stacks are empty
        if (s1.empty() && s2.empty()) {
            cout << "Q is empty";
            exit(0);
        }

        // if s2 is empty, move
        // elements from s1
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }

        // return the top item from s2
        int x = s2.top();
        s2.pop();
        return x;
    }
};

// Driver code
int main()
{
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);

    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';
    cout << q.deQueue() << '\n';

    return 0;
}
java:

// Java Program to implement a queue using two stacks 

// Note that Stack class is used for Stack implementation

import java.util.Stack;

public class awe {
    /* class of queue having two stacks */
    static class Queue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
    }

    /* Function to push an item to stack*/
    static void push(Stack<Integer> top_ref, int new_data)
    {
        // Push the data onto the stack
        top_ref.push(new_data);
    }

    /* Function to pop an item from stack*/
    static int pop(Stack<Integer> top_ref)
    {
        /*If stack is empty then error */
        if (top_ref.isEmpty()) {
            System.out.println("Stack Underflow");
            System.exit(0);
        }

        // pop the data from the stack
        return top_ref.pop();
    }

    // Function to enqueue an item to the queue
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }

    /* Function to deQueue an item from queue */
    static int deQueue(Queue q)
    {
        int x;

        /* If both stacks are empty then error */
        if (q.stack1.isEmpty() && q.stack2.isEmpty()) {
            System.out.println("Q is empty");
            System.exit(0);
        }

        /* Move elements from stack1 to stack 2 only if
        stack2 is empty */
        if (q.stack2.isEmpty()) {
            while (!q.stack1.isEmpty()) {
                x = pop(q.stack1);
                push(q.stack2, x);
            }
        }
        x = pop(q.stack2);
        return x;
    }

    /* Driver function to test above functions */
    public static void main(String args[])
    {
        /* Create a queue with items 1 2 3*/
        Queue q = new Queue();
        q.stack1 = new Stack<>();
        q.stack2 = new Stack<>();
        enQueue(q, 1);
        enQueue(q, 2);
        enQueue(q, 3);

        /* Dequeue items */
        System.out.print(deQueue(q) + " ");
        System.out.print(deQueue(q) + " ");
        System.out.println(deQueue(q) + " ");
    }
}
output:
1 2 3 






 

darkmode