【数据结构】栈(Stack)、队列(Queue)、双端队列(Deque) —— 有码有图有真相

目录

栈和队列

1. 栈（Stack）

1.1 概念

1.2 栈的使用（原始方法）

1.3 栈的模拟实现

【小结】

2. 栈的应用场景

1、改变元素的序列

2、将递归转化为循环

3、逆波兰表达式求值

4、括号匹配

5、出栈入栈次序匹配

6、最小栈

【概念区分】栈、虚拟机栈、栈帧有什么区别呢？

3. 队列（Queue）

3.1 概念

3.2 队列的使用（原生方法）

3.3 队列的模拟实现

3.4 循环队列

4. 双端队列 (Deque)

【面试题】

1、用队列模拟实现栈 （普通队列和普通栈）

2、用栈模拟实现队列（普通栈和普通队列）

【总结】

---

栈和队列

Vector基本上过时了，这里我们不进行讲解。

• LinkedList 不仅能当做链表(用List接口引用)，也能当做队列(用Deque接口和Queue接口引用)
• 主要看你用哪种接口调用LinkedList(一定是LinkedList实现的接口)，LinkedList 就表现哪种形式。在使用方法的时候必须满足接口中组织数据的形式。
• 主要看用哪种方式维护LinkedList的

1. 栈（Stack）

栈是一种数据结构，实体类，特点先进后出。如果数据要支持先进后出这种特点，就要选用数据结构栈这种方式来存储或组织数据。

• 数据结构中，结构就是来描述组织数据的方式的，之所以会有很多数据结构，是因为我们有不同的需求，组织的数据方式不同，有了很多种存储或组织数据的方式，所以就有了很多的数据结构。
• 栈只是一种数据结构，我们可以用数组（顺序表），单链表，双链表来实现栈（维护栈），但是在使用方法的时候必须满足先进后出的形式。
• 栈的底层本来就是一个数组，因为stack类继承了Vector类，而Vector类底层就是一个数组在存储数据。

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在现实生活中的例子：

子弹压弹以及发射。羽毛球放入桶中以及拿出来。

1.2 栈的使用（原始方法）

Stack类中的方法原生方法比较少。size方法继承于父类

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e （入栈）
E pop()	将栈顶元素出栈并返回  （出栈）
E peek()	获取栈顶元素  （查看栈顶元素）
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为2if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}
}

1.3 栈的模拟实现

栈的底层本就是一个数组，可以用数组(顺序表)，单链表，双链表模拟实现栈，但是在使用方法的时候必须满足先进后出的形式。

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似都是动态的顺序表，不同的是Vector是线程安全的。

1、顺序栈（用数组实现栈）

• 里面的数据是拿数组（顺序表，动态扩容的数组）来组织实现的。
• 栈的底层其实就是一个数组，但是我们提供的方法必须满足先进后出的形式。

 数组长度与数组中有效元素个数一定要分清楚。

这里usedSize，不仅可以记录有效元素个数，还能标记当前存储数据元素下标。

public class MyStack implements IStack {private int[] elem;private int usedSize;//1. 记录有效元素个数//2. 存储数据元素下标private static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new int[DEFAULT_CAPACITY];}//入栈@Overridepublic void push(int x) {if (full()) {elem = Arrays.copyOf(elem, elem.length * 2);}this.elem[usedSize] = x;usedSize++;}//出栈@Overridepublic int pop() throws StackEmptyException {if (empty()) {throw new StackEmptyException("栈为空！");}int old = elem[usedSize - 1];usedSize--;//相当于是删除// 如果里面为引用类型// elem[usedSize] = null;return old;}//获取栈顶元素，只查看不删除@Overridepublic int peek() {if (empty()) {throw new StackEmptyException("栈为空！");}return this.elem[usedSize -1];}//栈中有效元素个数@Overridepublic int size() {return this.usedSize;}//栈是否为空@Overridepublic boolean empty() {return usedSize == 0;}//栈中元素是否满了@Overridepublic boolean full() {return usedSize == elem.length;}//遍历打印//注意：该方法并不是栈中的方法，为了方便看测试结果给出的public void display() {for (int i = 0; i < usedSize; i++) {System.out.print(elem[i] + " ");}System.out.println();}
}

栈为空异常类：

public class StackEmptyException extends RuntimeException{public StackEmptyException(String message) {super(message);}
}

