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

}