数据结构 栈和队列

📕1.栈(Stack)

栈:一种特殊的线性表,只允许在固定的一段进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

从下图中我们可以看到,Stack类继承了Vector类,Vector和ArrayList类似,都是动态的顺序表，不同的是
Vector是线程安全的(有关线程问题请阅读JAVA EE ------> 多线程篇)。

✏️1.1 栈的基本操作

✏️1.2 栈的模拟实现

栈模拟实现源码,点击即可传送!!!

🔖1.2.1 构造方法

🔖1.2.2 扩容方法

🔖1.2.3 判断栈是否为空或是否满

🔖1.2.4 存储元素

🔖1.2.5 删除元素

🔖1.2. 6 获取栈顶元素

✏️1.3 逆波兰表达式

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰表达式计算: 以leetcode150题为例 逆波兰表达式求值

利用逆波兰表达式计算时，使用一个栈来存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

1. 如果遇到操作数，则将操作数入栈；
2. 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈；
3. 遍历完成后，栈内只有一个元素，该元素即为逆波兰表达式的值。

逆波兰表达式解决代码,点击传送!!!

📕2. 队列

队列：只允许在⼀端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO(First In First Out)原则
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）

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

✏️2.1 队列的基本操作

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

Queue<Integer> q = new LinkedList<>();
//实例化Linkedlist对象

✏️2.2 队列的模拟实现

队列的实现采用双向链表,链表头与链表尾都可以当作队头和队尾,时间复杂度都是O(1)

/**
 * name:XulongZhu
 */
public class MyQueue {

    //内部类,一个双向链表的节点
    static class Node{
        Node prev;
        Node next;
        int val;
        //节点的构造方法
        public Node(int val){
            this.val = val;
        }
    }

    //链表的头和尾
    public Node front;
    public Node rear;
    /**
     * 规定:链表头为队列头,链表尾为队列尾,插入采用尾插法
     */

    //添加元素
    public void offer(int val){
        Node node = new Node(val);
        //队列为空时
        if (front==null){
            front = node;
            rear = node;
        }else {
            rear.next = node;
            node.prev = rear;
            rear = node;
        }
    }

    //获取队头值
    public int peek(){
        //防止队列中没有元素
        if (front==null){
            return -1;
        }

        return front.val;
    }

    //获取队列中有效元素个数
    public int size(){
        int count = 0;
        Node cur = front;
        while (cur!=null){
            cur = cur.next;
            count++;
        }
        return count;
    }

    //删除队列中元素,并返回
    public int poll(){

        //队列为空
        if (front==null){
            return -1;
        }

        int val = front.val;
        front = front.next;
        //只有一个结点的话,此时front是null,让rear也为null,此时双向链表里就一个节点都没有了
        if (front!=null){
            front.prev = null;
        }else{
            rear = null;
        }
        return val;
    }
}

✏️2.3 循环队列

环形队列通常使用数组实现。

1. 数列下标循环小技巧

//定义数组下标,初始位置为0
int index = 0;

//遍历时不让index++,而是让index++后对数组长度取余,这样便可达到数组下标循环效果
index = (index+1) % arr.length

2. 如何区分环形队列空与满
   A: 通过添加SIZE属性,当SIZE等于数组长度是,环形队列就是满的.
   B: 牺牲一个位置,假设数组长度为8,但是只存放7个数据
   C: 使用标记,队列为空时，front = rear = 0，标志位 isFull = false.每次⼊队检查rear是否与 front 重合，如果重合设置 isFull = true，表示队列已满，否则，正常入队并移动 rear.出队时，移动 front 指针，设置 isFull = false.

练习题:设计循环代码
源码,点击传送!!!

✏️2.3 双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是“double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。


💡💡💡注意:因为Deque是一个接口,所以不能实例化,使用时必须创建LinkedList的对象。