方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

1.3：栈的应用场景

1.3.1：改变元素序列

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.一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ B）。

A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

1.3.2：将递归转化为循环

为什么可以使用栈将递归转换为循环而不是其他结构？还记得之前的单链表的逆序打印吗？

！！！敲重点：如何将单链表逆序打印？_myi__的博客-CSDN博客

我们发现：后调用的先退出，先调用的后退出----->方法之间的递归调用次序刚好和栈的特性是匹配的。

public void printReverse(Node<E> head){
   if(head == null){
         return;
   }
//一次将链表中的元素保存到栈中
   Stack<E> s = new Stack<>();
   Node<E> cur = head;
   while(cur!=null){
        s.push(cur.value);
        cur = cur.next;
   }
//将栈中的元素依次删除掉
   while(!s.empty()){
        System.out.print(s.pop()+" ");
   }
   System.out.println();
}

注意：并不是所有的递归都得用到栈。

1.4：栈的模拟实现

Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

类和接口总览：??????https://blog.csdn.net/myi__/article/details/121387084

import java.util.Arrays;

public class Stack<E> {
    E[] array;
    int size; //用来表示这个栈中有多少个元素，也可以表示栈顶元素的位置
    public Stack(){
        array = (E[]) new Object[3];
        size = 0;
    }
    public void push(E e){
        //1.先确保栈中空间足够
        ensureCapacity();
        //2.插入元素
        array[size] = e;
        size++;
    }
    public E pop(){
        E ret = peek();
        size--;
        return ret;
    }
    public E peek(){
        if(empty()){
            throw new RuntimeException("pop:栈是空的");
        }
        return array[size-1];
    }
    public boolean empty(){
        return 0 == size;
    }
    public int size(){
        return size;
    }
    private void ensureCapacity(){
        if(size == array.length){
            int newCapacity = size*2;
            array = Arrays.copyOf(array,newCapacity);
        }
    }

    public static void main(String[] args) {
        Stack<String> s = new Stack<>();
        s.push("111");
        s.push("222");
        s.push("333");
        s.push("444");
        s.push("555");
        s.push("666");
        System.out.println(s.size); //6
        System.out.println(s.peek()); //666

        s.pop();
        s.pop();
        System.out.println(s.size); //4
        System.out.println(s.peek()); //444

    }
}

1.5：栈、虚拟机栈、栈帧有什么区别呢？

栈：一般认为时后进先出的一种数据结构---在java的集合中有对应的实现---Stack，Stack在实现时继承了Vector。

虚拟机栈：具有特殊作用的一块内存空间。

? ? ? ? ? ? ? ? ? jvm为了对数据进行更好的管理，将内存按照不同的需求划分出来的一种结构

? ? ? ? ? ? ? ? ? 栈区：线程私有的，栈区中存放的是函数调用相关的一些信息，主要是栈帧

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?当栈区中内存空间不足时，会抛出StackOverflowException

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?当中的元素（栈帧）是按照数据结构中的栈的特性来实现的

栈帧：一种结构，这种结构与函数调用相关的，内部：局部变量表、操作数栈......

? ? ? ? ? ?每个方法在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中

? ? ? ? ? ?当方法调用结束时，该方法对应的栈帧会从虚拟机栈中出栈

? ? ? ? ? ?注意：每个方法的栈帧中结构都是一样，大小可能不同，栈帧的大小在程序编译时已? ? ? ? ? ? ?经确定好的

二：队列（Queue）

2.1：概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头 （Head/Front）

2.2：队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);
        q.offer(6);
        System.out.println(q.size()); //6
        System.out.println(q.peek()); //查看队头元素---1

        q.poll();//删除队头元素
        System.out.println(q.size());//5
        System.out.println(q.peek()); // 2

每个方法的时间复杂度都是O(1)

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

提问：队列底层是使用LinkedList实现的，为什么不使用连续的空间呢？会造成假溢出

如果使用连续空间，也可以达到时间复杂度都是O(1)的需求

虽然方式二也能达到链表的效果，但是它也是有缺陷的。如果你想存储有效元素但是空间存满的话，就算队头的元素已经出队列了，位置空出来了，rear也已经走到空间末尾了，可想而知元素就插不进去了，但其实有效元素并未存满。上述现象就是队列的假溢出。

真溢出是队列中有效元素已经和空间大小相等了，再放不进去元素了。

想要解决假溢出的问题，可以通过循环队列来解决

循环队列

力扣题:设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

class MyCircularQueue {
    int[] array;
    int front = 0;   //队头
    int rear = 0;    //队尾
    int count = 0;   //记录队列里有效元素的个数
    int N;
    public MyCircularQueue(int k) {
    array = new int[k];
    N = k;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }

        //直接往rear位置插入元素
        array[rear] = value;
        rear++;
        if(rear == N){
            rear = 0;
        }
        count += 1;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front++;
        front %= N;
        count -= 1;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    
    public int Rear() {
         if(isEmpty()){
            return -1;
        }
        return array[(rear-1+N)%N];
    }
    
    public boolean isEmpty() {
        return 0 == count;
    }
    
    public boolean isFull() {
        return count == array.length;

    }
}

2.3：队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。

//模拟实现队列 --- 底层使用双向链表 --- 在集合框架Queue是一个接口 --- 底层使用的是LinkedList
public class Queue<E> {
    //双向链表结点
    public static class ListNode<E>{
        ListNode<E> next;
        ListNode<E> prev;
        E value;

        ListNode(E value){
            this.value = value;
        }
    }
    ListNode<E> first;  //队头
    ListNode<E> last;   //队尾
    int size;

    //入队列---向双向链表尾部插入新节点
    public void offer(E e){
       ListNode<E> newNode = new ListNode<>(e);
       if(first == null){
           first = newNode;
       }else{
           last.next = newNode;
           newNode.prev = last;
       }
       last = newNode;
       size++;
    }

    //出队列---将双向链表首结点删除掉
    public E poll(){
        //1.队列为空
        //2.队列中只有一个元素
        //3.队列中有多个元素
        E value = null;
        if(first == null){
            return null;
        }else if(first == last){
            first = null;
            last = null;
        }else {
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        size--;
        return value;
    }
    //获取队头元素
    public E peek(){
        if(first == null){
            return null;
        }
        return first.value;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }

    public static void main(String[] args) {
        Queue<Integer> q = new Queue<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        System.out.println(q.size()); //3
        System.out.println(q.peek()); //1
        System.out.println(q.isEmpty()); //false

        q.poll();
        q.poll();
        q.poll();
        System.out.println(q.size()); //0
        System.out.println(q.peek()); //null
        System.out.println(q.isEmpty()); //true
    }
}