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

文章目录

一、栈
- 1.1 栈 VS 虚拟机栈 VS 栈帧
- 1.2 数据结构 -- 栈介绍
- 1.3 用数组模拟实现栈
- 1.4 栈的功能：逆序打印
二、队列
- 2.1 数据结果 -- 队列介绍
- 2.2 用单链表模拟实现Queue队列

一、栈

1.1 栈 VS 虚拟机栈 VS 栈帧

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

1.2 数据结构 – 栈介绍

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

1.3 用数组模拟实现栈

实现结构：
- 此处设计是整型数组
- 使用usedSize记录当前有序的数据，插入元素时可以把它当成下标
添加元素 push()：如果数组满了需要扩容
删除元素 pop()：栈不为空时才出元素
获取栈顶元素 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 栈的功能：逆序打印

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

二、队列

2.1 数据结果 – 队列介绍

队列特点：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，且是先进先出
Java中如何使用队列：
- Deque 双端队列：
- Queue 队列：
关于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;}}