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.
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.
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 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 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!.