小怡分享之栈和队列
前言：
🌈✨前面小怡给大家分享了顺序表和链表，今天小怡给大家分享一下栈和队列。
1.栈
1.1 概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（last in first out）的原则。
压栈：栈的插入操作叫做 进栈/压栈/入栈。入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2 栈的使用
| 方法 | 功能 |
|---|---|
| Stack() | 构造一个空的栈 |
| E push(E e) | 将e入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
1.3 栈的模拟实现
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
入栈：
- 如果采用尾插法入栈：入栈时间复杂度为O（n），如果有last，那么是O（1），但是出栈操作一定是O（n）；
- 如果采用头插法入栈：入栈时间复杂度为O（1），同时出战复杂度也是O（1）；
结论：
如果采用单链表来实现栈，可以采用头插法的形式入栈和出栈。
import java.util.Arrays;
public class Stack {int[] element;int usedSize;public Stack(){this.element=new int[10];}public int push(int val){if(isFull()){this.element= Arrays.copyOf(element,2*element.length);}element[usedSize++]=val;return val;}public int pop(){int val=peek();usedSize--;return val;}public int peek(){if(empty()){throw new RuntimeException("栈为空，无法获取栈顶元素");}return element[usedSize-1];}public boolean empty(){return 0==usedSize;}public boolean isFull(){return usedSize==element.length;}
}
1.4 栈的应用场景
改变元素的序列
1.若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）；
A.1，4，3，2 B.2，3，4，1
C.3，1，4，2 D.3，4，2，1
答案是：C
2.一个栈的初始状态为空。现将1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）；
A.12345ABCDE
B.EDCB54321
C.ABCDE12345
D.54321EDCBA
答案是：B
采用双向链表来实现栈是完全可以的，入栈不管是头插法还是尾插法，都是可以实现的，时间复杂度都可以达到O（1）。
1.5 概念区分
栈、虚拟机栈、栈帧有什么区别呢？
- 栈：一种数据结构；
- 虚拟机栈：当运行一个函数/方法，给其开辟的一块内存；
- 栈帧：JVM中的一块内存。
2.队列
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() | 检测队列是否为空 |
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
2.3 队列模拟实现
队列中既然可以存储元素，那底层肯定是要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。那么队列的实现用哪个更好呢？
单链表可以实现：单链表加上一个标记尾节点的引用。入队可以采用尾插法，出队可以删除头节点。
注意：就算是有尾结点的标记，也不能从头节点入队，因为删除还是需要找最后一个节点的前一个节点。
双链表可以实现：如果是双向链表，链表的头和尾都是可以进行入队的。
2.4 循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
数组下标循环的小技巧
1.下标最后再往后（offset小于array.length）：index=（index+offset）%array.length；
2.下标最前再往前（offset小于array.length）：index=（index+array.length-offset）%array.length
如何区分空与满
空：只要front和rear相遇，就是空的；
满：1.通过添加size属性记录；
2.保留一个位置。判断：rear的下一个是不是front；
3.使用标记，定义boolean类型元素。
3.双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque是“double ended queue”的简称，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际的工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
4.面试题
1.用队列实现栈
用队列实现栈，指的是用普通的队列来实现栈。
1.模拟的入栈操作是：放到了 不为空的队列当中。
2. 模拟的出栈操作是：把不为空的队列中的size-1个元素放到另一个队列当中。最后剩下的 这一个就是我们模拟“出栈”的元素。
import java.util.LinkedList;
import java.util.Queue;
public class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack(){qu1=new LinkedList<>();qu2=new LinkedList<>();}public void push(int x){if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}public int pop(){if(empty()){return -1;}if(!qu1.isEmpty()){int size=qu1.size();for(int i=0;i<size-1;i++){qu2.offer(qu1.poll());}return qu1.poll();}else {int size=qu2.size();int val=0;for(int i=0;i<size-1;i++){qu1.offer(qu2.poll());}return qu2.poll();}}public int top(){if(empty()){return -1;}if(!qu1.isEmpty()){int size=qu1.size();int val=0;for(int i=0;i<size;i++){val=qu1.poll();qu2.offer(val);}return val;}else {int size=qu2.size();int val=0;for(int i=0;i<size;i++){val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty(){return qu1.isEmpty()&&qu2.isEmpty();}
}2.用栈实现队列
模拟队列的入队操作：都是放到第一个栈。
- 判断第2个栈是不是空的？如果是空的需要把第一个栈当中的所有元素都放到第二个栈里，取出第二个栈当中的栈顶元素；
- 如果不是空的，直接取出第二个栈当中的栈顶元素。
import java.util.ArrayDeque;public class MyQueue {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueue(){stack1=new ArrayDeque<>();stack2=new ArrayDeque<>();}public void push(int x){stack1.push(x);}public int pop(){if(empty()){return -1;}if(stack2.isEmpty()){//第一个栈里面所有的元素 放到第二个栈当中while(stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek(){if(empty()){return -1;}if(stack2.isEmpty()){//第一个栈里面所有的元素 放到第二个栈当中while(stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty(){return stack1.isEmpty()&&stack2.isEmpty();}
}
🌈✨今天的分享到这里结束啦，小怡和大家一起分享一起学习一起进步，“成功路上并不拥挤，因为坚持的人不多”。