In this guide, you will discover how to utilize a stack to implement a queue in C++ programming language.
Implementing a queue using a stack data structure involves utilizing the push (adding an element) and pop (removing an element) operations at the low level.
A stack operates on the Last In First Out (LIFO) principle, in contrast to a queue which follows the FIFO (First In First Out) approach. When working with a stack, the element at the top is removed through popping, and a new element is added to the top through pushing. Conversely, a queue inserts elements at the bottom (enqueue) and removes elements from the top (dequeue).
Implementation of Queue:
By leveraging the stack data structure, there exist two methods to establish a queue. One strategy involves utilizing a single stack, whereas the alternative approach involves employing two stacks.
Using two stacks:
This technique guarantees that the initial inserted item remains the top element in stack1, allowing the deQueue process to effortlessly pop from stack1. Stack 2 serves the purpose of repositioning the element to the top of stack 1.
enqueue(x):
- While stack1 is not empty, push everything from stack1 to stack2.
- Push x to stack1.
- Push everything back to stack1.
dequeue(x):
- In case stack1 is devoid of elements, an error message is shown.
- Take out an element from stack1 and hand it back.
Example:
Let's consider a scenario to demonstrate the concept of a queue implemented using two stacks in C++.
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> stack1, stack2;
void enqueue(int x)
{
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
stack1.push(x);
while (!stack2.empty()) {
stack1.push(stack2.top());
stack2.pop();
}
}
int dequeue()
{
if (stack1.empty()) {
cout << "queue is Empty";
exit(0);
}
int x = stack1.top();
stack1.pop();
return x;
}
};
int main()
{
Queue q;
q.enqueue(7);
q.enqueue(9);
q.enqueue(8);
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
return 0;
}
Output:
Using one stack:
A queue can be constructed with a single stack operated by the user, leveraging recursive techniques.
enqueue(x):
- Push x to stack_.
dequeue(x):
- If stack_ is empty, display an error message.
- If stack_ has only one element, return it.
- Pop every item off the stack recursively, put it in a variable called ret, push it back into stack, and then return ret.
Dequeue's third phase guarantees the retrieval of the last item to be popped. If there is only a single item left in the stack, the recursion halts by returning the last element from stack within dequeue, and then reintegrating the rest of the items back into stack_.
Example:
Let's consider an example to demonstrate the concept of a queue implemented with a single stack in C++.
#include <bits/stdc++.h>
using namespace std;
struct Queue {
stack<int> stack_;
void enqueue(int x)
{
stack_.push(x);
}
int dequeue()
{
if (stack_.empty()) {
cout << "Queue is empty" << endl;;
exit(0);
}
int x = stack_.top();
stack_.pop();
if (stack_.empty())
return x;
int ret = dequeue();
stack_.push(x);
return ret;
}
};
int main()
{
Queue q;
q.enqueue(7);
q.enqueue(9);
q.enqueue(8);
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
cout << q.dequeue() << endl;
return 0;
}
Output:
Benefits of Queue using stack in C++
There are several advantages to implementing a queue in C++ with two stacks, especially when it comes to simplicity and efficiency in specific situations. Here are a few benefits:
- Simplicity: It is not too difficult to implement. There are two stacks: stack 1 is used for enqueue operations, and stack 2 is used for dequeue operations. It may facilitate understanding and maintenance of the code.
- Effectiveness of Dequeue Functions: In the amortized sense, dequeue operations have a constant time complexity of O(1). The reason for this is that the components are only transferred from stack1 to stack2 when stack2 is empty. Once transferred, stack2 can be efficiently dequeued multiple times until it becomes empty once more, at which point another transfer is initiated.
- Space Efficiency: O(n) is the space complexity, where n is the number of elements in the queue. It is because each element is only ever stored in stack1 or stack2. Higher space complexity could be achieved by using more data structures in other queue implementations.
- Flexibility: This method allows you to select your choice's underlying data structure (stacks). It can be beneficial in scenarios where a stack makes more sense or is more effective than other data structures.
- Enqueue Operations: Enqueue operations have a time complexity of O(1) because they directly push elements onto stack1. However, other data structures like a linked list or a dynamic array might be more efficient in scenarios where enqueue operations are frequent and dequeue operations are infrequent.