2、用链表实现栈（链式栈）

• 用单向链表实现栈：其中入栈用头插，出栈也是在头部，时间复杂度为O(1)
• 用双向链表实现栈：头尾都可以作为出栈和入栈。时间复杂度为O(1)

【小结】

数组维护（实现）栈

• 栈的底层本质就是数组（动态扩容的数组）
• 出栈和入栈时间复杂度都是为O(1)

链表实现栈 (链式栈)：

单链表维护栈

• 需要满足时间复杂度为O(1)，所以从头部插入（入栈），从头部删除（出栈）
• 如果从尾部插入和删除，非常的麻烦（插入的时候需要找尾节点，删除的时候还需要找尾结点）时间复杂度都为O(n)

双向链表维护栈

• 从头部插入（入栈），从头部删除（出栈）
• 从尾部插入（入栈），从尾部删除（出栈）
• 不管从哪里入栈和出栈时间复杂度都是O(1)

栈的底层本就是一个数组，可以用数组（顺序表），单链表，双链表模拟实现栈，但是在使用方法的时候必须满足先进后出的形式。

2. 栈的应用场景

1、改变元素的序列

2、将递归转化为循环

比如：逆序打印链表

用递归方法实现逆序打印链表

递归找两个条件：1、终止条件。2、找自己本身

//递归打印链表
public void display3(LinkedList pHead) {if (pHead == null) {return;}if (head.next == null) {System.out.println(pHead.val + " ");}display3(pHead.next);System.out.println(pHead.val + " ");
}

递归其实就是栈的形式，每次递归都要在栈上开辟栈帧，用栈模拟递归的形式。

利用栈（链式栈，用链表实现栈）去打印逆序链表

思路： 栈是先进后出的，所以把链表中的节点放进栈中，然后出栈打印，就能逆序打印出链表了

//循环方法 利用栈
public void display4() {Stack<ListNode> stack = new Stack<>();ListNode cur = head;//将链表中的节点保存到栈中while (cur != null) {stack.push(cur);cur = cur.next;}//遍历栈while (!stack.empty()) {System.out.print(stack.pop() + " ");}System.out.println();
}

3、逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。OJ链接

什么是逆波兰表达式：

• 将中缀表达式" 1 + ( ( 2 + 3 ) * 4 ) - 5 "转换为后缀表达式（逆波兰表达式）为：" 1 2 3 + 4 * + 5 - "
• 计算器怎么知道字符（ + - * / ）的优先级的高低呢（怎么识别括号的），一般在计算器中运算会把中缀表达式转换为后缀表达式，再通过后缀表达式计算这个表达式的值。
• 中缀表达式转换为后缀表达式(逆波兰表达式)步骤，选择题或填空题小技巧

第一步：从左到右，先乘除后加减，都填上括号

第二步：对应的运算符，挪倒右边括号的外面，只挪一次

第三步：把所有的括号都去掉，就得到了后缀表达式（逆波兰表达式）

拿到后缀表达式了，怎么去计算这个后缀表达式结果呢？

思路：

1. 遍历后缀表达式，把后缀表达式中的元素依次放进栈中，如果遇到了运算符，则弹出栈顶的两个元素，
2. 第一个元素作为运算符的右操作数，第二个元素作为运算符的左操作数，进行计算，只要遇到运算符就弹出栈顶两个元素进行运算，运算后的结果再次入栈，
3. 然后接着让后缀表达式中的元素入栈，直到后缀表达式的元素全部计算完。

遍历后缀表达式，只要是数字就入栈，是字符就弹出栈顶的两个元素，参与运算，最后把运算之后的结果，再次入栈。

这里给了字符串数组，避免二位数的数字被拆分开。

public int evalRPN(String[] tokens) {//创建一个栈Stack<Integer> stack = new Stack<>();//遍历后缀表达式for (String x : tokens) {//如果是操作数，放到栈中if (!isOperation(x)) {//这里将String类类型拆行为int基本类型并压栈//压栈时自动装箱stack.push(Integer.parseInt(x));} else {//如果是运算符则需要弹出栈顶两个元素，作为操作数进行运算//第一个为右边操作数，第二个左边操作数int num2 = stack.pop();int num1 = stack.pop();/*if (x.equals("+")) {stack.push(num1 + num2);}if (x.equals("-")) {stack.push(num1 - num2);}if (x.equals("*")) {stack.push(num1 * num2);}if (x.equals("/")) {stack.push(num1 / num2);}*///这里用switch语句更简洁，如果用if语句形式太多太复杂//判断是哪种运算符，并进行运行switch (x) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;}}}//走完for循环，栈内就剩一个元素了 即计算后的结果，直接返回return stack.pop();
}//判断是否是运算符
private boolean isOperation(String s) {if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;} else {return false;}
}

