Java 栈与队列超详细分析讲解

一、栈（Stack）

1、什么是栈？

栈其实就是一种数据结构 - 先进后出（先入栈的数据后出来，最先入栈的数据会被压入栈底）

什么是java虚拟机栈？

java虚拟机栈只是JVM当中的一块内存，该内存一般用来存放 例如：局部变量当调用函数时，我们会为函数开辟一块内存，叫做 栈帧，在 java虚拟机栈中开辟，具体如下。

常见考点：不可能的出栈顺序

这道题该怎么分析呢？

首先我们知道，出栈时拿到的第一个元素为4，那么4必须入栈，因为入栈的顺序是 1 2 3 4 5 6，所以4要入栈，1 2 3 得先入栈。（通过后面分析得知，该出栈序列正确）

2、栈的常见方法

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;
   }
}

来源：https://blog.csdn.net/qq_45792749/article/details/123811021