Implementation of Queue using one Stack in C++
Implementation of Queue using one Stack
In DSA, we use several algorithms with several data structures to soe problems. To understand the several data structures we turn them into one another using several different algorithm. Here is an article about the implementation of a queue using only one stack.
Implementation of Queue using one stack | PrepInsta
Stack vs Queue?
Stack is a data structure where you get Last in First out implementation, and queue is with first in first out implementation.
So, it seems impossible to turn a stack into a queue. Though by basic using of two stacks we can implement a queue very easily : Queue By 2 stacks.
Here goes the algorithm:
Here we are making a class named Queue, and the objects of the class can be used as real queue type data structure. Now as we need to turn a stack into a queue, the builtin stack class from C++ Standard Template Library is used (Stack in C++ STL). Here is how to get it done.
- Firstly, we are going to take one stack. Now stack can push value in the top and pop from there.
- So the top of the stack is going to be treated as the rear or back of the queue. So pushing value in the queue is easy, pushing value in the stack.
- For Pop, If the stack is empty, the queue can not pop anything.
- Now, the pop function or dequeue function is a trick with recursion.
- We know recursion uses stack memory to store recursively called functions. Now suppose in the Pop Function, we pop out one element in the stack, and keep base condition after that.
- The base condition is here as: if the stack is empty, we know the last popped value is the last value in the stack. And the last value in the stack is the front of the queue. So only then we return the value without pushing it back to the stack,
- Otherwise, we recursively call pop function again, store the value of it in another variable, and after that push the popped out value for that calling in the stack. By this, when the recursion will totally end, the values will be pushed in the order they were popped out, just deleting the last value in the stack.
- The same way can be used to check the front value too, using a recursive function.
- There may be a function called empty, saying if the size is 0 or not.
- Otherwise we can track how many nodes are there in the queue, using the size variable in the class.
The code to implement this:
Pushing the element : 5
Pushing the element : 2
Pushing the element : 11
1 5 2 11
The front most value right now is : 1
Pushing the element : 12
Pushing the element : 8
The front most value right now is : 2
2 11 12 8