4、括号匹配

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。OJ链接

有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

分为几种情况：

• 匹配。字符串遍历完成且栈为空。
• 不匹配。
• 一部分匹配：
• 左括号多：字符串遍历完成，栈不空
• 右括号多：字符串没有遍历完，栈空了

思路：

1. 遍历字符串，让左括号入栈，遇到右括号从栈中弹出元素，
2. 看该元素是否是与右括号匹配的左括号（如果是有效的字符串，则一定是第一个右括号与最后一个左括号先匹配），
3. 字符串遍历完了同时栈也空了，说明匹配的。

//括号匹配
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//1.遍历字符串for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//2.判断是否是左括号if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch);} else {//3.遇到了右括号//判断是否是第一次遇见右括号 同时判断了字符串没有遍历完，栈就为空的情况if (stack.empty()) {return false;}char ch2 = stack.peek();//ch2是左括号，获取栈顶元素不删除 此时ch是右括号//出栈的左括号是否跟此时右括号匹配if ((ch2 == '(' && ch == ')') || (ch2 == '{' && ch == '}') || (ch2 == '[' && ch == ']')) {stack.pop();} else {return false;}}}if(!stack.empty()) {return false;}return true;
}

5、出栈入栈次序匹配

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。OJ链接

例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

思路：

1. 遍历第一个序列进行压栈，每次压栈后栈顶的元素与第二个序列中的元素进行匹配，
2. 如果一样，第二个序列 j 往后走继续比较，如果不同，第一个序列继续压栈然后再比较，直到第一个序列遍历完，
3. 如果栈中没有元素，则出栈入栈次序匹配，如果栈中还有元素没有匹配，则出栈入栈次序不匹配。

//出栈入栈次序匹配
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;//遍历第一个序列并压栈for (int i = 0; i < popV.length; i++) {stack.push(pushV[i]);//判断栈顶元素是否与第二序列j位置的元素是否相同while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}//栈中是否还有元素return stack.empty();/*if (!stack.empty()) {return false;}return true;*/
}

• 这里注意stack.peek() == popV[j] ，我们需要对stack是否为空和popV[j]是否越界进行判断。
• 有可能栈空了，j 还没走完
• 有可能 j 走完了，栈还没为空
• 还有一点：stack.peek() == popV[j] 比较的时候尽量用 equals 进行比较。
• Integer的取值范围是 [-128,127]之间，如果弹出的元素在这个范围之内用 == 比较没问题，如果超过了这个范围 这个语句表达的结果就是false

6、最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。即时间复杂度为O(1) OJ链接

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

• pop、top 和 getMin 操作总是在 非空栈 上调用。

问题分析：

• 如果只有一个栈，把元素全部压进去，而最小的元素在栈底，那我们必须把栈底上面的元素都出栈，才能得到这个最小的元素，
• 如果有n个元素，那么检索到最小元素就不是常数时间了（即要在O(1)的时间内拿到最小值）。且在出栈的过程中最小值是在变化的。

思路：

1. 所以必须有两个栈，一个普通栈Stack，一个最小栈minStack。 在第一次往Stack中压栈的时候，无论放值多大或多小，我们都要维护这个值，把它压入minStack栈中，
2. 再次往Stack中压栈时，压栈的元素要与minStack栈顶元素比较，如果小于或等于minStack栈顶元素，我们也要维护这个元素，在Stack中压栈的同时也要把该元素压入minStack栈中，如果大于只在Stack中压栈，
3. 当压栈序列遍历完后，最小栈minStack栈顶元素就是这个压栈序列的最小元素了，能在常数时间内检索到最小元素的栈。
4. 出任何元素的时候如果这个元素在最小栈minStack中有维护的话，minStack栈中也需要出栈。且在出栈的过程中最小值是在变化的。

应题目要求，pop，top和getMin 操作总是在 非空栈 上调用，所以这些方法不用再判断栈是否为空。

