Queue using two stacks

A Queue is a FIFO (First In First Out) data structure. In this article, we aim to implement a Queue using two stack data structures. To implement Queue generally, we have some simple data structure that can hold data. In general, Queue supports insertion (enqueue) and deletion (dequeue) operations, which we can do with constant time by using either array or list data structure to store data.

Properties of Queue & Stack data structures.

Here to implement Queue using stacks, we have to compromise anyone operation complexity with linear time. When we use two stacks to get the first item in the stack, we have to pop all items from the stack and push into the second stack, as showing in the below picture.

We move all items from stack1 to stack2 to now the popped value from stack2 is the last item in stack1, which is the first item that we inserted. Rest all items by insert back to stack1.
In the second step, we go with the remaining two items, stack1 pops each value and push back to stack2, and the top value in the stack2 is our target item to dequeue. Finally, insert back all items into stack1.

At last, only one item left in the stack1 and pushes that into stack2, and then as that is the only value in the stack2, it returns as dequeue item from the queue. Let’s see the code for this approach.

int deQueue() {
    stack<int> st1; // Second stack.
    while(!st.empty()) {
        st1.push(st.top());
        st.pop();
    }
    int res = st1.top();
    st1.pop();
    while(!st1.empty()) {
        st.push(st1.top());
        st1.pop();
    }
    return res;
}
void enQueue(int val) {
    st.push(val);
}

Here deQueue runs with O(n) complexity. Whereas enQueue only runs with constant time. To do the same, we can use the recursion stack as well as showing in the below code.

Using Recursion stack

int deQueRec() {
    if(st.empty()) {
        return -1;
    }
    int tmp = st.top();
    st.pop();

    if(st.empty()) {
        return tmp;
    }
    int item = deQueRec();
    st.push(tmp);
    return item;
}

Here the recursion stack is the secondary stack, which also takes O(n) complexity. Let’s see the complete code with the main function.

// Output
8
5
7

We discussed both iterative and recursive approaches to implement a Queue using two stacks. If you have any better approach to solve this, please let our readers know by commenting here below. Happy Learning!.