一. 栈的概念及使用：
1. 概念： 栈一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守先进后出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈； 出栈 ： 栈的 删除操作叫做出栈 。 压栈和出栈出入数据都在栈顶。 如下图：
2 栈的使用 ：
代码：
代码语言：javascript复制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压栈方法：把元素压入栈中
代码语言：javascript复制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出栈方法：
代码语言：javascript复制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时 ， 后面的元素不会被覆盖 。
代码语言：javascript复制 //在不删除元素前提下获取栈顶元素
public int peek() {
if (isEmpty()) {
throw new ExceptionEmpty("栈是空的！！！");
}
int val = this.elem[this.usedSize-1];
//不用要减减
return val;
}二.栈的相关经典OJ
1. 最小栈： . - 力扣（LeetCode）
我画了超详细的图，帮助理解：
代码：
代码语言：javascript复制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.栈的压入、弹出序列：栈的压入、弹出序列_牛客题霸_牛客网
理解图：
代码：
代码语言：javascript复制//栈的压入、弹出序列
public boolean IsPopOrder (int[] pushV, int[] popV) {
// write code here
Stack<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 遍历完右括号，才是有效括号
代码：
代码语言：javascript复制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方法；尾插入队：
代码语言：javascript复制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方法：删除的前提下获取队列队头
代码语言：javascript复制 //删除前提下获取队列的队头
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方法：不删除的前提下获取队列队头
代码语言：javascript复制//不删除前提下获取队列的队头
public int peek() {
if (isEmpty()){
return -1;
}
return first.val;
}
public boolean isEmpty() {
return this.usedSize == 0;
// return fast == null;
}
}4.循环队列：
用顺序结构也可以 实现队列 ， 但是普通数组，会比较浪费空间 ，这里我们 让数组循环起来就不会浪费太多空间。这里我们叫它 循环队列。
设计循环队列的oj:. - 力扣（LeetCode）
这里也自己画了理解图：这里我们区分循环队列，是否为非空用了图里说的第三种方法。浪费一个空间
代码：
代码语言：javascript复制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方法时，定义一个中间变量这些细节，如图：
代码：
代码语言：javascript复制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）
图解：定义两个栈做到 "先进先出"，主要就是通过两个栈把栈里的元素反过来，
代码：
代码语言：javascript复制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全部元素放入stack2
while(!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();
*/
