implementing stack using queue

We need to implement a Stack data structure and only queue operations allowed on the instances


By making push operation costly: 

push(s, x) // x is the element to be pushed and s is stack

  1) Enqueue x to q2

  2) One by one dequeue everything from q1 and enqueue to q2.

  3) Swap the names of q1 and q2 

// Swapping of names is done to avoid one more  

// movement of all elements from q2 to q1. 


pop(s)

  1) Dequeue an item from q1 and return it.


c++:

    // Two inbuilt queues
    queue<int> q1, q2;
    
    // Function to implement push() operation
    void push(int x)
    {
        // Push x first in empty q2
        q2.push(x);

        // Push all the remaining 
        // elements in q1 to q2. 
        while (!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }

        // swap the names of two queues
        queue<int> q = q1;
        q1 = q2;
        q2 = q;
    }

    // Function to implement pop() operation
    void pop(){

        // if no elements are there in q1 
        if (q1.empty())
            return ;
        q1.pop();
    }

java:


// Java Program to implement a stack using 
// two queue 
import java.util.*;

class awe
{

    static class Stack 
    { 
        // Two inbuilt queues 
        static Queue<Integer> q1 = new LinkedList<Integer>();
        static Queue<Integer> q2 = new LinkedList<Integer>(); 
        
        // Method to implement push() operation
        static void push(int x) 
        {     
            // Push x first in empty q2 
            q2.add(x); 
    
            // Push all the remaining 
            // elements in q1 to q2. 
            while (!q1.isEmpty()) 
            { 
                q2.add(q1.peek()); 
                q1.remove(); 
            } 
    
            // swap the names of two queues 
            Queue<Integer> q = q1; 
            q1 = q2; 
            q2 = q; 
        } 
    
        // Method to implement pop() operation
        static void pop(){ 
    
            // if no elements are there in q1 
            if (q1.isEmpty()) 
                return ; 
                
            q1.remove(); 
        } 
    }; 
    
} 




By making pop operation costly: 

push(s,  x)

  1) Enqueue x to q1 (assuming size of q1 is unlimited).


pop(s)  

  1) One by one dequeue everything except the last element 

     from q1 and enqueue to q2.

  2) Dequeue the last item of q1, the dequeued item 

     is the result, store it.

  3) Swap the names of q1 and q2

  4) Return the item stored in step 2.

// Swapping of names is done to avoid one more

// movement of all elements from q2 to q1.

c++:

    queue<int> q1, q2;    //inbuild two queues

    void pop()
    {
        if (q1.empty())
            return;

        // Leave one element in q1 and 
        // push others in q2.
        while (q1.size() != 1)
        {
            q2.push(q1.front());
            q1.pop();
        }

        // Pop the only left element 
        // from q1
        q1.pop();

        // swap the names of two queues
        queue<int> q = q1;
        q1 = q2;
        q2 = q;
    }

    void push(int x)
    {
        q1.push(x);
    }
 

java:

/* Java Program to implement a stack  
using two queue */
import java.util.*; 
  
class Stack { 
    Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>(); 
   
    void pop() 
    { 
        if (q1.isEmpty()) 
            return; 
  
        // Leave one element in q1 and 
        // push others in q2. 
        while (q1.size() != 1) { 
            q2.add(q1.peek()); 
            q1.remove(); 
        } 
  
        // Pop the only left element 
        // from q1 
        q1.remove(); 
     
        // swap the names of two queues 
        Queue<Integer> q = q1; 
        q1 = q2; 
        q2 = q; 
    } 
  
    void push(int x) 
    { 
        q1.add(x); 
        
    } 
  
} 
  






darkmode