Stack via Queues

Stack via Queues

Implementing stack using queue

·

4 min read

A little introduction to Stack and Queue:

Stacks – Support retrieval by last-in, first-out (LIFO) order. Stacks are simple to implement and very efficient. The put and get operations for stacks are usually called push and pop Queues – Support retrieval in first-in, first-out (FIFO) order. This is surely the fairest way to control waiting times for services. The put and get operations for queues are usually called enqueue and dequeue.

1_w2zgPM-PJoRWFWJG2GrSaQ.png

Now our problem Statement is to implement a Stack data structure using only instances of Queue and queue operations allowed on the instances.

This is can be achieved in two ways either by making one of the operations of queue costlier(O(n)) In both methods, we use two queues to implement the stack operations, let us assume the two queues as queue1 and queue2.

queue<int> queue1,queue2;
  1. Making Push operation of stack costlier, in this method the newly entered element will always be at the front of queue1 .so that the pop operation takes constant time O(1). But for the push operation, we take the help of queue2 to make sure that every element is at the front of queue1, this usually takes linear time O(n) (Costlier). To achieve it we Firstly enqueue the element to be pushed into the stack to queue2 and dequeue the elements one by one from queue1 to queue2 until queue1 becomes empty. After the movement of all the elements from queue1 to queue2, the Swapping of names is done to avoid one more movement of all elements from queue2 to queue1.
void push(int x) 
    { 
        // Push x first in empty queue2 
        queue2.push(x); 
        // Push all the remaining elements in queue1 to queue2. 
        while (!queue1.empty()) { 
            queue2.push(queue1.front()); 
            queue1.pop(); 
        } 
      // swap the names of two queues 
        queue<int> q = queue1; 
        queue1 = queue2; 
        queue2 = q; 
    }

As pop operation involves in dequeue an element from queue1 and returns it.

  void pop() 
    { 
        if (queue1.empty()) 
            return; 
        queue1.pop(); 
    }

150.png

2.Making pop operation of stack costlier, in this method in push operation always the new element is enqueued to queue1. But in pop operation we one by one dequeue everything except the last element from queue1 and enqueue to queue2.To get the poped element dequeue the last item of queue1.

void pop() 
    { 
        if (queue1.empty()) 
             {
              cout<<"stack Underflow";
              return ;
              } 

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

        // Pop the only left element 
        // from queue1 
        int popedele=q1.pop();
        cout<<"The poped element is"<<popedele; 
        // swap the names of two queues 
        queue<int> q = queue1; 
        queue1 = queue2; 
        queue2 = q; 
    }

Push operation involves in enqueue an element to queue1 in constant time.

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

keep learning and sharing

Do leave your feedback and suggestions👀.