集合中篇—栈与队列

• 2020 年 3 月 10 日
• 筆記

1. 准备

Java的集合实现了栈与队列，我们直接调用就可以实现功能，可是平时就见过Queue、Stack、Deque这些字眼，完全不知道怎么回事，下面就来梳理一下他们的关系，先来看类图（这里简化并只关联了所需要提到的类或接）

• Stack类（栈），继承了Vector线程安全类，现在不推荐使用，推荐ArrayDeque
• Queue接口（队列），有Collection方法，而且也新增了自己的方法
• Deque接口（双向队列），继承了Queue，因为是双向队列，所以可以实现队列和栈的操作
• 我们之前学过的LinkedList以及ArrayDeque实现Deque接口，即可以作为队列和栈使用

2. Queue

Queue接口不同之处在于同一个功能他有两套方法，两套方法区别于一套是实现返回值，另一套是抛出异常

后面讲解基于抛出异常的方法

3. Deque

double ended queue，意思是双向队列，所以该接口多了操作方法，用于操作头尾，下面讲解部分方法，其余自行查看

4. LinkedList

• 之前我们就学过LinkedList了，底层是双向链表，想不到还支持栈和队列，而且有了头尾操作，实现栈和队列就简单了，我们比较熟悉他，所以栈和队列就基于LinkedList来讲解
• 栈和队列用头尾操作实现稍微想一下就会理解的，后面列出表格对照

4.1 栈

先进后出的结构，想象成羽毛球筒就行了，先放进去的羽毛球都是最后才能拿出来的

具体实现

public static void main(String[] args) {        LinkedList linkedList = new LinkedList();        linkedList.addFirst(1);      linkedList.addFirst(2);      linkedList.addFirst(3);      linkedList.addFirst(4);        linkedList.removeFirst();        //一定要用foreach方法，上篇有解释      for(Object i : linkedList){          System.out.println(i);      }  }

3  2  1

4.2 队列

public static void main(String[] args) {        LinkedList linkedList = new LinkedList();        linkedList.addLast(1);      linkedList.addLast(2);      linkedList.addLast(3);      linkedList.addLast(4);        linkedList.removeFirst();        //一定要用foreach方法，上篇有解释      for(Object i : linkedList){          System.out.println(i);      }  }

2  3  4

4.3 对照表

栈

队列