前言
在线性表中不止有顺序表和链表，今天的主角就如标题所说--->认识栈和队列。把他们俩放一起总结是有原因的，还请看官听我娓娓道来~
什么是栈？
栈（stack）是限定仅在表尾进行插入和删除操作的线性表
咱可以把栈理解成一个桶，栈底是固定的，放东西进去被称作“进栈”，拿东西被称作“出栈”， 所以栈也是按照后进先出的原则进行操作。
栈的基本方法有以下几种：
| push() | 将元素入栈 |
| pop() | 将栈顶元素出栈并返回 |
| peek() | 获取栈顶元素 |
| size() | 获取栈中有效元素个数 |
| empty() | 检测栈是否为空 |
import java.util.Stack;
public class MyStack {
public static void main(String[] args) {
Stack<Integer> stack =new Stack<>();
//push入栈
stack.push(12);
stack.push(23);
stack.push(34);
//peek获取栈顶元素，但不移除
int ret=stack.peek();
System.out.println(ret);
//pop移除栈顶元素
int ret1=stack.pop();
System.out.println(ret1);//注意看这里就发生了变化
System.out.println(stack.peek());
//获取栈的长度
System.out.println(stack.size());
//判断栈空
if(stack.empty()){
System.out.println("栈已经空");
}else{
System.out.println("栈不为空");
}
}
}运行结果如图所示，搭配画图食用效果更佳
栈的模拟实现
不要忘记栈也是线性表，我们是可以用数组来实现栈的，那么同样也可以用usedSize来记录
首先初始化好一个数组，和顺序表是类似的，不记得的可以先回忆一下-->http://t.csdnimg.cn/t0Rjd
import java.util.Arrays;
public class MyStack {
int []array;
int usedSize=0;
public MyStack(int[] array, int usedSize) {
this.array = array;
this.usedSize = usedSize;
}入栈也是要看满没满，是否需要扩容，道理和模拟实现顺序表是一样的
//push入栈
public void push(int val) {
if (isFull()) {
int[] newArray = Arrays.copyOf(array, array.length * 2);
array = newArray;
}
array[usedSize] = val;
usedSize++;
}
public boolean isFull(){
return usedSize==array.length;
} //peek获取栈顶元素，但不移除
public int peek(){
if(Empty()){
return -1;
}
return array[usedSize-1];
}要记住peek和pop的区别：peek只是获取栈顶元素，pop可是会移除的
//pop移除栈顶元素
public int pop(){
if(Empty()){
return -1;
}
int oldval=array[usedSize-1];
usedSize--;
return oldval;
} //获取栈的长度
public int size(){
return usedSize;
}
//判断栈空
public boolean Empty(){
return usedSize==0;
}
}
最后加上测试类，运行结果如图~
栈的运用
根据它的特性---数据都是后进先出的,来看几道题练练手
1.括号匹配
括号匹配
https://leetcode.cn/problems/valid-parentheses/description/
思考:从题目中就可以看出括号必须类型是一样的，这样左括号和右括号才会匹配，既然如此，顺着走下去，在遍历的过程中咱们把所有类型的左括号全部入栈，遇到不是左边的，便开始出栈去匹配左右括号，如果最后全部对上，那么最后栈必定为空，返回true。
但是左右括号不匹配是有两种情况，一种是还没遍历完字符串时，遇到右括号，栈已经空了，比如：()))))))。还有一种就是遍历结束后栈内还有元素，那就是典型的不匹配了
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
if(s==null||s.length()==0){
return true;
}
for (int i = 0; i <s.length() ; i++) {
char s1=s.charAt(i);
if(s1=='{'||s1=='['||s1=='('){
stack.push(s1);
}else{
if(stack.empty()){//右括号多于左括号
return false;
}
char s2 = stack.pop();//记录出栈的元素
if ((s2 == '{' && s1 != '}') || (s2 == '(' && s1 != ')') || (s2 == '[' && s1 != ']')) {
return false;
}
}
}
return stack.empty();
}
}2.逆波兰表达式求值
逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
思考：观察实例1便能发现运算符写在操作数之后就是这个“逆波兰表达式”，据逆波兰表达式的特性，比如1+2，变成2 1 + ，栈便能解决，比如先将1入栈，2入栈，如果第三次入栈的是运算符号，则将前两次的出栈，然后进行实际的运算，将结果压入栈中。
所以整体符思路就出来了：
1.创建一个栈来存储操作数
2.遍历逆波兰表达式数组的每个元素
3.若当前元素为操作数，则将其压入栈中
4.若当前元素为运算符，则从栈中弹出两个操作数，执行相应的运算，并将结果压入栈中
5.遍历结束后，栈中仅剩下一个元素，即为整个表达式的计算结果
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack= new Stack<>();
for(int i=0;i<tokens.length;i++){//遍历字符串
String temp=tokens[i];
if(!isOperation(temp)){
Integer val=Integer.valueOf(temp);//类型转化成整型
stack.push(val); //不是运算符就入栈 }
else{
Integer val2 = stack.pop();
Integer val1 = stack.pop();//否则弹出两个进行实际的运算
switch(temp){//运算符进行匹配
case "+":
stack.push(val1+val2);
break;
case "-":
stack.push(val1-val2);
break;
case "*":
stack.push(val1*val2);
break;
case "/":
stack.push(val1/val2);
break;
}
}
}
return stack.pop();
}
//遍历字符串的过程判断是否遇到运算符
public boolean isOperation(String s){
if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
return true;
}else{
return false;
}
}
}3.栈的压入，弹出顺序匹配
栈的压入、弹出序列匹配https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
思考：要判断出栈和入栈是否匹配，可以用上辅助栈，将 pushV 中的元素依次入辅助栈，在遍历 pushV 数组的过程中，判断popV数组对应的下标元素是否一样，一样的便出栈，popV遍历下一个，不一样的就pushV 指向下一个元素，直到栈顶元素不再与 popV 数组中对应位置的元素相等或者栈为空为止。最终，如果整个出栈过程符合规则，栈将会为空，此时返回 true；否则，返回 false，配合动图理解更好~
public boolean IsPopOrder (int[] pushV, int[] popV) {
if (pushV == null || popV == null || pushV.length != popV.length) {
return false;//排除一些常见情况
}
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushV.length; i++) {
stack.push(pushV[i]);入栈
while (j < popV.length && !stack.empty()&& popV[j] == stack.peek()) {
stack.pop();//出栈
j++;
}
}
return stack.empty();
}
}4.模拟实现最小栈
最小栈https://leetcode.cn/problems/min-stack/description/
思路：这道题需要实现最小栈,那这道题单靠一个栈，不太好实现，那我们就定义一个辅助栈，把这个辅助栈当做最小栈，
1.在push 的过程中，如果都是空栈，两个栈都入，如果不是，那显而易见只有最小的才会被存进辅助栈中，于是val值和辅助栈的栈顶比较，只有更小的元素才会存进辅助栈，
2.在出栈的过程中，两个栈都要出，只要保证出的是一样的元素即可
3.在获取栈顶元素但不出栈的过程中，只要返回普通栈的即可，因为push的过程中，元素可能不会入辅助栈
4.在获取最小元素的过程中，这是便可直接返回辅助栈的栈顶元素，这也是设置辅助的原因。
配合图片和代码理解效果更佳哦~
class MinStack {
public Stack<Integer> stack;
public Stack<Integer> minstack;
public MinStack() {
stack = new Stack<>();
minstack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minstack.empty()) {//第一次入栈
minstack.push(val);
}else{
Integer peekval = minstack.peek();
if (val <= peekval) {//只有更小才入栈
minstack.push(val);
}
}
}
public void pop() {
if (stack.empty()) {
return;
}
int popVal = stack.pop();
if (popVal == minstack.peek()) {//只要移除的元素和辅助栈的栈顶元素一致就能删
minstack.pop();
}
}
public int top() {
if (minstack.empty()) {
return -1;
} else {
return stack.peek();
}
}
public int getMin() {
if (minstack.empty()) {
return -1;
} else {
return minstack.peek();
}
}
}什么是队列？
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
咱可以把它理解成排队打饭的过程，进行排队(插入)操作的一端称为队尾, 进行打完饭走人(删除)操作的一端称为队头 ,配合下图就好理解多了~
队列的基本方法有以下几点：
| offer() | 入队 |
| poll() | 出队并返回出队元素——>就是队头 |
| peek() | 获取对头元素 |
| size() | 获取队列的元素个数 |
| isEmpty() | 判断队列是否为空 |
咱们上机试试：
import java.util.LinkedList;
import java.util.Queue;
public class MyQueue {
public static void main(String[] args) {
Queue<Integer> queue=new LinkedList<>();
//入队列
queue.offer(1);
queue.offer(2);
queue.offer(3);
int ret=queue.peek();//获取对头元素
System.out.println(ret);
System.out.println(queue.size());//获取队列元素个数
System.out.println(queue.isEmpty());//判断队列是否为空
System.out.println(queue.poll());//出队列
}
}搭配图片就更好理解了：
队列的模拟实现
这里用到的是链式结构去模拟实现，要注意，看下图理解更好~
先定义好一个双向链表
class ListNode{
public int val; // 节点的值
public ListNode prev; // 前驱节点
public ListNode next; // 后继节点
// 节点构造函数
public ListNode(int val){
this.val=val;
}
}
public ListNode head; // 头结点
public ListNode last; // 尾结点offer()入队----类似尾插
public void offer(int val){//尾插
ListNode node=new ListNode(val);
if(head==null){
head=last=node; // 将新节点作为唯一节点，即头结点和尾结点都指向它
}else {
last.next = node; // 将尾结点的后继节点指向新节点
node.prev = last; // 将新节点的前驱节点指向原尾结点
last = last.next; // 更新尾结点为新节点
}
}poll()出队----类似头删
public int poll(){
if(head==null){
return -1;
}
int ret=head.val;
if(head.next==null){ // 如果头结点后面没有节点，即队列只有一个节点
head=null; // 此时就是清空队列
}else {
head=head.next; // 更新头结点为原头结点的后继节点
head.prev=null; // 清空新头结点的前驱节点
}
return ret;
}peek()-----返回头结点的值即可
public int peek(){
if(head==null){
return -1;
}
return head.val; // 返回头结点的值
}isEmpty()----看头结点空不空
public boolean isEmpty(){
return head==null; // 头结点为空表示队列为空
}最后加上一个测试类，看运行结果就模拟实现成功了~
循环队列
那队列用顺序结构实现是什么样呢？-------->就是循环队列
看上面的图解是不是理解了很多？就是卷起来~这样的话就能循环利用数组空间了
那接下来就用数组来模拟实现它吧！
设计循环队列https://leetcode.cn/problems/design-circular-queue/description/
思考：既然是循环，首尾如何连接呢？这个又是数组，不能像链表一样去改变指向，这时就有一个公式：first=(first+1)%len;这样的走向是远远好于first++的，这样就不用考虑越界的问题了
于是先用数组去定义这个循环队列，定义好首和尾
public class MyCircularQueue {
public int[] elem;
public int first;
public int last;
public MyCircularQueue(int k) {
elem = new int[k];
}入队和出队原理是一样的，要考虑循环，所以不能直接++；
public boolean enQueue(int value) {//入队
if (isFull()) {
return false;
}
elem[last] = value;//不为空直接入队
last = (last + 1) % elem.length;//更新队尾指针，考虑循环情况
return true;
}
public boolean deQueue() {//出队
if (isEmpty()) {
return false;
}
first = (first + 1) % elem.length;//出队就是first移动，道理是一样的
return true;
}队头元素直接获取即可，队尾就要注意了，一般情况下，直接获取下标是last-1的元素即可，因为这里浪费了一个空间，好区分空和满，但如果last刚好指向0，数组下标是没有-1的，所以这里要做判断，如果是last==0，返回的其实是最后一个元素，下标就是len-1的元素
public int Front() {//获取队头元素
if (isEmpty()) {
return -1;
}
return elem[first];
}
public int Rear() {//获取队尾元素
if (isEmpty()) {
return -1;
}
int index = last == 0 ? //要考虑last是否是0
elem.length - 1 : last - 1;
return elem[index];
}空和满是首先考虑的问题，以浪费一个空间为代价进行区分
// 判断队列是否为空
public boolean isEmpty() {
return first == last; // 队头指针与队尾指针相等时，队列为空
}
// 判断队列是否满
public boolean isFull() {
return (last + 1) % elem.length == first; // 队尾的下一个是队头时，队列为满
}双端队列
直接上图理解效果
双端队列（deque）是一种具有两端插入和删除操作的数据结构，即可以在队列的两端进行插入和删除元素。这种数据结构可以看作是既具备栈的特点，又具备队列的特点
所以双端队列所具备的方法也是二者兼备，可以用链式结构或顺序结构实现都可以哦~
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现使用 ArrayDeque作为线性实现：
import java.util.Deque;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 从栈顶弹出元素
System.out.println(stack.peek()); //查看栈顶元素但不弹出
}
}使用 LinkedList 作为链式实现：
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Deque<Integer> queue = new LinkedList<>();
// 在队尾添加元素
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);
System.out.println(queue.removeFirst()); //从队头移除元素
System.out.println(queue.peekFirst()); //查看队头元素但不移除
}
}栈和队列的相互转化
无论是如何转化，单靠一个是肯定不行的，所以肯定要有辅助栈或队列的
1.用队列模拟实现栈
用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/description/
思考：这道题是要咱用队列去模拟实现栈的功能，单单一个队列肯定不行，那就两个。一个做存储元素，一个来辅助。
class MyStack {
public Queue<Integer> queue1; // 第一个队列
public Queue<Integer> queue2; // 第二个队列
public MyStack() {
queue1 = new LinkedList<>(); // 初始化第一个队列
queue2 = new LinkedList<>(); // 初始化第二个队列
}首先入栈push()，如果两个队列都是空，直接默认放入存储元素的队列即可，而在一般情况下，谁不为空就放谁那里，毕竟不为空就意味着有元素已经放入，直接入即可。
// 将元素压入栈顶
public void push(int x) {
if(empty()){ // 如果栈为空，直接将元素加入第一个队列
queue1.offer(x);
}
else if (queue2.isEmpty()) { // 如果第二个队列为空，将元素加入第一个队列
queue1.offer(x);
} else { // 否则将元素加入第二个队列
queue2.offer(x);
}
}重点看出栈pop(),栈的特性是“先进后出”，用队列去模拟实现这个功能，对于要出栈的元素，要把栈中除了最后元素以外的所有元素都弹出到辅助栈中去接收，这段详细解释下~
因为栈出栈只能是栈顶元素，而队列的特性先进先出，于是栈顶元素以下的元素都可以弹出到辅助队列中去，原队列中剩下的最后一个元素便是栈顶元素
当然两个队列都要考虑，哪个是存储元素的，哪个又是辅助的。
// 弹出栈顶元素并返回
public int pop() {
if (empty()) {
return -1; // 如果栈为空，返回-1
}
if (!queue1.isEmpty()) {
int size = queue1.size();
for (int i = 0; i < size - 1; i++) { // 将 queue1 中除最后一个元素外的其他元素转移到 queue2 中
queue2.offer(queue1.poll());
}
return queue1.poll(); // 返回 queue1 中最后一个元素，即为栈顶元素
} else {
int size = queue2.size();
for (int i = 0; i < size - 1; i++) { // 将 queue2 中除最后一个元素外的其他元素转移到 queue1 中
queue1.offer(queue2.poll());
}
return queue2.poll(); // 返回 queue2 中最后一个元素，即为栈顶元素
}
}然后是top(),和pop()很类似，但并不移除，道理是一样的，只不过要把所有元素都弹出到辅助队列中去，于是要定义一个变量去存储最后一次弹出元素，那就是栈顶元素
// 返回栈顶元素但不弹出
public int top() {
if(empty()){
return -1; // 如果栈为空，返回-1
}
int ret = -1;
if(!queue1.isEmpty()){
int size = queue1.size();
for (int i = 0; i < size; i++) {
ret = queue1.poll(); // 将 queue1 中的元素逐个转移到 queue2 中，并记录最后一个元素
queue2.offer(ret);
}
return ret; // 返回 queue1 中的最后一个元素，即为栈顶元素
} else {
int size = queue2.size();
for (int i = 0; i < size; i++) {
ret = queue2.poll(); // 将 queue2 中的元素逐个转移到 queue1 中，并记录最后一个元素
queue1.offer(ret);
}
return ret; // 返回 queue2 中的最后一个元素，即为栈顶元素
}
}最后就是判断是否为空，这个最好写了，只要两个队列都是空，也就代表栈是空
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
2.用栈模拟实现队列
用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/
有了第一题的经验，这道题也好写了。模仿着来：
首先定义出两个队列，一个存储元素，一个进行辅助
class MyQueue {
public Stack<Integer> stack1; // 栈1
public Stack<Integer> stack2; // 栈2
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}然后是入队offer()，这个直接入存储元素的栈就行，这里就默认是stack1，这里还设置将栈2 的元素倒入栈1，这是为了保证栈1一直都是存储元素的栈：
public void push(int x) {
while (!stack2.isEmpty()) { // 将栈2中的元素倒入栈1
stack1.push(stack2.pop());
}
stack1.push(x); // 将新元素压入栈1
}出队poll()：因为其先进先出的特性，用栈模拟的时候弹出就是栈底元素，这个好办，直接把栈1的所有元素都倒入栈2去，然后直接去弹出栈2的栈顶元素，这样就移除成功了，最后别忘了把栈2的元素倒回栈1去，配合图片理解效果更佳~
public int pop() {
while (!stack1.isEmpty()) { // 将栈1中的元素倒入栈2
stack2.push(stack1.pop());
}
return stack2.pop(); // 弹出栈2顶部元素
}返回对头元素peek():这个和poll是一样的，只不过用变量接受就好
public int peek() {
while (!stack1.isEmpty()) { // 将栈1中的元素倒入栈2
stack2.push(stack1.pop());
}
int peek = stack2.peek(); // 获取栈2顶部元素但不弹出
while (!stack2.isEmpty()) { // 将栈2中的元素倒回栈1
stack1.push(stack2.pop());
}
return peek;
}判断是否为空也是一样empty()，直接上代码~
public boolean empty() {
return stack1.empty() && stack2.empty();
}这就是本篇文章的全部内容啦~如果觉得有收获的，希望可以点点赞支持下=V=！
