1. 前言
栈和队列是 Java 数据结构中比较简单但又非常重要的类型，我们需要了解栈和队列的存储原理以及各自的特点，熟悉他们各自的常用操作。
2. 后进先出
周末陪孩子玩新买的玩具枪，看到弹夹我乐了，这不就是一个栈容器吗！儿子问我什么是栈，我反问儿子，你装弹的顺序和子弹打出去的顺序有没有关联或规律呢？儿子想了一会说，最先装进去的子弹要等到最后才能被发射出去，而第一发子弹是最后一个装进去的！ [图片上传失败...(image-29af7-1658654574813)]
（图片来源于网络，版权归原作者所有）
正像枪的弹夹一样，栈表示的是一个后进先出的对象，也叫堆栈。无需百度，直接打开 java.util.Stack 源码还能看到 Java 为此定义了一个专属单词 LIFO ，其实就是 last-in-first-out 的缩写。 细心的小伙伴还会从源码中发现 Stack 其实是继承自 Vector ，上一节我们介绍了数组， Vector 就是可实现自动增长的对象数组，它支持线程的同步。所以我们可以发现，栈的本质也是数组。数据从栈顶压入，操作的时候先从栈顶取出。
3. 栈的常用操作
5f026a14097f900008710686.jpg
创建一个栈只需要 new Stack () 来在内存中开辟一块连续的默认容量为 10 的空间。添加元素我们称之为压入 push () , 取出元素我们使用 pop () , 查看栈顶元素我们可以使用 peek () , 此外我们还可以使用 empty () 来判断当前栈是否为空栈。
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="java" cid="n14" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">//声明一个栈对象，并向内压入三个元素
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
代码块123456789101112131415</pre>
5ee860d80a92e09812000900.jpg
堆栈类非常简单，但请不要忽视父类 Vector 中有很多方法，感兴趣的小伙伴可以去看源码，后面我们也会介绍 Vector。
5ee860f00938b32c09330887.jpg
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；
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="java" cid="n35" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">//声明一个队列
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
代码块12345678910111213141516171819202122</pre>
但是我们创建 Queue 的时候会发现直接实例化会报错，因为它是 interface 接口，实例化的时候可以用 LinkedList，LinkedList 继承自 Deque，Deque 继承自 Queue。
5f02697a09b1f55f08940249.jpg
6. 栈和队列的对比
通过这一节的学习我们知道了栈和队列都是线性表，区别在于栈限定只能在表的一端（栈顶）进行插入和删除操作，队列限定只能在表的一端进行插入，在另一端进行删除。
5ee8616b0a2a51bc12000675.jpg
7. 栈和队列的应用场景
栈和队列在我们自己的开发工作中使用是相对比较少的，但是对它们的实际应用却随处可见：
-
我们的开发工具会对括号 “（” 关闭进行匹配校验，就是在输入左括号 “（” 时将其压入栈内，在输入右括号 “）” 时从栈中取出并进行匹配校验
-
我们在进行一系列操作后想要撤回上一步操作，也是从我们的操作记录栈中取出了之前操作的历史记录
-
关于迷宫的解法也用到了栈，用于在使用 “穷举解法” 时记录前面的尝试记录
-
队列因为可以完美模拟排队场景，因此在餐厅叫号程序、银行医院的排队系统中都会用到队列结构。
8. 小结
通过学习我们知道了栈和队列都是线性数据结构，栈的特点是后进先出，常用的操作有压入 push ()、查询 peek () 和取出 pop () 等；队列的特点是先进先出，常用的操作有添加 add ()、查询 element () 和 peek ()、从队列头部取出 poll () 以及移除 remove () 等。我们要熟练掌握常用的操作和方法，结合实际应用场景，充分利用好它们各自的特点。
网友评论