数据结构 栈和队列

📕1.栈(Stack)

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

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

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

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

✏️1.1 栈的基本操作

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

✏️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 队列的基本操作

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

💡💡💡注意：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的对象。