import java.util.Stack;
class MinStack {public Stack<Integer> stack;public Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}//入栈public void push(int val) {stack.push(val);if (minStack.empty()) {minStack.push(val);return;}int peekVal = minStack.peek();//-1 < 3if (val <= peekVal) {minStack.push(val);}}//出栈public void pop() {int val = stack.pop();if (val == minStack.peek()) {minStack.pop();}}// peek 获得当前普通栈的栈顶元素，不删除public int top() {return stack.peek();}//最小栈的peek，每次通过这个方法获取 最小值public int getMin() {return minStack.peek();}
}

当写的代码出错了，一定记得调试：

1. 看哪个测试用例错了
2. 拿着这个测试用例去调试画图
3. 一定记住不能光看代码！！！看代码是看不出来的
4. 如果通过肉眼就能看到代码的问题那为什么我们要有编译器呢？直接记事本写代码不就好了。

【概念区分】栈、虚拟机栈、栈帧有什么区别呢？

• 栈是一种先进后出的数据结构；
• 虚拟机栈是JVM划分的一块内存；
• 栈帧：运行程序调用方法时会在虚拟机当中，给这个方法开辟一块内存(空间)，开辟的空间就叫作栈帧。

每个函数(方法)在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中，当函数调用结束时，该函数对应的栈帧会从虚拟机栈中出栈。

注意：每个方法在栈帧中结构都是一样，大小可能不同，栈帧的大小在程序编译时已经确定好的。

3. 队列（Queue）

3.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)

• 入队列：进行插入操作的一端称为队尾（Tail/Rear）
• 出队列：进行删除操作的一端称为队头 （Head/Front）

3.2 队列的使用（原生方法）

在Java中，Queue是个接口，底层是通过链表实现的。

Queue接口里有两组方法，即add，remove，element与offer，poll，peek是对应的，但它们是有区别的，下面会讲。常用的为后者。size和isEmpty方法是继承父类的。

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素（查看元素，不删除）
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}
//执行结果
5
1
2
3

3.3 队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？链式实现(使用较多)，数组(顺序表)实现。

队列的底层本就是一个双向链表，可以用数组(顺序表)，单链表，双链表模拟实现队列，但是在使用方法的时候必须满足先进先出的形式。

1、用链式实现队列（链式队列）

单链表实现队列：

• 入：头插法 -> O(1)     出：删除链表最后一个（需要找尾巴） O(n)
• 入：尾插法 -> O(N)(需要找尾巴)    出：删除链表第一个 O(n)
• 需要满足出队列 入队列，时间复杂度为O(1)，队列的特性。

双链表实现队列（用的最多）

• 入：头插法 -> O(1)    出：删除链表最后一个 O(1)
• 入：尾插法 -> O(1)    出：删除链表第一个 O(1)

单链表实现队列哪种形式 时间复杂度都是O(n)，有局限性；而双链表实现队列哪种形式 时间复杂度都是O(1)，而且队列的底层本来就是双链表实现的，所以使用双链表实现较多。

双向链表模拟实现队列：

//双向链表模拟实现队列
public class MyLinkedListQueue {//节点，内部类public static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//入队列,尾插public boolean offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.prev.next = node;node.prev = last;last = node;}usedSize++;return true;}//出队列，头删public int poll() throws QueueEmptyException {if (head == null)  {throw new QueueEmptyException("队列为空！");}int retVal =  head.val;if (head.next == null) {head = null;last = null;} else {head = head.next;head.prev = null;}usedSize--;return retVal;}//获取队头元素，不删除public int peek() throws QueueEmptyException {if (head == null) {throw new QueueEmptyException("队列为空！");}return head.val;}public int size() {return usedSize;}public boolean empty() {return head == null;}
}

队列为空的自定义异常类

public class QueueEmptyException extends RuntimeException {public QueueEmptyException(String message) {super(message);}
}

单向链表模拟实现队列：

• 这里我们为了更方便模拟实现，在单链表中定义了head指向头节点，last 指向尾节点，usedSize记录节点个数。
• 需要满足时间复杂度为O(1)，队列的特性。只能从尾入，从头删，时间复杂度就都是O(1)了；如果从头进，从尾删，时间复杂度仍为O(n)，因为尾结点删除你找不到上一个节点是谁了（单向的）。
• 如果是双向链表实现就没有局限，所以双向链表才是最通用的链表。

