---

---

一、栈

栈说白了就是一个盒子，你先放进去的东西后拿出来，实现栈除了可以使用栈的类Stack外，还可以使用链表
遵循先进先出，后进后出原则进行内容变化，重点是可以把递归转换成栈
我们查看其源码我们看到，它实质上是一个顺序表即数组，有压栈和出栈操作

1. 模拟实现栈

这次我们就不定义接口了，就直接写MyStack类吧，然后实现一些方法
我们重点就来讲压栈和出栈，压栈说白了就是先检测你的数组有没有满，满了就扩容，否则我们就直接让有效元素个数对应的下标的数字等于我们压入的数字（因为数组下标和实际位置差1的特性）
出栈就是先判断数字是不是空的，如果不是我们直接让有效数字个数减少，这样我们再次压入其他数字的时候就可以把原有数字覆盖
其他方法操作下来，我们的时间复杂度都是O(1)

//MyStack类
public class MyStack {public int [] elem;public int usedSize;public MyStack() {this.elem = new int[2];}public void push(int val) {if (isFull()) {this.elem = Arrays.copyOf(elem, 2 * elem.length);}elem[usedSize] = val;usedSize++;}public boolean isFull() {return usedSize == elem.length;}public int pop(){if(isEmpty()){throw new IsEmptyException("空数组异常");}int ret = peek();usedSize --;return ret;}public boolean isEmpty(){return usedSize == 0;}public int peek(){if(isEmpty()){throw new IsEmptyException("空数组异常");}return elem[usedSize-1];}public int size(){if(isEmpty()){throw new IsEmptyException("空数组异常");}return usedSize;}@Overridepublic String toString() {return "MyStack{" +"elem=" + Arrays.toString(elem) +", usedSize=" + usedSize +'}';}
}//测试类
public static void main(String[] args) {MyStack myStack = new MyStack();System.out.println("压栈");myStack.push(10);myStack.push(12);myStack.push(15);System.out.println(myStack);System.out.println("查看栈顶元素："+myStack.peek());System.out.print("出栈：");System.out.print(myStack.pop()+" ");System.out.print(myStack.pop()+" ");System.out.print(myStack.pop());System.out.println();System.out.println("栈顺序"+myStack);Stack<Integer> stack = new Stack<>();}

打印结果就是这样，看起来一切正常

2. 小试牛刀

1. 判断一个栈的出栈顺序是否为题目给定情况

题目链接
我们首先来讲讲这道题的核心思想是什么，根据题目要求
我们让i下标等于pushV，j下标等于popV
我们就以：pushV：1 2 3 4 5 和popV：4 3 5 1 2来讲解
我们先定义一个栈，叫stack，把右侧看做栈顶
好，我们定义好了i下标和j下标，此时它们分别代表数字1和数字4
我们比较i下标的数字和j下标数字是否匹配，发现不匹配，将i下标当前指向的元素放入栈中，此时我们得栈数字有[1]，此时我们得i下标++，发现还是和j下标数字不匹配，继续放元素到栈中，继续++
直到[1,2,3,4]，发现栈中的栈顶元素为4，和j下标元素匹配，那好，我们就弹出栈顶元素4，此时栈中元素为[1,2,3]，此时j下标++向后走，走到数字3位置，此时我们再判断，栈中元素是空的吗，不是，我们还要继续判断相等，此时我们我们发现栈顶元素3和j下标当前的数字3匹配，我们栈顶元素继续弹出，k++一下向后走，走到数字5的位置，此时栈中元素为[1,2]
此时再判断，栈中元素是空的吗，不是，那我们还要继续判断相等，此时这一轮循环走完了，我们的i要++一下，走到数字5的位置，此时栈顶元素是2，和当前j下标的数字不一样，那我们是不是继续要从pushV中放数字，好，我们放入数字5，此时栈中元素为[1,2,5]，栈顶元素和此时j下标的元素相等，我们此时弹出栈顶元素，此时j++向后走一位，走到1的位置，此时栈中元素为[1,2]，此时栈顶元素和j下标并不匹配，这一轮循环走完，i++了一下，此时i就超过了原来的数组范围，大的循环走了出来，此时我们判断栈中是否还存有元素，发现还是有元素，那我们就可以知道“4 3 5 1 2”这个出栈顺序就不是原有合理顺序
如果出栈顺序是这样popV：4 5 3 2 1 ，一样的逐一的进行判断，发现最后栈是空的，那它就是和题目要求成立
但是有个特殊情况，比如这样：如果每个都匹配的情况 5 4 3 2 1 和 1 2 3 4 5
那内部进行判断的时候我们就要加上限制条件栈不可以为空并且j位置不能超过原数组范围，因为此时下标出了数组范围再取元素就空数组异常了，i不用判断是因为i有循环进行范围约束而j却没有

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack <Integer> stack = new Stack<>();int i = 0;int j = 0;for(i = 0;i<pushV.length;i++){//大循环stack.push(pushV[i]);//还要考虑如果每个都匹配的情况 5 4 3 2 1 和 1 2 3 4 5while(!stack.empty() && j<= popV.length && stack.peek() == popV[j]){//内部循环stack.pop();j++;}}//看看stack空不空就行了return stack.empty();}
}

