测试4
测试大礼包
爬虫实战特训课

1. 前言

栈和队列是 Java 数据结构中比较简单但又非常重要的类型，我们需要了解栈和队列的存储原理以及各自的特点，熟悉他们各自的常用操作。

2. 后进先出

周末陪孩子玩新买的玩具枪，看到弹夹我乐了，这不就是一个栈容器吗！儿子问我什么是栈，我反问儿子，你装弹的顺序和子弹打出去的顺序有没有关联或规律呢？儿子想了一会说，最先装进去的子弹要等到最后才能被发射出去，而第一发子弹是最后一个装进去的！

（图片来源于网络，版权归原作者所有）

正像枪的弹夹一样，栈表示的是一个后进先出的对象，也叫堆栈。无需百度，直接打开 java.util.Stack 源码还能看到 Java 为此定义了一个专属单词 LIFO ，其实就是 last-in-first-out 的缩写。
细心的小伙伴还会从源码中发现 Stack 其实是继承自 Vector ，上一节我们介绍了数组， Vector 就是可实现自动增长的对象数组，它支持线程的同步。所以我们可以发现，栈的本质也是数组。数据从栈顶压入，操作的时候先从栈顶取出。

3. 栈的常用操作

java.util.Stack 中对栈的操作其实只有五个，也非常简单，我们还是用玩具弹夹为例，结合动图来看。
图片描述

创建一个栈只需要 new Stack () 来在内存中开辟一块连续的默认容量为 10 的空间。添加元素我们称之为压入 push () , 取出元素我们使用 pop () , 查看栈顶元素我们可以使用 peek () , 此外我们还可以使用 empty () 来判断当前栈是否为空栈。

//声明一个栈对象，并向内压入三个元素
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
//判断是否为空栈
System.out.println(stack.isEmpty());//输出：false
//使用peek()方法查询栈顶元素，使用pop()方法取出栈顶元素
System.out.println(stack.peek());//输出：3
System.out.println(stack.pop());//输出：3
System.out.println(stack.peek());//输出：2
System.out.println(stack.pop());//输出：2
System.out.println(stack.peek());//输出：1
System.out.println(stack.pop());//输出：1
System.out.println(stack.isEmpty());//输出：true

图片描述
堆栈类非常简单，但请不要忽视父类 Vector 中有很多方法，感兴趣的小伙伴可以去看源码，后面我们也会介绍 Vector。
图片描述

4. 队列的定义和特点

我们还是从源码中去寻找队列的官方定义，跟栈一样简单的一句话：order elements in a FIFO (first-in-first-out) manner. 翻译成中文就是 “先来后到”。数据从队列的一端进入，从另一端取出。先到先得在我们生活中最常见的例子就是排队了。

5. 队列的常用操作

队列的常用操作也非常简单，我们可以看源码中对 Queue 类中六个方法的介绍。

  • add () ：增加一个元素，如果队列已满，则抛出一个 IIIegaISlabEepeplian 异常；
  • remove () ：移除并返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常；
  • element () ：返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常；
  • offer () ：添加一个元素并返回 true，如果队列已满，则返回 false；
  • poll () ：返问并移除队列头部的元素，如果队列为空，则返回 null；
  • peek () ：返回队列头部的元素，如果队列为空，则返回 null；
//声明一个队列
Queue queue = new LinkedList();
//先向队列中添加五个元素
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
//移除并返回队列头部的元素
System.out.println(queue.remove());//输出：1
//返回队列头部的元素
System.out.println(queue.element());//输出：2
//添加一个元素并返回true，如果队列已满则返回false
System.out.println(queue.offer(6));//输出：true
//返回队列头部的元素
System.out.println(queue.peek());//输出：2
//返问并移除队列头部的元素
System.out.println(queue.poll());//输出：2
System.out.println(queue.poll());//输出：3
System.out.println(queue.poll());//输出：4
System.out.println(queue.poll());//输出：5
System.out.println(queue.poll());//输出：6

但是我们创建 Queue 的时候会发现直接实例化会报错，因为它是 interface 接口，实例化的时候可以用 LinkedList，LinkedList 继承自 Deque，Deque 继承自 Queue。

6. 栈和队列的对比

通过这一节的学习我们知道了栈和队列都是线性表，区别在于栈限定只能在表的一端（栈顶）进行插入和删除操作，队列限定只能在表的一端进行插入，在另一端进行删除。
图片描述

7. 栈和队列的应用场景

栈和队列在我们自己的开发工作中使用是相对比较少的，但是对它们的实际应用却随处可见：

  • 我们的开发工具会对括号 “（” 关闭进行匹配校验，就是在输入左括号 “（” 时将其压入栈内，在输入右括号 “）” 时从栈中取出并进行匹配校验
  • 我们在进行一系列操作后想要撤回上一步操作，也是从我们的操作记录栈中取出了之前操作的历史记录
  • 关于迷宫的解法也用到了栈，用于在使用 “穷举解法” 时记录前面的尝试记录
  • 队列因为可以完美模拟排队场景，因此在餐厅叫号程序、银行医院的排队系统中都会用到队列结构。

8. 小结

通过学习我们知道了栈和队列都是线性数据结构，栈的特点是后进先出，常用的操作有压入 push ()、查询 peek () 和取出 pop () 等；队列的特点是先进先出，常用的操作有添加 add ()、查询 element () 和 peek ()、从队列头部取出 poll () 以及移除 remove () 等。我们要熟练掌握常用的操作和方法，结合实际应用场景，充分利用好它们各自的特点。