首頁 >後端開發 >C++ >使用佇列來反轉一個堆疊

使用佇列來反轉一個堆疊

WBOY
WBOY轉載
2023-08-26 17:01:06847瀏覽

介紹

佇列和堆疊都是線性資料結構,用於儲存資料。堆疊使用LIFO原則來插入和刪除元素。佇列使用FIFO原則。在本教程中,我們將學習如何使用佇列來反轉一個堆疊。反轉意味著堆疊的最後一個元素變成第一個,依此類推。

什麼是堆疊?

資料結構中的堆疊受到現實生活中的堆疊的啟發。它使用後進先出(LIFO)邏輯,這意味著最後進入堆疊的元素將首先被移除。在堆疊中,元素從頂部插入,並且只能從頂部移除。堆疊只有一個端點。

在現實生活中,堆疊報紙就是堆疊的一個例子。從堆中取出的報紙是最後放入的報紙。

堆疊的基本功能

  • push() − 它將從頂部插入一個堆疊元素。

    Syntax − stack_name.push(element type)

  • pop() − It will remove elements from the top of the stack.

    Syntax − stack_name.pop()

  • #size() − 它將傳回堆疊的大小。

    Syntax − stack_name.size()

  • #top() − 它傳回堆疊頂元素的參考。

    Syntax − stack_name.top()

使用佇列來反轉一個堆疊

#什麼是隊列?

隊列在資料結構中的概念源自於現實生活中的隊列。在佇列中,元素從後端插入,從前端移除。佇列兩端都是開放的,並且遵循先進先出(FIFO)原則進行操作。這個原則表示先插入的元素將會先從佇列中移除。

隊列的基本功能

  • push() − 將元素插入佇列的後端。

    Syntax − queue_name.push(data type)

  • pop() − 從佇列的前端刪除元素。

    Syntax − queue_name.pop()

  • #front() − 取得隊列中第一個元素的參考。

    Syntax − queue_name.front()

  • #size() − 傳回佇列的大小。

    Syntax − queue_name.size()

#使用佇列反轉堆疊

首先,讓我們透過一個範例來理解什麼是堆疊反轉。

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

邏輯 - 我們使用一個有元素的堆疊和一個空佇列。逐一從堆疊中彈出元素並將它們插入佇列,直到所有元素都插入完成。現在,將佇列元素移除並再次插入空堆疊中。完成。

演算法

Step 1: Insert elements into the Stack.

第二步:取一個空隊列。

步驟3:逐一將堆疊元素推入空隊列中。

第四步:現在堆疊為空。

步驟 5:從佇列中逐一彈出元素並推入堆疊。

步驟6:堆疊已反轉。

Example

以下範例顯示。

#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 

結論

我們可以透過使用佇列來輕鬆地反轉一個堆疊。我們將堆疊元素插入佇列中,然後將佇列元素再次插入堆疊中。我希望您能夠輕鬆理解和實現這種方法。

以上是使用佇列來反轉一個堆疊的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除