栈与队列
1. 栈
栈(stack)是一种遵循先入后出逻辑的线性数据结构。如图所示，我们把堆叠元素的顶部称为"栈顶"，底部称为"栈底"。将把元素添加到栈顶的操作叫作"入栈"，删除栈顶元素的操作叫作"出栈"。 
1.1 栈的常用操作
栈的常用操作如表所示，具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的push()、pop()、peek()命名为例:
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
push() | 元素入栈(添加至栈顶) | O(1) |
pop() | 栈顶元素出栈 | O(1) |
peek() | 访问栈顶元素 | O(1) |
通常情况下，我们可以直接使用编程语言内置的栈类:
java
/* 初始化栈 */
Stack<Integer> stack = new Stack<>();
/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* 访问栈顶元素 */
int peek = stack.peek();
/* 元素出栈 */
int pop = stack.pop();
/* 获取栈的长度 */
int size = stack.size();
/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();1.2 栈的典型应用
- 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
- 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。
2. 队列
队列(queue)是一种遵循先入先出规则的线性数据结构。如图所示，我们将队列头部称为"队首"，尾部称为"队尾"，将把元素加入队尾的操作称为"入队"，删除队首元素的操作称为"出队"。 
2.1 队列常用操作
队列的常见操作如表所示:
| 方法名 | 描述 | 时间复杂度 |
|---|---|---|
push() | 元素入队，即将元素添加至队尾 | O(1) |
pop() | 队首元素出队 | O(1) |
peek() | 访问队首元素 | O(1) |
我们可以直接使用编程语言中现成的队列类：
java
/* 初始化队列 */
Queue<Integer> queue = new LinkedList<>();
/* 元素入队 */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);
/* 访问队首元素 */
int peek = queue.peek();
/* 元素出队 */
int pop = queue.poll();
/* 获取队列的长度 */
int size = queue.size();
/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();2.2 队列典型应用
- 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
- 各类待办事项。任何需要实现"先来后到"功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。
3. 双向队列
在队列中，我们仅能删除头部元素或在尾部添加元素。如图所示，双向队列(double-ended queue)提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。 
3.1 双向队列常用操作
双向队列的常用操作如表所示，具体的方法名称需要根据所使用的编程语言来确定:
| 方法名 | 描述 | 时间复杂度 |
|---|---|---|
push_first() | 将元素添加至队首 | O(1) |
push_last() | 将元素添加至队尾 | O(1) |
pop_first() | 删除队首元素 | O(1) |
pop_last() | 删除队尾元素 | O(1) |
peek_first() | 访问队首元素 | O(1) |
peek_last() | 访问队尾元素 | O(1) |
同样地，我们可以直接使用编程语言中已实现的双向队列类：
java
/* 初始化双向队列 */
Deque<Integer> deque = new LinkedList<>();
/* 元素入队 */
deque.offerLast(2); // 添加至队尾
deque.offerLast(5);
deque.offerLast(4);
deque.offerFirst(3); // 添加至队首
deque.offerFirst(1);
/* 访问元素 */
int peekFirst = deque.peekFirst(); // 队首元素
int peekLast = deque.peekLast(); // 队尾元素
/* 元素出队 */
int popFirst = deque.pollFirst(); // 队首元素出队
int popLast = deque.pollLast(); // 队尾元素出队
/* 获取双向队列的长度 */
int size = deque.size();
/* 判断双向队列是否为空 */
boolean isEmpty = deque.isEmpty();3.2 双向队列应用
双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。