一，栈

1.1 栈的概念

栈是一种线性表（是一种特殊的线性表），栈只允许在固定一端进行插入和删除元素。插入元素的一端称为栈顶，另一端称为栈底。所以栈中的数据元素满足先进后出（First In Last Out）的原则。

1.2 栈的操作

压栈（push）：栈中插入操作叫做压栈/入栈，在栈顶插入元素

出栈（pop）：栈中删除操作叫做出栈，在栈顶删除元素

读取栈顶元素（peek）：读取栈顶的元素，但是不弹出该元素

获取栈中元素个数（size）：获取栈的元素个数

判断栈为空（empty)：判断栈是否为空，返回true/false

1.3 栈的模拟实现

假设栈的底层实现逻辑是一个顺序表

代码如下：

import java.util.Arrays;public class MyStack {public int[] elem;//定义一个数组用来存储栈内的元素public int usedSize;//用来记录栈内的元素个数public static final int DEFAULT_SIZE = 10;public MyStack() {this.elem = new int[DEFAULT_SIZE];}//push操作public void push(int val) {//需要判断栈是否满了if (isFull()) {this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);}this.elem[this.usedSize] = val;this.usedSize++;}private boolean isFull() {return this.usedSize == this.elem.length;}//pop操作public int pop() {//判断栈是否为空if (empty()) {return -1;//假设栈为空返回-1，也可以抛异常}int ret = this.elem[this.usedSize - 1];this.usedSize--;return ret;}//empty操作public boolean empty() {return this.usedSize == 0;}//peek操作public int peek() {//判断栈是否为空if (empty()) {return -1;//假设栈为空返回-1，也可以抛异常}return this.elem[this.usedSize - 1];}//size操作public int size() {return this.usedSize;}
}

1.4 栈的应用场景

1. • 判断出入栈序列是否匹配

示例：若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

注意：做这种题时只需要对每一种出入栈序列进行手动模拟一遍即可！

2. • 将递归转化为循环

递归的优点：递归的代码简洁

循环的优点：代码的效率更高

示例：逆序打印链表

import java.util.Stack;public class displayList {//递归的方式逆序打印链表public void display1() {if(head != null){printList(head.next);//递归函数System.out.print(head.val + " ");}}public void printList(ListNode cur){if(cur == null){return;}//循环的方式逆序打印链表public void display2() {//创建一个栈按照链表的顺序从头到尾将每一个节点压入栈中Stack stack = new Stack();ListNode cur = head;//入栈while(cur != null) {stack.push(cur);cur = cur.next;}//出栈while(!stack.empty()) {System.out.print(cur.val + " ");}System.out.println();}
}

3. 括号匹配

20. 有效的括号 - 力扣（LeetCode）

4. 逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

5. 出栈入栈次序匹配

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

这里的3 4 5后续都将以OJ的形式进行讲解！！！

二，队列

2.1 队列的概念

队列也是一种线性表（也是一种特殊的线性表），只允许在一端进行插入数据，在另一端进行删除操作。插入元素的一端叫队尾，删除元素的一端叫队头。所以队列中的数据元素满足先进先出（First In First Out）的原则。

2.2 队列的操作

入队（offer）：队中插入元素的操作叫入队，在队尾进行插入

出队（poll）：队中删除元素的操作叫出队，在队头进行删除

读取队头元素（peek）：读取队头的元素，但是不弹出该元素

读取队中的元素个数（size）：获取栈的元素个数

判断队列是否为空（isEmpty）：判断栈是否为空，返回true/false

2.3 队列的模拟实现

Queue是一个接口，底层是通过链表来实现的（在实例化时必须实例化LinkedList）

public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;ListNode tail;public int usedSize;//offer操作public void offer(int val) {ListNode node = new ListNode(val);if (this.head == null) {this.head = node;this.tail = node;} else {this.tail.next = node;this.tail = node;}this.usedSize++;}//poll操作public int poll() {if (isEmpty()) {return -1;//假设队列为空时返回-1，也可以抛异常}int ret = this.head.val;this.head = this.head.next;if (this.head == null) {this.tail = null;}this.usedSize--;return ret;}//peek操作public int peek() {if (isEmpty()) {return -1;//假设队列为空时返回-1，也可以抛异常}int ret = this.head.val;return ret;}//empty操作public boolean isEmpty() {return this.usedSize == 0;}//size操作public int size() {return this.usedSize;}
}

2.4 循环队列

环形队列通常使用数组实现，通常保留一个位置来区分空与满

判空：Q.rear == Q.front

判满：(Q.rear+1) % array.length == Q.front

2.5 队列OJ题

1. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

2. 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）