栈（Stack）和队列(Deque、Queue)

一、栈

1.1 栈 VS 虚拟机栈 VS 栈帧

1. 区别：
   • 栈：是一种数据结构
     • 任何数据结构都是用来组织描述数据的
   • 虚拟机栈（JVM虚拟机栈）：是系统的一块内存
   • 栈帧：方法调用的时候，在虚拟机栈上开辟的内存区域

1.2 数据结构 – 栈介绍

1. 栈的特点：只允许在固定的一端进行插入和删除元素操作，且是先进后出的
   
2. Java中如何使用栈：
   • Stack<类型> stack = new Stack<>();
   • 上述方法用得越来越少了，现在多用【ArrayDequeue】代替
3. 栈是如何实现的：
   
4. 关于模拟实现栈：可以用数组/链表，Java中的Stack底层是用数组实现的
   • 用数组实现：看下面
   • 用链表实现
     

1.3 用数组模拟实现栈

1. 实现结构：
   • 此处设计是整型数组
   • 使用usedSize记录当前有序的数据，插入元素时可以把它当成下标
2. 添加元素 push()：如果数组满了需要扩容
3. 删除元素 pop()：栈不为空时才出元素
4. 获取栈顶元素 peek()：栈不为空时才能获取

public class MyStack {private int[] elem;private int usedSize;public MyStack() {this.elem = new int[5];}//压栈 --- 放元素public void push(int val) {if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}public boolean isFull() {return usedSize == elem.length;}//出栈public int pop() {if(empty()) {throw new StackEmptyException("栈为空！");}return elem[--usedSize];}//获取栈顶元素public int peek() {if(empty()) {throw new StackEmptyException("栈为空！");}return elem[usedSize-1];}public boolean empty() {return usedSize == 0;}
}

//这是设计的自定义异常
public class StackEmptyException extends RuntimeException{public StackEmptyException() {}public StackEmptyException(String message) {super(message);}
}

1.4 栈的功能：逆序打印

1. 解析：如果我们要将一个递归实现的代码改成非递归，基本会用到栈/队列
2. 代码：
   

二、队列

2.1 数据结果 – 队列介绍

1. 队列特点：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，且是先进先出

2. Java中如何使用队列：

   • Deque 双端队列：
     

   • Queue 队列：
     

3. 关于Queue队列的模拟实现：数组和链表都可以实现

   • 用数组实现
     
     

   • 用链表实现
     

2.2 用单链表模拟实现Queue队列

public class MyQueue {public ListNode head;public ListNode last;static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}private int usedSize;public void offer(int val) {ListNode node = new ListNode(val);if(head == null) {head = node;last = node;}else {last.next = node;last = last.next;}usedSize++;}public int getUsedSize() {return usedSize;}public int poll() {if(head == null) {return -1;}int val = -1;if(head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;usedSize--;return val;}public int peek() {if(head == null) {return -1;}return head.val;}}