Java 栈与队列超详细分析讲解
时间：2023-01-06 09:04:20 | 栏目：JAVA代码 | 点击：次
一、栈（Stack）
1、什么是栈？
栈其实就是一种数据结构 - 先进后出（先入栈的数据后出来，最先入栈的数据会被压入栈底）
什么是java虚拟机栈？
java虚拟机栈只是JVM当中的一块内存，该内存一般用来存放 例如：局部变量当调用函数时，我们会为函数开辟一块内存，叫做 栈帧，在 java虚拟机栈中开辟，具体如下。
常见考点：不可能的出栈顺序
这道题该怎么分析呢？
首先我们知道，出栈时拿到的第一个元素为4，那么4必须入栈，因为入栈的顺序是 1 2 3 4 5 6，所以4要入栈，1 2 3 得先入栈。（通过后面分析得知，该出栈序列正确）
2、栈的常见方法
| 方法 | 作用 |
|---|---|
| E push(E item) | 放入元素 |
| E pop() | 获取栈顶元素并弹出 |
| E peek() | 获取栈顶元素 |
| boolean isEmpty() | 判断栈是否为空（父类Vector的方法） |
3、自己实现一个栈（底层用一个数组实现）
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[4];
}
// 放入元素
public void push(int val) {
if(isFull()) {
// 如果放满了，二倍扩容
this.elem = Arrays.copyOf(elem,2 * elem.length);
}
this.elem[this.usedSize++] = val;
}
// 获取栈顶元素并弹出
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空！");
}
usedSize--;
return elem[usedSize];
}
// 获取栈顶元素
public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空！");
}
return elem[usedSize-1];
}
// 是否为空
public boolean isEmpty() {
return usedSize == 0;
}
// 是否满了
public boolean isFull() {
return elem.length == usedSize;
}
}
二、队列（Queue）
1、什么是队列？
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 - 先进先出。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2、队列的常见方法
// 普通队列 Queue<Integer> queue = new LinkedList<>(); queue.offer(1);// 队尾入 int top = queue.peek();// 获取队头元素 queue.poll();// 弹出队尾元素并返回 // 双端队列 Deque<Integer> deque = new LinkedList<>(); deque.offer(1);// 默认队尾入 deque.offerFirst(2);// 队头入 deque.offerLast(3);// 队尾入 deque.peekFirst();// 获取队头元素 deque.peekLast();// 获取队尾元素 deque.pollFirst();// 弹出队头元素并返回 deque.pollLast();// 弹出队尾元素并返回
3、队列的实现（单链表实现）
/**
* 每个节点
*/
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public class MyQueue {
public Node head;
public Node tail;
/**
* 插入元素 -- 尾插法
* @param val
*/
public void offer(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
}
/**
* 出队列
*/
public int poll() {
if(isEmpty()) {
throw new RuntimeException("队列为空！");
}
int val = head.val;
head = head.next;
return val;
}
/**
* 获取队头元素
*/
public int peek() {
if(isEmpty()) {
throw new RuntimeException("队列为空！");
}
return head.val;
}
// 队列是否为空
public boolean isEmpty() {
return head == null;
}
}
4、循环队列
当考虑用数组来实现一个队列， 很容易想到以下结构：
当我们连续从该队头中弹出元素时，就可以发现问题了
可以看到此时数组并没有满，但是当我们再次插入元素时，队尾却插入不了了，这时候我们可以想到将该数组看成是循环的数组，结构如下。
可以看出，当 front 和 rear 相遇时，队列可能的情况有两种，要么为空，要么是满的状态。那么队列什么时候为空，什么时候是满的呢？
我们有两种方法：
1、设置usedSize 当usedSize和数组长度相等时为满，等于0 则为空。
2、设置标志位 设 flag = true，每放一个元素，将 flag 置为 false，每有一个元素出队列，则将 flag 置为 true。当 front 和 rear 相遇时，flag为 true 则是空的，反之则是满的。
public class MyCircularQueue {
public int[] elem;
public int front;// 队头下标
public int rear;// 队尾下标
boolean flag = true;// 是否为空
public MyCircularQueue(int k) {
elem = new int[k];
}
// 向循环队列插入一个元素。如果成功插入则返回真。
public boolean enQueue(int value) {
if (isFull()) {
return false;
// throw new RuntimeException("队列已满!");
}
elem[rear] = value;
rear = (rear + 1) % elem.length;
flag = false;
return true;
}
// 从循环队列中删除一个元素。如果成功删除则返回真。
public boolean deQueue() {
if (isEmpty()) {
return false;
// throw new RuntimeException("队列为空!");
}
front = (front + 1) % elem.length;
flag = true;
return true;
}
// 从队首获取元素。如果队列为空，返回 -1 。
public int Front() {
if (isEmpty()) {
return -1;
// throw new RuntimeException("队列为空!");
}
return elem[front];
}
// 获取队尾元素。如果队列为空，返回 -1 。
public int Rear() {
if (isEmpty()) {
return -1;
// throw new RuntimeException("队列为空!");
}
// 如果是0下标，拿最后一个元素
if (rear == 0) {
return elem[elem.length-1];
}else {
return elem[rear - 1];
}
}
// 检查循环队列是否为空。
public boolean isEmpty() {
if (rear == front && flag){
return true;
}
return false;
}
// 检查循环队列是否已满。
public boolean isFull() {
if (rear == front && !flag){
return true;
}
return false;
}
}