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属性，其中先添加到队列的元素将首先被移除，依此类推。