Home > Article > Backend Development > Using a queue to reverse a stack
Queue and stack are both linear data structures used to store data. The stack uses the LIFO principle to insert and delete elements. The queue uses the FIFO principle. In this tutorial, we will learn how to use queues to reverse a stack. Reversing means that the last element of the stack becomes the first, and so on.
Stacks in data structures are inspired by real-life stacks. It uses last-in-first-out (LIFO) logic, which means that the last element that went onto the stack will be removed first. In a stack, elements are inserted from the top and can only be removed from the top. The stack has only one endpoint.
In real life, stacking newspapers is an example of a stack. The newspaper taken from the pile is the last one put in.
push() − It will insert a stack element from the top.
Syntax − stack_name.push(element type)
pop() − It will remove elements from the top of the stack.
Syntax − stack_name.pop()
size() − It will return the size of the stack.
Syntax − stack_name.size()
top() − It returns a reference to the top element of the stack.
Syntax − stack_name.top()
The concept of queue in data structure originates from the queue in real life. In the queue, elements are inserted from the backend and removed from the frontend. Both ends of the queue are open and operate on a first-in-first-out (FIFO) principle. This principle means that the element inserted first will be removed from the queue first.
push() − Inserts elements into the backend of the queue.
Syntax − queue_name.push(data type)
pop() − Removes an element from the front of the queue.
Syntax − queue_name.pop()
front() − Gets a reference to the first element in the queue.
Syntax − queue_name.front()
size() − Returns the size of the queue.
Syntax − queue_name.size()
First, let us understand what stack inversion is through an example.
Stack before reversing: [2,5,6,7] Stack Reversed: [7,6,5,2]
Logic - We use a stack with elements and an empty queue. Pop elements from the stack one by one and insert them into the queue until all elements have been inserted. Now, the queue element is removed and inserted into the empty stack again. Finish.
Step 1: Insert elements into the Stack.
Step 2: Get an empty queue.
Step 3: Push the stack elements into the empty queue one by one.
Step 4: The stack is now empty.
Step 5: Pop elements from the queue one by one and push them onto the stack.
Step 6: The stack has been reversed.
The following example is shown.
#include<iostream> #include<stack> #include<queue> using namespace std; //function to reverse a queue void reverse(queue<int> &q) { //Declaring a stack s stack<int> s; //inserting Queue elements into stack while (!q.empty()) { s.push(q.front()); q.pop(); } //Again pushing the elements into queue from back while (!s.empty()) { q.push(s.top()); s.pop(); } } void printQueue(queue<int> q) { while(!q.empty()) { cout<<q.front()<<" "; q.pop(); } cout<<endl; } int main() { queue<int> q; //pushing elements into the Queue for(int i=1;i<=5;i++) { q.push(i); } cout<<"Initial Queue is: "; printQueue(q); reverse(q); cout<<"Reversed Queue is: "; printQueue(q); }
Initial Queue is: 1 2 3 4 5 Reversed Queue is: 5 4 3 2 1
We can easily reverse a stack by using a queue. We insert the stack element into the queue, and then insert the queue element into the stack again. I hope you can easily understand and implement this approach.
The above is the detailed content of Using a queue to reverse a stack. For more information, please follow other related articles on the PHP Chinese website!