使用佇列反轉棧

---

簡介

佇列和棧都是線性資料結構，用於儲存資料。棧使用後進先出 (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 

結論

我們可以使用佇列輕鬆反轉棧。我們將棧元素插入到佇列中，然後再次將佇列元素重新插入到棧中。我希望您發現此方法易於理解和實現。