2. 括号匹配

题目链接
这个题目核心问题就是如何去直到括号在哪以及括号的个数的问题
我们就拿( [ ] )举例，我们定义一个栈，把左括号存到里面去，栈中元素和右括号进行匹配，如果相等则弹出栈顶元素，以此类推，如果在弹出过程中第一次遇到不匹配的情况，不要犹豫直接返回false，肯定不是匹配了的
我们再拿(( )情况举例，如果右括号你都匹配完了左括号还有剩余，那也是不匹配
还有( ))情况，左括号遍历完了右括号还有剩余，也是不匹配

class Solution {public boolean isValid(String s) {Stack <Character> stack = new Stack<>();for(int i = 0 ;i<s.length();i++){//取出字符char ch = s.charAt(i);if(ch == '(' || ch == '{' || ch == '['){stack.push(ch);}else{//判空if(stack.empty()){return false;}//比较char chs = stack.peek();if(chs == '(' && ch == ')' || chs == '{' && ch == '}' || chs == '[' && ch == ']'){stack.pop();}else{//说明剩下的右边的元素根本就不是括号，可能是其他字符//比如((??这样return false;}}}//如果此时for循环走完了你的栈中还有元素，也就是说没有匹配完if(!stack.empty()){return false;}//当上述所有条件头部满足，说明就删完了，匹配成功return true;}
}

3. 逆波兰表达式求值

题目链接
我们首先明白什么是逆波兰表达式，我们正常的表达式是这样的，比如2*(3+5)
但是计算机的计算器在计算的时候是不知道我们人类的运算符优先规则去算的，那是怎么搞的呢
你看，逆波兰表达式核心就是把符号往后移，看我演示
设$M=(3+5)$，则M的逆波兰表达式为$35+$，之后整体式子的逆波兰表达式是$ 2M* $，带入M后就是$2 35+ * $，那此时计算就是$ 3+5=8 $，再$2\ast 8=16$
画图就是这样的

那我们直接来写题吧

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for(int i = 0;i<tokens.length;i++){if(!isOperator(tokens[i])){stack.push(Integer.parseInt(tokens[i]));}else{//注意两个数的出栈顺序int num1 = stack.pop();int num2 = stack.pop();switch(tokens[i]){case "+"://算出的结果要压入栈中stack.push(num2+num1);break;case "-":stack.push(num2-num1);break;case "*":stack.push(num2*num1);break;case "/":stack.push(num2/num1);break;}}}return stack.pop();}private boolean isOperator(String operator){if(operator.equals("+")||operator.equals("-")||operator.equals("*")||operator.equals("/")){return true;}return false;}
}

4. 求最小栈元素

题目链接
就是要求栈中最小的元素，因为栈不可以倒着遍历，因此我们只能用两个栈，一个普通栈存数字，另一个最小值栈存放当前栈中最小数字
当我不断的压普通栈，如果压的数字有比当前存放最小值的栈的栈顶元素小的话，最小值的栈顶元素就变成当前压入普通栈大的元素
这样当我普通栈出栈的时候，如果比我最小栈栈顶元素一样，那就一起出，否则就只是普通栈出
这样当我后续删除普通栈元素时，每一次都能在最小栈中找到当前普通栈中的最小值

class MinStack {private Stack<Integer> stack;private 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{//只有当压入普通栈的元素比最小值栈的栈顶元素小的时候//此时压入普通栈的数字才要同时压入最小值栈if( val <= minStack.peek()){minStack.push(val);}}}public void pop() {//判空if(stack.empty()){return;}//如果普通栈栈顶元素和最小值栈栈顶元素相等，要一起弹出int val = stack.pop();if(val == minStack.peek()){minStack.pop();}}public int top() {//判空if(stack.empty()){return -1;}return stack.peek();}public int getMin() {return minStack.peek();}
}

3. 单链表实现栈

入栈我们采用头插法，出栈我们采用删除头节点方法，此时它们时间复杂度都是O(1)
假如你入栈采用尾插法，还要遍历去找尾巴，麻烦，时间复杂度是O(n)
假如你对单链表的尾节点加上last引用，入栈没问题了可是你出栈还不是要删除尾节点，还不是要找其前一个节点，时间复杂度还是O(n)
但是，如果你采用双向链表，就可以实现，而且双向链表本身就有实现Deque接口，我们说过这是跟栈和队列有关的接口

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

使用双向列表，我们就能保证出栈和入栈的时间复杂度都是O(1)

二、队列

这个定义说白了就跟我们排队一样的，遵循先进先出后进后出
只不过分为普通队列和双端队列
普通队列是Queue类，而双端队列则是Deque类

当然，我们之前有讲过，链表可以实现栈和队列，那对于单链表如果去实现队列
你给单链表的尾节点添加了Last引用，此时尾插法入队和头删法出队时间复杂度都是O(1)没有问题，但是反之头插法入队和尾删法出队还是得知道尾节点的前驱节点，时间复杂度还是O(n)

1. 官方队列类Queue

我们通过双向链表创建Queue类Queue <Integer> queue = new LinkedList<>();

以下是各个方法测试

public static void main(String[] args) {Queue <Integer> queue = new LinkedList<>();System.out.println("入队");queue.offer(15);queue.add(10);System.out.println("出队");System.out.println(queue.poll());System.out.println(queue.remove());System.out.println("再次出队，各个方法情况");System.out.println("不会抛出异常"+queue.poll());System.out.println("抛出异常"+queue.remove());System.out.println("查看队头元素，各个方法情况");System.out.println("不会抛出异常"+queue.peek());System.out.println("会抛出异常"+queue.element());}

关于入队、出队以及查看队头元素，都有各自的两种方法，它们区别就是安全性问题
对于使用add、remove和element方法会抛出异常，而offer、poll和peek则不会，因此我们从安全性原则上去讲，更推荐offer、poll和peek方法

2. 双向链表模拟实现Queue类

入队就采用尾插法，出队就采用头删法，查看队头元素直接返回头节点的数值

public class MyQueue {static class LinkedList{public int value;public LinkedList nextAddress;public LinkedList previousAddress;public LinkedList(int value) {this.value = value;}}public LinkedList head;public LinkedList last;public int usedSize;//入队-->尾插法，遵循源码public void offer(int data){LinkedList node = new LinkedList(data);if(head == null){head = last = node;}else{last.nextAddress = node;node.previousAddress = last;last = node;usedSize++;}}//出队-->头删法public int poll(){if(head == null){throw new QueueEmptyException("空队列异常");}int val = head.value;if(head.nextAddress == null){head = last = null;}else{head = head.nextAddress;head.previousAddress = null;usedSize--;}return val;}//查看队头情况public int peek(){if(head == null){throw new QueueEmptyException("空队列异常");}return head.value;}public int size(){return usedSize;}public boolean isEmpty(){return head == null;}public void display(){LinkedList current = head;while(current != null){System.out.print(current.value+" ");current = current.nextAddress;}}
}//自定义异常QueueEmptyException类
public class QueueEmptyException extends RuntimeException{public QueueEmptyException() {}public QueueEmptyException(String message) {super(message);}
}//测试用例
public static void main(String[] args) {MyQueue myQueue = new MyQueue();System.out.println("入队方法测试");myQueue.offer(10);myQueue.offer(15);myQueue.offer(22);myQueue.offer(30);myQueue.display();System.out.println();System.out.println("出队方法测试");System.out.print(myQueue.poll()+" ");System.out.print(myQueue.poll()+" ");System.out.println();System.out.println("获取队头元素方法测试");System.out.print("队列情况：");myQueue.display();System.out.println();System.out.print("出队：");System.out.println(myQueue.peek());System.out.print("获取大小：");System.out.println(myQueue.size());System.out.print("判空：");System.out.println(myQueue.isEmpty());}

最中效果如下

3. 顺序表模拟实现Queue类

顺序表会有一种情况，首先我定义队头指针front和队尾指针rear，我每添加一个元素我的rear就往后走，直到到达边界，走到末尾我们循环回到开头，好，此时我要出队出一些元素，此时我的front向后走了几步，我此时再想放元素发现“满了”
但真的满了吗，我不是刚刚才出队几个元素没，诶，这就是数组的假溢出，因为你的rear队尾指针走到头了会误以为满了

Q1：还有，我们不是定义了队头队尾指针吗，你想我们开始为空的时候它们会在一起，数组满了的时候它们也会在一起，如何区分呢
Q2：其次，我们既然要实现循环队列，如何实现呢

• 解法一：添加size属性标记
• 解法二：开始为空的时候我们标记成false，每一次入队我们检查front是否重合，如果重合就标记成true否则我们就正常添加元素
• 解法三：每一次存放数据的时候检查rear的下一个是不是front，如果是我们就可以认为满了，不能再放入元素

---

那如何从数组后面跳到前面呢，我们先来讲讲偏移量概念
如果你想从数组前面到达后面，我们就要(index+array.length-偏移量)%array.length
如果你想从数组后面到达前面，我们就要(index+偏移量)%array.length
偏移量指的就是你和你目标举例多远，比如4下标距离5下标距离是1，假如数组大小是4则3下标举例0下标距离也是1

---

我们采用解法三去实现，这里给出一道相关的题题目链接

class MyCircularQueue {public int [] array;public int front;//头public int rear;//尾 public MyCircularQueue(int k) {//示例中给三个能够从一下标获取元素，说明至少需要k+1个空间array = new int[k+1];}public boolean enQueue(int value) {if(isFull()){return false;}this.array[rear] = value;//不可以直接rear++，否则越界rear = (rear+1)%array.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front = (front+1)%array.length;return true;}public int Front() {if(isEmpty()){return -1;}return array[front];}public int Rear() {if(isEmpty()){return -1;}//此时还要判断rear的位置，如果是0说明满了回到了开头//否则没有满就返回下标前一个数if(rear == 0){return array[array.length-1];}else{return array[rear-1];}}public boolean isEmpty() {if(rear == front){return true;}return false;}public boolean isFull() {if((rear+1)%array.length == front){return true;}return false;}
}

4. 双端队列

现在不管从哪边入队和出队都可以了
而且我们看到Deque源码中有peek和poll方法，证明其可以实现栈
而且还有数组型栈ArrayDeque，它也可以作为队列

public static void main(String[] args) {Deque<Integer> deque = new LinkedList<>();deque.addFirst(11);deque.addFirst(22);deque.addLast(33);System.out.println(deque);System.out.print(deque.pollFirst()+" ");System.out.println(deque.pollLast());System.out.println("===实现栈===");Deque<Integer> deque1 = new LinkedList<>();deque1.push(11);deque.push(22);deque1.push(33);System.out.println(deque1);System.out.println("查看栈顶元素："+deque1.peek());System.out.println("弹出栈顶元素："+deque1.poll());System.out.println(deque1);System.out.println("===数组实现双端栈===");Deque<Integer> deque2 = new ArrayDeque<>();deque2.push(11);deque2.push(55);deque2.push(88);System.out.println(deque2);System.out.println("查看栈顶元素："+deque2.peek());System.out.println("弹出栈顶元素："+deque2.poll());System.out.println(deque2);System.out.println("===数组实现队列===");Deque<Integer> deque3 = new ArrayDeque<>();deque3.addFirst(42);deque3.addFirst(55);deque3.addLast(99);System.out.println(deque3);System.out.println("查看栈顶元素："+deque3.peek());System.out.println("弹出栈顶元素："+deque3.poll());System.out.println(deque3);}

5. 队列实现栈

题目链接
我们这道题要使用两个队列，因为你的队列是先进先出，而栈是先进后出，因此要有另一个队列存出栈元素
怎么个出法呢？假设刚开始两个队列都为空，则我们默认把数字依次放入队列一queue1中
下一次再放元素的时候哪一个队列不是空的我们就放进哪个队列中
出元素时，我们看哪一个队列不是空的，我们就出除了出队元素以外的元素

还有后续获取“栈顶元素”时候，我们要定义一个中间变量temp，每次从一个栈中弹出元素的时候我们就把数字放在里面，直到最后一次弹出的数字就是我们想要的队头元素

class MyStack {private Queue<Integer> qu1;//我用简写表示queue1private Queue<Integer> qu2;//同理public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(qu2.isEmpty()){//qu2空qu1.offer(x);}else if(qu1.isEmpty()){//qu1空qu2.offer(x);}else{//同时为空qu1.offer(x);}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}public int pop() {if(empty()){return -1;}if(qu1.isEmpty()){int size = qu2.size();while(size-1 != 0){qu1.offer(qu2.poll());size--;}return qu2.poll();}else if(qu2.isEmpty()){int size = qu1.size();while(size-1 != 0){qu2.offer(qu1.poll());size--;}return qu1.poll();}return -1;}public int top() {if(empty()){return -1;}if(qu1.isEmpty()){int temp = 0;int size = qu2.size();while(size != 0){temp = qu2.poll();qu1.offer(temp);size--;}return temp;}else if(qu2.isEmpty()){int temp = 0;int size = qu1.size();while(size != 0){temp = qu1.poll();qu2.offer(temp);size--;}return temp;}return -1;}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

6. 栈实现队列

我们刚刚使用两个队列实现栈，那现在也要用两个栈实现队列
入队我们默认放在第一个栈中，因为栈顺序是先进后出的，因此我们再把第一个栈的元素放入第二个栈中，此时第二个栈的栈顶元素即出队元素
如果第二个栈没有数据，则先把第一个栈的所有元素拿过来

class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

---

文章错误不可避免，期待您的指正，我们共同进步

---

---

END