【学习笔记】数据结构与算法03：栈与队列

知识出处：Hello算法：https://www.hello-algo.com/.

文章目录

- 2.2 栈和队列
- - 2.2.1 「栈 stack」
  - - 2.2.1.1 栈的常用操作
    - 2.2.1.2 栈的典型应用
  - 2.2.2「队列 queue」
  - - 2.2.2.1 队列的常用操作
    - 2.2.2.2 队列的典型应用
  - 2.2.3 双向队列「double-ended queue」
  - - 2.2.3.1 双向队列常用操作
    - 2.2.3.2 双向队列的应用场景

2.2 栈和队列

2.2.1 「栈 stack」

「栈 stack」是一种遵循先入后出逻辑的线性数据结构。

堆叠元素的顶部称为“栈顶”
底部称为“栈底”
把元素添加到栈顶的操作叫作“入栈” （push，压栈，将数据压进去
删除栈顶元素的操作叫作“出栈”（pop，出栈，像冒泡一样

栈的先入后出规则

2.2.1.1 栈的常用操作

通常情况下，我们可以直接使用编程语言内置的栈类（Java提供了栈的实现类Stack）

/* 初始化栈 */
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();

2.2.1.2 栈的典型应用

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

2.2.2「队列 queue」

「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

队列头部称为“队首”
尾部称为“队尾”
把元素加入队尾的操作称为“入队”
删除队首元素的操作称为“出队”

队列的先入先出规则

2.2.2.1 队列的常用操作

Java也提供了队列的实现。注意，和栈不一样，Queue<E> 是接口，在此基础上内置了大量的实现类以供使用，下面举例的是实现类是 LinkedList，它既实现了Deque（Queue），还实现了List。

/* 初始化队列 */
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.2.2 队列的典型应用

处理集中爆发的大量订单。队列被大量运用在消息队列中，因此产生了很多MQ中间件。MQ被大量运用在淘宝订单，抢票，秒杀等场景中，用于处理短时间大量订单的情况
按顺序处理代办事件。编程是抽象现实的过程，任何在现实中需要“排队”的场景都可以用到队列。比如打印机的任务队列，餐厅出餐的队列，还有线程池这样需要按顺序处理任务的场景，队列在这些场景中可以有效地维护处理顺序。

2.2.3 双向队列「double-ended queue」

双向队列允许在头部和尾部执行元素的添加或删除操作，结合了栈和队列的特点，具有更高的灵活性。

2.2.3.1 双向队列常用操作

在Java中可以直接使用已提供了双向队列Deque（也是接口

push_first()将元素添加至队首
push_last()将元素添加至队尾
pop_first()删除队首元素
pop_last()删除队尾元素
peek_first()访问队首元素
peek_last()访问队尾元素

/* 初始化双向队列 */
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();