How to implement a queue using stacks in C++
Educative Answers TeamThe task at hand is to implement a queue using a stack data structure, with the push (adding an element) and pop (removing an element) operations as the low-level data structure.
A queue is a FIFO (First In First Out), while a stack is a LIFO (Last In First Out) data structure.
A stack pushes a new element to the top of the stack and also pops the element at the top. A queue, however, dequeues (removes) an element from the top of the queue, but it enqueues (inserts) an element at the bottom.
Implementation
There are two methods used to implement a queue using the stack data structure. One method uses two stacks while the other uses one.
Using two stacks
This method ensures that the oldest inserted element is always at the top of stack1 so that the deQueue operation just pops from stack1. To put the element at the top of stack1, stack2 is used.
enqueue(x):
-
While
stack1is not empty, push everything fromstack1tostack2. -
Push
xtostack1. -
Push everything back to
stack1.
dequeue(x):
-
If
stack1is empty, display an error message. -
Pop an item from
stack1and return it.
Code
The code snippet below puts the above algorithm into code:
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> stack1, stack2;
void enqueue(int x)
{
// Move all elements from s1 to s2
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
// Push item into s1
stack1.push(x);
// Push everything back to s1
while (!stack2.empty()) {
stack1.push(stack2.top());
stack2.pop();
}
}
// Dequeue an item from the queue
int dequeue()
{
// if first stack is empty
if (stack1.empty()) {
cout << "queue is Empty";
exit(0);
}
// Return the top of stack1
int x = stack1.top();
stack1.pop();
return x;
}
};
int main()
{
Queue q;
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
return 0;
}
Using one stack
A queue can also be implemented using only one user stack; this method uses recursion.
enqueue(x):
- Push
xtostack_.
dequeue(x):
-
If
stack_is empty, then display an error message. -
If
stack_has only one element, then return it. -
Recursively pop everything from the
stack_, store the popped item in a variableret, push theretback tostack_, and returnret.
Step 3 of
dequeue()makes sure that the last popped item is always returned. Recursion stops when there is only one item in thestack_, so the last element ofstack_indequeue()is returned, while all other items are pushed back instack_.
Code
The code snippet below puts the above algorithm into code:
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> stack_;
// Enqueue an item to the queue
void enqueue(int x)
{
stack_.push(x);
}
// Dequeue an item from the queue
int dequeue()
{
if (stack_.empty()) {
cout << "Queue is empty" << endl;;
exit(0);
}
// pop an item from the stack
int x = stack_.top();
stack_.pop();
// if stack becomes empty, return
// the popped item
if (stack_.empty())
return x;
// recursive call
int ret = dequeue();
// push popped item back to the stack
stack_.push(x);
// return the result of deQueue() call
return ret;
}
};
int main()
{
Queue q;
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
return 0;
}
RELATED TAGS
View all Courses
