C++中佇列和雙端佇列的區別

---

佇列和雙端佇列都是C++程式語言STL中定義的線性資料結構。佇列遵循先進先出原則，先新增到佇列的元素將先被移除；而雙端佇列可以在首索引或尾索引處新增元素，同樣，也可以移除任意一端的元素。我們將檢視這兩種資料結構的程式碼，以瞭解它們的確切區別。

佇列基礎

如上所述，佇列基於先進先出原則。我們可以線上性時間複雜度內將元素新增到佇列的末尾，並且可以在恆定時間內移除或彈出位於佇列開頭的元素。

語法

C++中佇列的語法

queue<data_type> queue_name;

這裡，`data_type`是要新增到佇列的元素的資料型別，例如int、long long、string、float、vector等；`queue_name`是程式設計師為佇列資料結構指定的名稱。

讓我們來看一些佇列的基本函式：

示例

#include <bits/stdc++.h>
using namespace std;

// main function 
int main(){
   // defining a queue of integer type
   queue<int>q; // q is the name given to the queue     
   // adding elements to the queue
   q.push(1);
   q.push(2);
   q.push(3);
   q.push(4);    
   // getting size of the queue
   cout<<"Size of the queue is: "<<q.size()<<endl;
   // getting first element of the queue
   cout<<"Front or first element of the queue is: "<<q.front()<<endl;    
   // removing first element of queue
   q.pop();
   cout<<"Front element after popping one time is: "<<q.front()<<endl;    
   // check if queue is empty
   cout<<"Is queue empty? : "<<q.empty()<<endl;
   // remvoing all the elements
   while(q.empty() == false){
      q.pop();
   }
   // check if queue is empty
   cout<<"Is queue empty after removing all the elements? : "<<q.empty()<<endl;
   return 0; 
}

輸出

Size of the queue is: 4
Front or first element of the queue is: 1
Front element after popping one time is: 2
Is queue empty? : 0
Is queue empty after removing all the elements? : 1

雙端佇列基礎

雙端佇列是一種順序資料結構，我們可以從中以恆定時間從前後兩端新增或移除元素。在向量中，我們只能在後端進行這些操作，這使得雙端佇列成為雙向向量。雙端佇列可以作為向量、棧和佇列工作，這使其成為所有這些的超集。

語法

C++中雙端佇列的語法

deque<data_type> deque_name;

這裡，`data_type`是要新增到雙端佇列的元素的資料型別，例如int、long long、string、float、vector等；`deque_name`是程式設計師為雙端佇列資料結構指定的名稱。

示例

讓我們來看一些雙端佇列的基本函式：

#include <bits/stdc++.h>
using namespace std;

// main function 
int main(){
   // defining a queue of integer type
   deque<int>dq; // q is the name given to the queue     
   // adding elements to the deque from front
   dq.push_front(1);
   dq.push_front(2);    
   // getting size of the deque
   cout<<"Size of the queue is: "<<dq.size()<<endl;
   // adding elements to the deque from back
   dq.push_back(3);
   dq.push_back(4);
   // print deque 
   for(int i=0; i<dq.size(); i++){
      cout<<dq[i]<<" ";
   }
   cout<<endl;    
   // getting size of the deque
   cout<<"Size of the deque is: "<<dq.size()<<endl;    
   // getting first element of the deque
   cout<<"Front or first element of the deque is: "<<dq[0]<<endl;    
   // removing first element of deque
   dq.pop_front();
   cout<<"Front element after popping one time is: "<<dq[0]<<endl;
   // getting last element of the deque 
   cout<<"Front or first element of the deque is: "<<dq.back()<<endl;    
   // removing first element of deque
   dq.pop_back();
   cout<<"Front element after popping one time is: "<<dq.back()<<endl;    
   // check if queue is empty
   cout<<"Is deque empty? : "<<dq.empty()<<endl;
   // removing all the elements
   while(dq.empty() == false){
      dq.pop_back();
   }
   // check if deque is empty
   cout<<"Is deque empty after removing all the elements? : "<<dq.empty()<<endl;
   return 0; 
}

輸出

Size of the queue is: 2
2 1 3 4 
Size of the deque is: 4
Front or first element of the deque is: 2
Front element after popping one time is: 1
Front or first element of the deque is: 4
Front element after popping one time is: 3
Is deque empty? : 0
Is deque empty after removing all the elements? : 1

佇列和雙端佇列之間的一些關鍵區別

• 佇列只能在尾部插入，而雙端佇列可以在兩端插入。

• 雙端佇列可以在兩端移除元素，而佇列只能從頭部移除。

• 我們可以訪問雙端佇列的每個索引，而對於佇列，則只能訪問頭部索引。

• 雙端佇列是棧、向量和佇列的超集。

• 可以使用迴圈遍歷雙端佇列而不移除元素，但對於佇列，必須移除元素才能遍歷佇列。

比較依據	佇列	雙端佇列
插入	只能在尾部插入元素。	可以在兩端插入元素。
移除	只能從頭部移除元素。	可以在兩端移除元素。
訪問元素	只能訪問佇列的頭部元素。	可以訪問雙端佇列的每個元素。
遍歷	必須移除佇列元素才能遍歷佇列。	可以使用迴圈遍歷雙端佇列而不移除元素。

結論

在本教程中，我們瞭解了C++程式語言中佇列和雙端佇列的區別，其中我們瞭解了它們的基本程式碼和功能。雙端佇列是一種佇列、棧和向量的超集，因為它可以像所有這三種一樣工作；而佇列只遵循FIFO屬性，其中先新增到佇列的元素將首先被移除，依此類推。