C++ 使用队列反转堆栈

介紹

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

什么是堆栈

数据结构中的堆栈是受现实生活中的堆栈启发的。它使用LIFO（Last In First Out）逻辑，这意味着在堆栈中最后进入的元素将被首先删除。在它里面，元素是在顶部插入的，并且将只从顶部删除。堆栈只有一个端点。

在现实生活中，堆栈的一个例子是一叠报纸。从这堆报纸中，最后放置的报纸会先被删除。

堆栈的基本功能

• 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 

结论

我们可以通过使用队列轻松地逆转一个堆栈。我们把堆栈的元素插入队列，然后再把队列的元素重新插入堆栈中。我希望你能发现这个方法很容易理解和实现。