Using a queue to reverse a stack

introduce

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.

What is a stack?

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.

Basic functions of the stack

• 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()

What is a queue?

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.

Basic functions of queue

• 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()

Reverse stack using queue

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.

algorithm

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.

Example

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);
}

Output

Initial Queue is: 1 2 3 4 5 
Reversed Queue is: 5 4 3 2 1 

in conclusion

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!