队列
数组模拟
使用两个指针维护数组q
hh为队头 要做删除操作 以0为起点
tt为队尾 用于插入 和栈同理 以-1为起点
队尾（右边）加 队头（左边）删
入队：q[++tt]=x
出队：hh++
判空 tt≥hh?"no":"yes"
取队头q[hh]
queue
#include <queue>
std::queue<int> myQueue;
队列是一种类型的容器的适配器，FIFO（先进先出），其中元素被插入到所述容器的一端，并从其另一端进行提取操作。
队列被实现为容器的适配器，其是使用特定容器类封装到对象内部，作为其底层的容器类，提供了一个特定的一组成员函数来访问它的元素。
元素被压入到所指定容器的“后面”，并从其“前”弹出。
底层容器可以是标准容器类模板或一些其它专门设计的容器类中的一个。
这个基础容器应至少包括以下操作支持：
- empty
- size
- front
- back
- push_back
- pop_front
标准库容器中的deque和list满足上面的要求。对于没有指定容器的queue实例，默认情况下使用标准库容器deque。
1.队列初始化
deque<int> mydeck(3, 100); // 双端队列里初始化3个元素，都是100
list<int> mylist(2, 200); // list 容器里初始化2个元素，都是200
queue<int> first; // 初始化一个空队列
queue<int> second(mydeck); // 复制 mydeck 的内容初始化队列
queue<int, list<int> > third; // 初始化空队列，底层使用 list 容器
queue<int, list<int> > fourth(mylist); // 复制 mylist 的内容初始化队列，底层使用 list 容器
cout << "size of first: " << first.size() << endl; // 0
cout << "size of second: " << second.size() << endl; // 3
cout << "size of third: " << third.size() << endl; // 0
cout << "size of fourth: " << fourth.size() << endl; // 2
2.判空
queue<int> myqueue1;
bool empty1 = myqueue1.empty(); // true
queue<int> myqueue2({100,100});
bool empty2 = myqueue2.empty(); // false
3.获得元素个数
queue<int> myints;
cout << "0. size: " << myints.size() << endl; // 输出：0
for (int i = 0; i < 5; i++) myints.push(i);
cout << "1. size: " << myints.size() << endl; // 输出：5
myints.pop();
cout << "2. size: " << myints.size() << endl; // 输出：4
4.返回头元素引用
头元素就是最先加入队列的元素，这个元素也是下次pop出队的元素。
queue<int> myqueue3;
myqueue3.push(77);
myqueue3.push(66);
int& a1 = myqueue3.front(); // 77
int a2 = myqueue3.front(); // 77
myqueue3.front() = 88; // 给头元素77赋值为88
cout << "front:" << myqueue3.front() << endl; // 输出：88
5.返回末尾元素引用
末尾元素就是最后加入队列的元素，这个元素也是最新push入队的元素。
queue<int> myqueue4;
myqueue4.push(77);
myqueue4.push(66);
int& b1 = myqueue4.back(); // 66
int b2 = myqueue4.back(); // 66
myqueue4.back() = 33; // 给末尾元素66赋值为33
cout << "front:" << myqueue4.front() << endl; // 输出：33
6.入队/出队
queue<int> myqueue5;
myqueue5.push(55); // 无返回值，入队了一个55，size()==1
myqueue5.push(45); // size()==2
myqueue5.pop(); // 无返回值，出队了一个55，size()==1
7.(C++11)另一种入队，其底层容器调用了emplace_back方法。
myqueue5.emplace(45);
8.(C++11)交换
queue<int> teeth;
teeth.emplace(4); teeth.emplace(7);
queue<int> bags;
bags.emplace(4); bags.emplace(7); bags.emplace(7);
bags.swap(teeth);
cout << teeth.size() << endl; //输出：3
cout << bags.size() << endl; //输出：2
9.运算符 = != > >= < <=
// [==]当两个队列front()内容一致，返回true
queue<int> q1, q2;
bool ret = q1 == q2; // ret为true
// [!=]当两个队列元素front()不相等，返回true
queue<int> q3, q4;
q3.push(1);
bool ret2 = q3 != q4; // ret2为true
// [>]左边队列的front()的元素大于右边队列pop的元素，则返回true.
queue<int> q5, q6;
q5.push(1); q5.push(2); q5.push(2);
q6.push(0); q6.push(2);
bool ret3 = q5 >= q6; // ret3为true，因为1大于0
💬 评论