//单向链表模拟实现队列
public class MySingleListQueue {//节点，内部类public static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int usedSize;//入队列,尾插public boolean offer(int val) {ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.next = node;last = node;}usedSize++;return true;}//出队列，头删public int poll() throws QueueEmptyException {if (head == null)  {throw new QueueEmptyException("队列为空！");}int retVal =  head.val;if (head.next == null) {head = null;last = null;} else {head = head.next;}usedSize--;return retVal;}//获取队头元素，不删除public int peek() throws QueueEmptyException {if (head == null) {throw new QueueEmptyException("队列为空！");}return head.val;}public int size() {return usedSize;}public boolean empty() {return head == null;}
}

2、用数组实现队列（顺序队列）

数组（顺序表）实现队列会出现下面情况，从reat位置入(队尾)，从front位置出(队头)，如果数组后面已经满了，而前面因为删除了元素空出了，怎么才能利用起来前面的空间呢，

rear是当前可以存放数据元素下标。

如果说让元素整体往前挪，也需要消耗时间；我们能不能让reat再回去，所以我们引出了环形队列(循环队列)。

下面的循环队列，就是用数组(顺序表)模拟实现的队列。

3.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

rear是当前可以存放数据元素的下标，与数组模拟实现栈中useSize异曲同工之妙。

rear可能放元素放满了，与front相遇；或者front出元素数组为空了，与rear相遇。

问题1、rear和front相遇了，如何区分空与满

解决空还是满，有很多种方案：

1. 使用usedSize进行记录
2. 浪费一个空间来表示满
3. 使用标记

这里我们主要讲解第二种方案：

例如：这里要放89我们可以先让rear判断下一个是否是front，如果下一个是front证明满了不能放了。否则没满。即每次放元素之先rear判断一下。

• 如果front与rear相遇，就认为是空的。
• 如果reat下一个是front，就认为是满的。

问题2、rear怎么从7下标，来到0下标

• rear从7下标到0下标，同时兼顾1下标到2下标这种普通情况。
• rear = (rear + 1) % len
• front = (front + 1) % len

设计一个循环队列。OJ链接

class MyCircularQueue {public int[] elem;//public int usedSize;public int front;//表示队头public int rear;//表示队尾public MyCircularQueue(int k) {elem = new int[k + 1];}//入队列,数组尾入public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}//出队列，数组头出public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}//从队首获取元素public int Front() {if (isEmpty()) {return -1;//或抛出自定义异常}return elem[front];}//获取队尾元素public int Rear() {if (isEmpty()) {return -1;//或抛出自定义异常}int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}//检查循环队列是否为空public boolean isEmpty() {return front == rear;}//检查循环队列是否已满public boolean isFull() {return (rear + 1) % elem.length == front;}
}

这里有两点要注意的：

1. ​​​rear是当前可以存放数据元素的下标，获取队尾元素时会有一种极端情况，如果此时rear是0下标位置，找队尾下标就是下标为7的位置，不能直接通过rear-1 来获得队尾下标。
2. 传入参数k空间容量大小，但是我们是通过浪费一个空间来表示满的情况，需要数组多申请一个，即new  k+1个空间的数组。或者定义usedSize，通过数据的个数来表示front与rear相遇时是满的还是空的情况，就不存在浪费空间的说法了。

4. 双端队列 (Deque)

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头 出队和入队，也可以从队尾 出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象。底层是双向链表实现的。

我们发现，Deque中包含了很多方法：

• Deque底层有 offer()，poll()，peek()  和 add()，remove()，element() 
• Queue底层也有 offer()，poll()，peek()  和 add()，remove()，element() 
• 它们属于两组方法，功能互相对应。
• 区别：底层代码注解为，add 插不了元素会抛异常，对于offer 来说不会抛异常，认为offer 方法优于add

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口：

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue/deque = new LinkedList<>();//双端队列的链式实现

•  不仅可以当做队列，也可以当做栈。
• 双端队列线性实现 -》 常用当做栈使用，因为栈底层本身就是数组。
• 双端队列链式实现 -》 常用当做队列或双端队列使用，因为队列或双端队列底层本身就是链表(双向链表)

【面试题】

他实现了我： 必须是他类中的方法，遵循我的形式，来模拟实现我的形式。

