栈

栈在计算机编程中很常见，是最基本的数据结构，比如在递归的时候，我们用到了递归栈。那么，栈有什么样的性质呢？ 栈的定义 栈是一种特殊的表，这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈也称为后进先出表（LIFO 表）。 编程时，我们可以用数组来模拟栈的操作，比如定义数组int a[1000]，和栈顶指针top，那么，往栈里压进一个元素x，其操作为a[++top]=x，取出栈顶元素为x=a[top]，删除栈顶元素只需栈顶指针top减一即可。需要特别注意的是，在进栈时，需要判断栈是否已满，出栈时需要判断栈是否为空。

STL Stack

在 C++ 中，我们可以使用标准库stack实现栈的基本操作。使用标准库的栈时，先包含相关的头文件：

#include<stack>

定义栈如下：

stack<int> s;

栈的操作：

s.empty()：如果栈为空返回 true，否则返回 false

s.size()：返回栈中元素的个数

s.pop()：删除栈顶元素但不返回其值

s.top()：返回栈顶的元素，但不删除该元素

s.push()：在栈顶压入新元素

队列

队列是限定在一端进行插入，另一端进行删除的特殊线性表。 允许出队的一端：队头 允许入队的一端：队尾 特性：先进先出（FIFO） 数组模拟队列 定义数组q，队头指针f，队尾指针r，初始f==r表示空队。 进队：q[++r] = x 出队：f++ 假溢出与循环队列 普通队列会出现假溢出（前面空间空闲但队尾已到数组末尾），用循环队列解决。 数组长度m，初始f=r=m 进队：q[(r+1)%m] = x 出队：f=(f+1)%m 队满：(r+1)%m == f

STL Queue

头文件：

#include<queue>

定义：

queue<int> q;

常用操作：

q.push(x)：队尾入队

q.front()：取队头

q.back()：取队尾

q.pop()：队头出队

q.empty()：判空

q.size()：元素个数

双端队列 deque

两端均可插入 / 删除，头文件：

#include<deque>

定义：

deque<int> q;

常用操作：

q.push_back(elem)：尾插

q.push_front(elem)：头插

q.pop_back()：尾删

q.pop_front()：头删

q.front()/q.back()：取头尾

q.empty()：判空

q.size()：元素个数