使用队列反转栈

---

简介

队列和栈都是线性数据结构，用于存储数据。栈使用后进先出 (LIFO) 原则插入和删除其元素。队列使用先进先出 (FIFO) 原则。在本教程中，我们将学习如何使用队列反转栈。反转意味着栈的最后一个元素变成第一个元素，依此类推。

什么是栈？

数据结构中的栈受到现实生活中栈的启发。它使用后进先出 (LIFO) 逻辑，这意味着最后进入栈的元素将首先被移除。在栈中，元素从顶部插入，也只能从顶部移除。栈只有一个端点。

现实生活中栈的一个例子是报纸堆。从堆中，最后放置的报纸将首先被移除。

栈的基本函数

• push() − 从顶部插入栈元素。

  语法 − stack_name.push(元素类型)

• pop() − 从栈顶移除元素。

  语法 − stack_name.pop()

• size() − 返回栈的大小。

  语法 − stack_name.size()

• top() − 返回栈顶元素的引用。

  语法 − stack_name.top()

什么是队列？

数据结构中的队列受到现实生活中队列的启发。在队列中，元素从后端插入，从前端移除。队列两端都开放，并且在其操作中使用先进先出 (FIFO) 原则。该原则规定，首先插入的元素将首先从队列中移除。

队列的基本函数

• push() − 将元素插入到队列的后端。

  语法 − queue_name.push(数据类型)

• pop() − 从队列的前端移除元素。

  语法 − queue_name.pop()

• front() − 获取队列中第一个元素的引用。

  语法 − queue_name.front()

• size() − 返回队列的大小。

  语法 − queue_name.size()

使用队列反转栈

让我们首先通过一个例子了解什么是栈反转。

Stack before reversing: [2,5,6,7]
Stack Reversed: [7,6,5,2]

逻辑− 我们使用一个包含元素的栈和一个空的队列。逐个从栈中弹出元素并将其插入到队列中，直到所有元素都插入。现在，移除队列元素并再次将其插入到空栈中。这样就完成了。

算法

步骤 1：将元素插入到栈中。

步骤 2：获取一个空的队列。

步骤 3：将栈元素逐个推入空队列中。

步骤 4：现在栈为空。

步骤 5：逐个从队列中弹出元素并推入栈中。

步骤 6：栈已反转。

示例

以下示例展示了。

#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 

结论

我们可以使用队列轻松反转栈。我们将栈元素插入到队列中，然后再次将队列元素重新插入到栈中。我希望您发现此方法易于理解和实现。