1、用队列模拟实现栈 （普通队列和普通栈）

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。OJ链接

问题分析：

• 队列是先进先出的，栈是先进后出的，这两个矛盾的，所以要用队列实现栈，一个队列是无法实现栈的。需要两个队列实现栈。
• 用队列实现栈 ，那拿什么实现队列呢，用Linkedlist（双向链表）实现队列。
• 为什么不用ArrayDeque （数组）实现链表呢，这就把问题拉回到了用数组和链表区别的问题了。因为数组实现队列有一个缺点就是扩容问题，可能会浪费空间；用Linkedlist实现队列比较多。
• 用链表也可以实现栈，用数组也可以实现栈，但是用数组实现的比较多，用链表实现栈每次需要维护它的指向，所以具体使用看场景。

思路：

• 一个队列是无法实现栈的，需要两个队列实现栈。实例化两个队列，一个为qu1，一个为qu2。
• ”入栈“操作让元素进入非空的队列，如果非空的队列为qu1 ，则让元素入队列(qu1)，就是用队列实现了"入栈"的操作，此时”出栈“操作 则是让qu1中的size-1个元素出队列，然后依次人队列(qu2)中，此时qu1中还剩一个元素，出队列，就是用队列实现了"出栈"的操作；
• 如果非空的队列为qu2，则让元素入队列(qu2)，就是用队列实现了"入栈"的操作，此时”出栈“操作 则是让qu2中的size-1个元素出队列，然后依次人队列(qu1)中，此时qu2中还剩一个元素，出队列，就是用队列实现了"出栈"的操作；
• 如果两个队列都是空的话，则让元素入队列(qu1)，就是用队列实现了"入栈"的操作。

1. ”入栈“：元素放到不为空的队列中 ， 如果两个队列都为空那么就放到第一个队列当中。
2. ”出栈“：元素不为空的队列，出size-1个元素到另一个队列当中
3. 当两个队列都为空的时候，那么说明模拟的栈是空的

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//队列中模拟实现栈的入栈操作public void push(int x) {//哪个队列不为空入哪个队列if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()){qu2.offer(x);} else {//两个队列都为空的 指定存放到第一个队列当中qu1.offer(x);}}//队列中模拟实现栈的出栈操作public int pop() {//两个队列都为空if (empty()) {return -1;//或者抛出自定义异常}//判断哪个队列不为空//出size - 1个元素到另一队列中if (!qu1.isEmpty()) {int size = qu1.size();//进来后，que1队列出size - 1个元素到qu2中for (int i = 0; i < size - 1; i++) {//for (int i = 0; i < qu1.size()-1; i++) {//这里的for循环不能这样写，因为qu1中的size一直在变，//每次qu1中元素出栈后底层的size就会减减，会导致循环次数减少int x = qu1.poll();qu2.offer(x);}return qu1.poll();} else {int size = qu2.size();//进来后，que2队列出size - 1个元素到qu1中for (int i = 0; i < size - 1; i++) {int x = qu2.poll();qu1.offer(x);}return qu2.poll();}}//队列中模拟实现栈的获得栈顶元素操作public int top() {//两个队列都为空if (empty()) {return -1;//或者抛出自定义异常}//判断哪个队列不为空//出size个元素到另一队列中if (!qu1.isEmpty()) {int size = qu1.size();int x = -1;//进来后，que1队列出size个元素到qu2中for (int i = 0; i < size; i++) {x = qu1.poll();qu2.offer(x);}return x;} else {int size = qu2.size();int x = -1;//进来后，que2队列出size个元素到qu1中for (int i = 0; i < size; i++) {x = qu2.poll();qu1.offer(x);}return x;}}//队列中模拟实现栈的是否为空操作public boolean empty() {//两个队列同时为空时，说明模拟实现的栈是空的return qu1.isEmpty() && qu2.isEmpty();}
}

这里代码要注意两点：

1. 队列中模拟实现栈的出栈操作和获得栈顶元素时，for遍历一个队列size - 1个元素出队列到另一队列时，size() - 1 不能作为for循环的判断条件。因为每次元素从该队列出去，size()在不断减少(变化)，会导致循环次数减少。定义一个变量记录一下size()的值。
2. 队列中模拟实现栈的获得栈顶元素操作时，我们需要一个队列中的size个元素全部到另一个队列中，定义一个变量，每次出队列到另一个队列的元素都记录一下，最后一次记录的就是需要的元素。

