目录：
一. 栈的概念及使用
二.栈的相关经典OJ
三. 队列的概念及使用
二. 队列的相关经典OJ
一. 栈的概念及使用：
1. 概念： 栈一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守先进后出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈； 出栈 ： 栈的 删除操作叫做出栈 。 压栈和出栈出入数据都在栈顶。 如下图：
2 栈的使用 ：
代码：
public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
} 3 栈的模拟实现：
1. 注意：这里的peek方法是获得；栈顶元素，当再 push时 ， 后面的元素不会被覆盖 。而
(1)push压栈方法：把元素压入栈中
public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}//压栈public void push(int val) {if (isFull()) {this.elem = Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize++] = val;}(2)pop出栈方法：
public boolean isFull() {return this.usedSize == elem.length;}//判空public boolean isEmpty() {return this.usedSize == 0;}//出栈->获取栈顶元素，并且元素可以被覆盖public int pop() {if (isEmpty()) {throw new ExceptionEmpty("栈是空的！！！");}int val = this.elem[this.usedSize-1];this.usedSize--;//要减减，为后续push可以覆盖元素return val;} （3） peek方法 获取栈顶元素： 后面 再push时 ， 后面的元素不会被覆盖 。
//在不删除元素前提下获取栈顶元素public int peek() {if (isEmpty()) {throw new ExceptionEmpty("栈是空的！！！");}int val = this.elem[this.usedSize-1];//不用要减减return val;} 二.栈的相关经典OJ
1. 最小栈： . - 力扣（LeetCode）
我画了超详细的图，帮助理解：
代码：
class MinStack {public Stack<Integer> minStack;public Stack<Integer> stack;public MinStack() {minStack = new Stack<>();stack = 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 popVal = stack.pop();//普通栈出栈//最小栈出栈if(popVal == minStack.peek()) {minStack.pop();}}//获取普通栈的栈顶元素public int top() {if(stack.empty()) {return -1;}return stack.peek();}//获取最小栈的栈顶元素public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/2.栈的压入、弹出序列：栈的压入、弹出序列_牛客题霸_牛客网
理解图：
代码：
//栈的压入、弹出序列public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);/*** 这里注意stack.peek() == popV[j]，不能写入while循环，不然栈顶元素和popV元素，* 不相等，会一直死循环i不会加加，就没法压入pushV的下一个元素*///注意压栈的同时，和popV[j]比较，不相同借助for循环继续往后压栈while(!stack.empty() && j < pushV.length &&stack.peek() == popV[j]) {stack.pop();j++;}}return stack.empty();}
}
3.逆波兰表达式求值：. - 力扣（LeetCode）
图解：
class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();//遍历字符串for(String str : tokens) {if(!isOperator(str)) {//是字符转为数字，放入栈中int x = Integer.parseInt(str);//字符转为数字stack.push(x);}else {//是操作符，就拿出来两个操作数计算int val2 = stack.pop(); int val1 = stack.pop();switch(str) {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();}private boolean isOperator(String ch) {if(ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")) {return true;}return false;}
} 4. 括号匹配： . - 力扣（LeetCode）
这题画图是关键主要三种情况：要同时，满足栈为空并且 i 遍历完右括号，才是有效括号
代码：
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 {//情况1.栈为空，但是i没有遍历完,右括号多if(Stack.empty()) {return false;}//这里开始比较括号匹不匹配//情况2.（括号顺序不对），刚开始比较第一个括号就不匹配if(Stack.peek() == '[' && ch == ']' || ch == ')'&& Stack.peek() == '(' || ch == '}' && Stack.peek() == '{' ) {Stack.pop();} else {return false;}}} //情况3.栈不为空，虽然i遍历完了，（左括号多）if(!Stack.empty()) {return false;}return true;}
} 三. 队列的概念及使用：
1. 概念 ：
队列 只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2 队列的使用：
在 Java 中， Queue 是个接口， 底层是通过链表实现 的。
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现 Queu接口。
3. 队列模拟实现：队列的实现，可以使用 顺序结构和链式结构 ，这里我们双链表实现，时间复杂度是O（1）很方便。
offer方法；尾插入队：
public class MyQueue {static class ListNode {public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode first = null;public ListNode last = null;public int usedSize;public void offer (int val) {ListNode node = new ListNode(val);if (isEmpty()) {last = first = node;}else {//尾插last.next = node;node.prev = last;last = last.next;}this.usedSize++;} poll方法：删除的前提下获取队列队头
//删除前提下获取队列的队头public int poll() {if (isEmpty()){return -1;}int ret = first.val;first = first.next;//只删剩一个节点时，空没有prev！if(first != null) {first.prev = null;}this.usedSize--;return ret;}peek方法：不删除的前提下获取队列队头
//不删除前提下获取队列的队头public int peek() {if (isEmpty()){return -1;}return first.val;}public boolean isEmpty() {return this.usedSize == 0;
// return fast == null;}
} 4.循环队列：
用顺序结构也可以 实现队列 ， 但是普通数组，会比较浪费空间 ，这里我们 让数组循环起来就不会浪费太多空间。这里我们叫它 循环队列。
设计循环队列的oj:. - 力扣（LeetCode）
这里也自己画了理解图：这里我们区分循环队列，是否为非空用了图里说的第三种方法。浪费一个空间
代码：
class MyCircularQueue {public int Rear;public int Front;public int[] elem;public MyCircularQueue(int k) {elem = new int[k+1];}//入队列public boolean enQueue(int value) {if(isFull()) {return false;}elem[Rear] = value;Rear = (Rear+1) % elem.length;return true;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}Front = (Front+1) % elem.length;return true;}//不删除获取队头public int Front() {if(isEmpty()) {return -1;}return elem[Front];}//获取队尾public int Rear() {if(isEmpty()) {return -1;}//Rear是插入元素遍历数组的下标int index = ((Rear == 0) ? (elem[elem.length-1]) : (elem[Rear-1]));return index;}public boolean isEmpty() {return Rear == Front;}public boolean isFull() {return (Rear+1) % elem.length == Front;}}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/二. 队列的相关经典OJ：
1. 用队列实现栈 ：. - 力扣（LeetCode）
图解：主要就是定义两个队列做到 "先进后出"，这里注意入栈和出栈操作，和写peek方法时，定义一个中间变量这些细节，如图：
代码：
class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}//模拟入栈public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()) {q2.offer(x);}else {//q1或者q2都为空，就任意放一个q1.offer(x);}}//模拟出栈public int pop() {if(empty()) {return -1;}else if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size-1; i++) {q2.offer(q1.poll());}return q1.poll();}else {int size = q2.size();for(int i = 0; i < size-1; i++) {q1.offer(q2.poll());}return q2.poll();}}//模拟获取栈顶元素public int top() {if(empty()) {return -1;}else if(!q1.isEmpty()) {int size = q1.size();//定义一个中间变量，把一个栈的元素经过中间变量// 全部放入另一个栈中，最后返回，最后经过中间变量的元素int val = 0;for(int i = 0; i < size; i++) {val = q1.poll();q2.offer(val);}return val;}else {int size = q2.size();int val = 0;for(int i = 0; i < size; i++) {val = q2.poll();q1.offer(val);}return val;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}/*** 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();*/ 2. 用栈实现队列: . - 力扣（LeetCode）
图解：定义两个栈做到 "先进先出"，主要就是通过两个栈把栈里的元素反过来，
代码：
class MyQueue {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueue() {stack1 = new ArrayDeque<>();stack2 = new ArrayDeque<>();}//模拟实现入队public void push(int x) {//把与元素全部放入stack1中stack1.push(x);}//模拟实现出队public int pop() {//因为是用栈模拟实现队列，所以判断一下，//如果两个栈为空，那么整个队列就为空if(empty()) {return -1;}//走到这里，stack1 不为空，stack2为空if(stack2.isEmpty()) {//不为空就把stack1全部元素放入stack2，达到元素逆置效果while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}//模拟实现获取队列队头元素（思路和模拟实现出队差不多，只是最后是eek）public int peek() {//因为是用栈模拟实现队列，所以判断一下，//如果两个栈为空，那么整个队列就为空if(empty()) {return -1;}//走到这里，stack1 不为空，stack2为空if(stack2.isEmpty()) {//不为空就把stack1全部元素放入stack2while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}/*** 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();*/ 
