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

双端队列的基础

Deque是一种连续的数据结构，可以在常数时间内从前端和后端添加或删除元素。在向量中，我们只能在后端执行这些操作，这使得双端队列成为双边向量。双端队列可以作为向量、栈和队列使用，使它成为它们的超集。

语法

C++中deque的语法

deque<data_type> deque_name;

在这里，data_type是我们想要添加到deque中的元素的数据类型，例如int、long long、string、float、vector等，而deque_name是程序员给deque数据结构的命名。

示例

让我们看一些deque的基本函数-

#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

队列和双端队列之间的一些关键区别

队列只能在尾部插入，而双端队列可以在两端都进行插入。
双端队列可以在两端移除元素，而队列只能从前面移除。
我们可以访问双端队列的每个索引，而队列只能访问前面的索引。
双端队列是栈、向量和队列的超集。
通过循环可以遍历双端队列而不移除元素，但要遍历队列必须先移除元素。

比较基础	队列	双端队列
插入	只能在队列的尾部插入元素。	可以在两端插入元素。
删除	只能从队列的前端删除元素。	可以在两端删除元素。
访问元素	只能访问队列的前端元素。	可以访问双端队列中的每个元素。
遍历	必须移除队列元素才能遍历。	使用循环遍历双端队列时不需要移除元素。