2、用栈模拟实现队列（普通栈和普通队列）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty） OJ链接

思路：

• 一个栈是无法实现队列的，需要两个栈实现队列。实例化两个栈，一个是s1，一个是s2。
• “入队列”操作让元素进入s1栈中，就是用栈实现了“入队列”操作。
• “出队列”操作让 s1栈中的元素 全部(size()个）依次出栈，然后进入s2栈中，此时s2栈中的元素顺序与之前s1栈中的元素顺序是相反的，然后出s2栈 栈顶的元素，就用栈实现了“出队列”的操作。

• “入队”：入到s1中
• “出队”：s2栈为空，s1中的元素一个一个全部倒放到第二个队列当中。

//用栈模拟实现队列（普通栈和普通队列）
class MyQueue {private Deque<Integer> s1;private Deque<Integer> s2;//private Stack<Integer> s1;//private Stack<Integer> s2;public MyQueue() {s1 = new ArrayDeque<>();s2 = new ArrayDeque<>();}//栈中模拟实现队列的入队列操作public void push(int x) {s1.push(x);}//栈中模拟实现队列的出队列操作public int pop() {if (empty()) {return -1;//或抛出自定义异常，但力扣上认为-1是正确的}if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}//代码走到这里s2中一定有元素return s2.pop();}//栈中模拟实现队列的获得队头元素操作public int peek() {if (empty()) {return -1;//或抛出自定义异常，但力扣上认为-1是正确的}if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}//代码走到这里s2中一定有元素return s2.peek();}//栈中模拟实现队列的是否为空操作public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}

这里同样也要注意：栈中模拟实现队列的出栈操作和获得队头元素时，如果使用for遍历一个栈size个元素出栈到另一栈时，size()不能作为for循环的判断条件。因为每次元素从该栈出去，size()在不断减少(变化)，会导致循环次数减少。定义一个变量记录一下size()的值。

【总结】

分清楚一点

栈(Stack)是普通类 先进后出

• 栈可以实例化，可以被数组（顺序表）、单链表、双链表实现；栈继承了Vector类，而Vector类底层就是一个数组在存储数据，所以栈的底层其实就是数组(顺序表)。
• 通过数组（顺序表）、单链表、双链表实现的栈调用方法必须遵先进后出的形式。 拿数组（顺序表）实现的栈最常用。

• 用Stack 去引用自己的对象其实不常用。Stack<Integer> stack = new Stack<>(); 不常用
• 用ArrayDeque双端队列的线性实现，来代替实现栈。Deque<Integer> stack = new ArrayDeque<>(); 常用
• ArrayDeque类 底层也是数组（顺序表结构）

队列(Queue)是一个接口 先进先出

• 队列不能实例化，但可以被数组（顺序表）、单链表、双链表实现；队列的底层是被LinkedList类实现的，LinkedList底层又是双向链表，所以队列的底层其实就是双向链表。
• 通过数组（顺序表）、单链表、双链表实现的队列调用方法必须遵循先进先出的形式。
• 拿LinkedList（双向链表）来实现队列最常用。Queue<Integer> queue = new LinkedList<>();

双端队列(Deque)是一个接口 双端进出都可以

• 双端队列不能实例化，但可以被数组（顺序表）、单链表、双链表实现；双端队列的底层是被LinkedList类实现的，LinkedList底层又是双向链表，所以双端队列的底层其实就是双向链表。
• 通过数组（顺序表）、单链表、双链表实现的队列调用方法必须遵循的双端进出都可以形式。
• 拿LinkedList（双向链表）来实现双端队列最常用。Deque<Integer> deque/queue = new LinkedList<>();

拿接口去引用对象 与 拿对象本身来引用自己对象有什么区别？

• 区别：拿对象本身来引用自己对象包含的方法多，能调用的方法多。
• 一般拿接口去实现具体类使用较多，因为可读性比较高，你知道要调用的是谁的方法；而如果拿实体类自己去实体化对象，不知道以什么方式去用的，方法过多

---

好啦Y(^o^)Y，本节内容到此就结束了。下一篇内容一定会火速更新！！！

后续还会持续更新数据结构与算法方面的内容，还请大家多多关注本up，第一时间获取新鲜的知识。

如果觉得文章不错，别忘了一键三连哟！