Implementing Stack using queues in two ways

Reading time: 30 minutes

Definition

A stack is based on the principle of Last-in-First-Out(LIFO). It is commonly used abstract data type with two major operations, namely pop and push. Push() and pop() are carried out in the topmost element, which is the item most recently added to the stack. The Push operation adds an element to the stack while the pop operatiion removes an element from the top position.

Basic Operations

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations-

• push() - Pushing (storing) an element on the stack.
• pop() - Removing (accessing) an element from the stack.

To check the status of the stack we will use following functions-

• peek() - get the top data element of the stack , without removing it.
• isFull() - check if stack is full.
• isEmpty() - check if stack is empty.

Implementation Details

• In this article we will be using queue data structure for storing the data.
• We are given a queue data structure with enqueue and dequeue operations, the task is to implement a stack using instances of queue data structure and operations on them. Since we are implementing stack data structure using queues, we will have to consider the natural behaviour of queues too, which is Last In First Out.
  For performing push we require only one stack as we can directly enqueue data into queue, but to perform pop we will require two Queues, because we need to follow stack's LIFO property and if we directlt dequeue any data element out of queue, it will follow FIFO approach.

Implementation

A stack can be implemented using two queues. Let stack to be implemented be s and queues used to implement s be queue1 and queue2. s can be implemented in two ways:

Method 1 (By making push operation costly)

In this method we will make sure that the newly entered element is always at the front of queue and so on.

To achieve this, we will need two stacks. Following steps will be involved while pushing a new element to the stack.

NOTE: First queue(q1) is the main queue being used to store the data, while the second queue(q2) is to assist and store data temporarily during various operations.

Pseudocode for push:

push(s,x)

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

Pseudocode for pop:

pop(s)

1. If queue1 is empty then error
2. Dequeue an item from q1 and return it.

Implementation of Method-1 (using C++ alongwith stl)

#include <bits/stdc++.h> 
using namespace std;
class Stack 
{  
    // Two inbuilt queues 
    queue<int> q1, q2;
    public: 
    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; 
    } 
    void pop()
    { 
        if (q1.empty())  return ; 
        q1.pop(); 
    } 
    int top() 
    { 
        if (q1.empty())  return -1; 
        return q1.front(); 
    } 
 }; 
int main() 
{ 
    Stack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    cout<<s.top()<<"\n"; 
    s.pop(); 
    cout <<s.top()<<"\n"; 
    s.pop(); 
    cout <<s.top()<<"\n"; 
    return 0; 
} 

Method 2 (By making pop operation costly)

In this method, in push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.

Pseudocode for push:

push(s, x)

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

Pseudocode for pop:

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 result, store it.
3. Swap the names of q1 and q2.
4. Return the item stored in step2.

Implementation of method-2 (using C++ along with stl)

#include<bits/stdc++.h> 
using namespace std;
class Stack 
{ 
    queue<int> q1, q2; 
    int curr_size; 
    public: 
    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);
    } 
    int top() 
    { 
        if (q1.empty()) 
            return -1; 
        while( q1.size() != 1 ) 
        { 
           q2.push(q1.front()); 
           q1.pop(); 
        }  
        // last pushed element 
        int temp = q1.front(); 
        // to empty the auxiliary queue after last operation 
        q1.pop(); 
        // push last element to q2 
        q2.push(temp); 
        // swap the two queues names 
        queue<int> q = q1; 
        q1 = q2; 
        q2 = q; 
        return temp; 
    } 
};
int main() 
{ 
    Stack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    s.push(4); 
    cout <<s.top()<<"\n"; 
    s.pop(); 
    cout <<s.top()<<"\n"; 
    s.pop(); 
    cout <<s.top()<<"\n"; 
    return 0; 
}

Complexity

If Method-1 is used Then:

For push: O(n)
For pop: O(1)

For push operation we move all the elements in the first queue to second queue, one by one so, that means it requires O(n).
For pop operation, we only remove an element for queue 'q1' so it requires O(1).

If Method-2 is used Then:

For push: O(1)
For pop: O(n)

For push operation we have to only enqueue data one by one in a single queue, that means it requires O(1).
For pop operation, we need to move elements from one queue to another one by one so it requires O(n).

Advantages

1. Speed - Data queues are fast method of inter-process communication. They are fastest form of asynchronous communication between two different tasks.
2. Flexibility - Queues allows computers to handle multiple tasks. The programmer does not need any knowledge of inter-process communication.
3. Multiple Clients - Queues are helpful when multiple consumers share a particular process.