队列和STL —— queue 【复习笔记】

1. 队列

1.1 队列的概念和术语

队列是一种访问受限的线性数据结构，它遵循先进先出（First In First Out，FIFO）的原则，队列只允许在一端进行插入操作，而在另一端进行删除操作。

允许插入的一端称为队尾，允许删除的一端称为队头

入队：也叫插入操作，是将新元素添加到队尾的操作

出队：也叫删除操作，是将队头元素移除的操作

1.2 队列的实现

和栈一样，队列是一个相对简单的数据结构

下列代码只是简单的模拟一下队列，一些情况如：队列为空再删除元素会发生什么并没有考虑....

//创建
const int N = 1e6 + 10;
//创建一个足够大的数组，用数组充当队列
int q[N];
//因为在队列头和尾操作，t标记尾元素，h标记头元素的前一个位置
//( h,t]的形式，h也可以标记为头元素(个人习惯）
int h, t;//入队，时间复杂度O(1)
void push(int x)
{//从1开始存储q[++t] = x;
}//出队,时间复杂度O(1)
//使用时自己判断能否出队
void pop()
{h++;
}//返回队头,时间复杂度O(1)
int front()
{return q[h + 1];
}//返回队尾，时间复杂度O(1)
int back()
{return q[t];
}//判断队列是否为空,时间复杂度O(1)
bool empty()
{return t == h;
}//返回元素个数,时间复杂度O(1)
int size()
{return t - h;
}

2. queue

2.1 STL —— queue

#include<queue>
//以下操作的时间复杂度都为O(1)
void test()
{queue<int> q;//入队q.push(1);q.push(2);//返回队列里实际元素cout << q.size() << endl;//返回队头元素cout << q.front() << endl;//返回队尾元素cout << q.back() << endl;//出队q.pop();q.pop();//返回队列是否为空if (q.empty()) cout << "空" << endl;
}

2.2 STL —— deque

双端队列（简称 deque）是一种特殊的数据结构，它结合了队列和栈的特点，允许在队列的两端进行插入和删除操作

队列两端分别为前端和后端，两端都可以入队和出队

#include<deque>
typedef pair<int, int> PII;
void test()
{deque<PII> q;//头插，尾插，时间复杂度O(1)q.push_front({1,1});q.push_back({ 2,2 });//返回deque的元素个数cout << q.size() << endl;//返回deque的头元素cout << q.front().first << endl;//返回deque的尾元素cout << q.back().second << endl;//尾删q.pop_back();//头删q.pop_front();//返回deque是否为空if (q.empty()) cout << "空" << endl;for (int i = 1; i <= 10; i++){q.push_front({ i,i });}//清理队列，时间复杂度O(N)q.clear();cout << q.empty() << endl;}