数据结构 栈和队列
文章目录
📕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题为例 逆波兰表达式求值
利用逆波兰表达式计算时，使用一个栈来存储操作数，从左到右遍历逆波兰表达式，进行如下操作：
- 如果遇到操作数，则将操作数入栈；
- 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈；
- 遍历完成后，栈内只有一个元素，该元素即为逆波兰表达式的值。
📕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 =newLinkedList<>();//实例化Linkedlist对象✏️2.2 队列的模拟实现
队列的实现采用双向链表,链表头与链表尾都可以当作队头和队尾,时间复杂度都是O(1)
/** * name:XulongZhu */publicclassMyQueue{//内部类,一个双向链表的节点staticclassNode{Node prev;Node next;int val;//节点的构造方法publicNode(int val){this.val = val;}}//链表的头和尾publicNode front;publicNode rear;/** * 规定:链表头为队列头,链表尾为队列尾,插入采用尾插法 *///添加元素publicvoidoffer(int val){Node node =newNode(val);//队列为空时if(front==null){ front = node; rear = node;}else{ rear.next = node; node.prev = rear; rear = node;}}//获取队头值publicintpeek(){//防止队列中没有元素if(front==null){return-1;}return front.val;}//获取队列中有效元素个数publicintsize(){int count =0;Node cur = front;while(cur!=null){ cur = cur.next; count++;}return count;}//删除队列中元素,并返回publicintpoll(){//队列为空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 循环队列
环形队列通常使用数组实现。
- 数列下标循环小技巧
//定义数组下标,初始位置为0int index =0;//遍历时不让index++,而是让index++后对数组长度取余,这样便可达到数组下标循环效果 index =(index+1)% arr.length - 如何区分环形队列空与满
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的对象。
