Implementing Queue using Stack in two ways

Reading time: 35 minutes | Coding time: 15 minutes

Illustration

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first.

Definition

A Queue is defined by its property of FIFO, which means First in First Out, i.e the element which is added first is taken out first. This behaviour defines a queue, whereas data is actually stored in an array or a list in the background.
What we mean here is that no matter how and where the data is getting stored, if the first element added is the first element being removed and we have implementation of the functions enqueue() and dequeue() to enable this behaviour, we can say that we have implemented a Queue data structure.

Basic Operations

Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic operations associated with queues:

1. enqueue() − add (store) an item to the queue.
2. dequeue() − remove (access) an item from the queue.

*NOTE :- In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.
Few more functions are required to make the above-mentioned queue operation efficient. These are:

1. peek() − Gets the element at the front of the queue without removing it.
2. isfull() − Checks if the queue is full.
3. isempty() − Checks if the queue is empty.

Implementation Details

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

Implementation

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly)

In this approach, we make sure that the oldest element added to the queue stays at the top of the stack, the second oldest below it and so on.

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

NOTE: First stack(stack1) is the main stack being used to store the data, while the second stack(stack2) is to assist and store data temporarily during various operations.

Pseudocode for enqueue:

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.

Pseudocode for dequeue:

deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it

Method 2 (By making deQueue operation costly)

In this method, in en-queue operation, the new element is inserted at the top of stack1 simply by calling the push() function. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

Here, we insert a new element onto the stack1, but doing so will push our first element towards the bottom of the stack, as we insert more elements to the stack.
But we want the first element to be removed first. Hence in the dequeue operation, we will have to use the second stack2.

Pseudocode for enqueue:

enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

Pseudocode for dequeue

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.

Method 2

Method 2 is better 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 empty.

Implementation Of Method - 2

• C++

   #include<bits/stdc++.h>
   using namespace std; 
       class Stack
        {
            int top;
            public:
            int a[10];  
            Stack()
            {
                top = -1;
            }
            void push(int x);
            int pop();
            bool isEmpty();
        };
        // function to insert data into stack
        void Stack::push(int x)
        {
            if(top >= 10)
            {
                cout << "Stack Overflow \n";
            }
            else
            {
                a[++top] = x;
                cout << "Element Inserted into Stack\n";
            }
        }
        // function to remove data from the top of the stack
        int Stack::pop()
        {
            if(top < 0)
            {
                cout << "Stack Underflow \n";
                return 0;
            }
            else
            {
                int d = a[top--];
                return d;
            }
        }
        // function to check if stack is empty
        bool Stack::isEmpty()
        {
            if(top < 0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        class Queue {
            public:
            Stack S1, S2;
            void enqueue(int x);
            int dequeue();
        };
        // enqueue function
        void Queue :: enqueue(int x) 
        {
            S1.push(x);
            cout << "Element Inserted into Queue\n";
        }
        // dequeue function
        int Queue :: dequeue() 
        {
            int x, y;
            while(!S1.isEmpty()) 
            {
                // take an element out of first stack
                x = S1.pop();
                // insert it into the second stack
                S2.push(x);
            }
            // removing the element
            y = S2.pop();
        // moving back the elements to the first stack
        while(!S2.isEmpty()) 
        {
            x = S2.pop();
            S1.push(x);
        }
        return y;
    }
    // main function
    int main()
    {
        Queue q;
        q.enqueue(10);
        q.enqueue(100);
        q.enqueue(1000);
        cout << "Removing element from queue" << q.dequeue();
        return 0;
    }

Complexity

If Method - 1 is used Then:
For Enqueue : O(n)
For Dequeue : O(1)

For method-2, If the queue is not empty, we move all the elements present in the first stack to the second stack, one by one so, that means it requires O(n).
Also, In this approach the oldest element added to the queue always stays at the top of the stack, the second oldest below it and so on so, Dequeue operation requires only O(1).

If Method - 2 is used Then:
For Enqueue : O(1)
For Dequeue : O(n)

For method-2,The worst case running time for implementing these(enqueue & dequeue) operations using stacks is O(n) because you need to transfer n elements from stack 1 to stack 2 when a dequeue method is called. Pushing to stack 1 is simply O(1).

Or we can say ,when we are inserting at top of stack this means, we have to delete element from bottom(because in queue insertion and deletion are done at opposite ends) for this we have to shift n-1 top element to 2nd stack delete bottom most element and then shift back n-1 elements back to 1st stack, it will take,

n-1(popping elements) + n-1(pushing in second stack) + 1(deleting bottom most element) + n-1(shifting back to 1st stack) = 3n-2 = O(n) time.

Advantages

• Some functional programming languages like Haskell, ML, or Lisp support lists as a built-in type. Lists typically are represented as singly, forward-linked lists, which means that they support O(1) prepend but O(n) concatenate. In languages like this, it's extremely easy to make a stack - we just prepend to a list to push and drop the first element to pop. Because of the internal implementation, this runs in O(1) time.if we implement the queue using two stacks (or more; the Hood-Melville queue uses six!), then you can get amortized O(1) enqueue and dequeue even if we only have stacks in our language.
• In some cases you may want to use special stacks to implement the queue to get extra functionality out. For example, you can augment a stack data structure to support O(1) find-min/find-max. If you have a stack like this, you can then use the two-stack construction to make a queue that also has O(1) find-min/find-max. Trying to solve this problem directly is much harder.
• we know that we can simulate a queue with two stacks, you can immediately prove that the queue automaton is at least as powerful as a Turing machine, and thus that queue automata are Turing-complete.

Applications

• A two-stack pushdown automaton is a theoretical computing device with power equivalent to a Turing machine.
• A queue automaton is a similar structure that uses a queue instead of two stacks.