【数据结构】 栈和队列

一、栈

之前学习的 局部变量存储在栈中 ，这个栈 指的是 内存。
而现在学习的栈，指的是一种 数据结构，特点为：先进后出。

1.1 栈的概念

1.2 栈的使用

import java.util.Stack;public class Test {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);int val = stack.pop();//删除System.out.println(val);//45val = stack.pop();System.out.println(val);//34int val2 = stack.peek();//只获取，不删除System.out.println(val2);//23int val3 = stack.peek();//只获取，不删除System.out.println(val3);//23boolean empty =  stack.empty();//判空System.out.println(empty);//false}
}

1.3 栈的模拟实现

1.3.1 数组 模拟栈的实现（顺序栈）

import java.util.Arrays;
import java.util.Stack;public class MyStack {//数组模拟栈 的实现//push()：存储数据private int[] elem;private int usedSize;//usedSize：当前数组有多少个元素， 默认为0private static final int DEAULT_SIZE = 10;public MyStack(){elem = new int[DEAULT_SIZE];}public void push(int val){if(isFull()){grow(); //扩容}elem[usedSize] = val;usedSize++;}private void grow(){elem = Arrays.copyOf(elem,elem.length);}public boolean isFull(){return usedSize == elem.length;}//pop()：删除数据public int pop(){if(isEmpty()){//return -1;throw new StackEmptyException("栈为空异常！");}usedSize--;return elem[usedSize];}public boolean isEmpty(){return usedSize == 0;}//peek()：获取栈顶元素，但是不删除当前元素public int peek(){if(isEmpty()){//return -1;throw new StackEmptyException("栈为空异常！");}//usedSize--;return elem[usedSize - 1];}//size()public int size(){return usedSize;}
}

测试代码：

import java.util.Stack;public class Test {public static void main(String[] args) {MyStack stack = new MyStack();stack.push(12);stack.push(23);stack.push(34);stack.push(45);int val = stack.pop();//删除System.out.println(val);//45val = stack.pop();System.out.println(val);//34int val2 = stack.peek();//只获取，不删除System.out.println(val2);//23int val3 = stack.peek();//只获取，不删除System.out.println(val3);//23boolean empty =  stack.isEmpty();//判空System.out.println(empty);//false}

输出结果：

数组实现栈：入栈O(1)；出栈O(1)。

1.3.2 双向链表 模拟栈的实现（链式栈）

（1）单向链表 模拟栈（从头入栈，从头出栈）

• 入栈从头入，出栈从头出；可以保证入栈和出栈的时间复杂度为O(1)。
• 从链表的尾巴 入栈和出栈 不行，因为入栈可以做到O(1)，但是出栈还是O(n)。

（2）双向链表 模拟栈

• 无论从从头还是从尾，时间复杂度 都为O(1)。
  -== 双向链表（LinkedList）可以被当做 栈来使用 ==！

1.4 栈相关的 OJ题

1.4.1 逆波兰表达式求值 / 后缀表达式求值

（1）LC150：逆波兰表达式求值

（2）图解

• 中缀表达式 转换 后缀表达式推导：

• 利用栈进行转换：

（3）Java 代码实现

import java.util.Stack;class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();  for(int i = 0; i < tokens.length; i++){String s = tokens[i];if(!isOperation(s)){ Integer ret = Integer.valueOf(s);stack.push(ret);} else {  // 是运算符Integer val2 = stack.pop();Integer val1 = stack.pop();switch(s){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 isOperation(String val){ if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){return true;}return false;}
}

1.4.2 括号匹配

（1）LC20.有效的括号

（2）图解

（3）Java 代码实现

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{//ch = 右括号if(stack.isEmpty()){//4.字符串没有遍历完成，但是栈为空return false;}//拿到栈顶元素char peekCh = stack.peek();if( peekCh == '(' && ch == ')'|| peekCh == '{' && ch == '}'|| peekCh == '[' && ch == ']'){stack.pop();}else{return false;//2.左右括号不匹配}}}if(!stack.isEmpty()){//3.字符串遍历完成，但是栈当中不为空return false;}return true;}
}

1.4.3 出栈入栈次序匹配

（1）牛客链接：JZ31 栈的压入、弹出序列

（2）图解

（3）Java 代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/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]);while(!stack.isEmpty() && j < popV.length && stack.peek() == popV[j]){//栈不为空，j位置合法，取栈顶元素比较stack.pop();j++;}}return stack.isEmpty();}
}

1.4.4 最小栈

（1）LC155.最小栈

（2）图解

（3）Java 代码实现

class MinStack {Stack<Integer> stack;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{int peekMinVal = minStack.peek();if(val <= peekMinVal){minStack.push(val);}}}public void pop() {int val = stack.pop();if(val == minStack.peek()){minStack.pop();}}//peek()public int top() {return stack.peek();}//O(1)public int getMin() {return minStack.peek();}
}

二、队列

2.1 队列的概念

2.2 队列的使用

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

package queuedemo;import java.util.LinkedList;
import java.util.Queue;public class Test {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(12);//offer 添加元素12queue.offer(23);queue.offer(34);queue.offer(45);System.out.println(queue.poll());//12:poll 删除元素System.out.println(queue.peek());//23:peek 获取元素 不删除System.out.println(queue.isEmpty());//false}
}

2.3 队列的模拟实现

2.3.1 双向链表 模拟实现 队列（链式队列）

（1） 图解

• offer()

• poll()

（2）Java 代码实现

package queuedemo;public class MyQueue {static class Node {public int val;public Node prev;public Node next;public Node(int val) {this.val = val;}}public Node front;//队头：链表的头public Node rear;//队尾: 链表的尾巴public void offer(int val) { // offer(): 相当于尾插法Node node = new Node(val);if (front == null) {front = node;rear = node;} else {rear.next = node;node.prev = rear;rear = node;}}public int poll(){//删除元素if(front == null){return -1;}int val = front.val;front = front.next;//防止 只有一个节点if(front != null){front.prev = null;}else{rear = null;}return val;}public int size(){Node cur = front;int count = 0;while(cur != null){count++;cur = cur.next;}return count;}public int peek(){if(front == null){return -1;}return front.val;}
}

测试代码：

package queuedemo;import java.util.LinkedList;
import java.util.Queue;public class Test {public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer(12);queue.offer(23);queue.offer(34);queue.offer(45);System.out.println(queue.poll());//12System.out.println(queue.peek());//23}

2.3.2 数组 模拟实现 队列（循环队列）

（1）LC622.设计循环队列

（2）图解

（3）Java 代码实现

• 方法2：牺牲一个空间 实现循环队列

package queuedemo;// 方法2：牺牲一个空间 实现循环队列
public class MyCircularQueue {public int[] elem;public int front;public int rear;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;}//处理0下标位置int index = rear == 0 ? elem.length - 1: rear - 1;return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {if((rear + 1) % elem.length == front){return true;}return false;}
}

• 方法3：使用标记 实现循环队列

package queuedemo;//方法3：使用标记 实现循环队列
public class MyCircularQueue2 {public int[] elem;public int front;public int rear;public boolean isFull;//标记public MyCircularQueue2(int k) {elem = new int[k];isFull = false;}public boolean enQueue(int value) {//入队列 操作if(isFull()){return false;}elem[rear] = value;rear = (rear + 1) % elem.length;if(rear == front){isFull = true;}return true;}public boolean deQueue() {//出队列if(isEmpty()){return false;}front = (front + 1) % elem.length;isFull = false;return true;}public int Front() {//获取队首元素if(isEmpty()){return -1;}return elem[front];}public int Rear() {//获取队尾元素if(isEmpty()){return -1;}//处理0下标位置int index = (rear - 1 + elem.length) % elem.length;return elem[index];}public boolean isEmpty() {return !isFull && front == rear;}public boolean isFull() {return isFull;}
}

三、双端队列

3.1 双端队列的使用

• 双端队列（deque）是指允许两端都可以进行入队和出队操作的队列。
• 元素可以从队头出队和入队，也可以从队尾出队和入队。
• Deque是⼀个接口，使用时必须创建LinkedList的对象。

package queuedemo;import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;public class Test {public static void main(String[] args) {Deque<Integer> dequeue = new LinkedList<>();dequeue.offerFirst(12);dequeue.pollLast();Deque<Integer> stack = new LinkedList<>();stack.push(10);//数组实现的双端队列Deque<Integer> stack2 = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现}

3.2 双端队列 相关OJ题

3.2.1 用队列实现栈

（1） LC225.用队列实现栈

（2）图解

（3）Java 代码实现

package queuedemo_queue_eg;
//LC225.用队列实现栈
import java.util.LinkedList;
import java.util.Queue;public class MyStack {//首先 要有2个普通队列private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//模拟入栈public void push(int x) {if(empty()){//如果2个队列都为空，放到qu1qu1.offer(x);return;}//有1个队列不为空if(!qu1.isEmpty()){//如果qu1不为空，放到qu1qu1.offer(x);}else{qu2.offer(x);}}//模拟出栈public int pop() {if(empty()){//栈本身是空的return -1;}if(!qu1.isEmpty()){//如果qu1不为空，放到qu1int size = qu1.size();while(size -1 != 0){qu2.offer(qu1.poll());size--;}return qu1.poll();}else{int size = qu2.size();while(size -1 != 0){qu1.offer(qu2.poll());size--;}return qu2.poll();}}public int top() {if(empty()){//栈本身是空的return -1;}if(!qu1.isEmpty()){int size = qu1.size();int tmp = -1;while(size != 0){tmp = qu1.poll();qu2.offer(tmp);size--;}return tmp;}else{int size = qu2.size();int tmp = -1;while(size != 0){tmp = qu2.poll();qu1.offer(tmp);size--;}return tmp;}}//2个队列都是空 说明模拟的栈是空的public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

3.3.2 用栈实现队列

（1）LC232.用栈实现队列

（2）图解

（3）Java 代码实现

package queuedemo_queue_eg;
//LC232.用栈实现队列
import java.util.Stack;public class MyQueue {//至少需要2个栈private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(empty()) {//模拟的队列是空的return -1;}if(s2.isEmpty()) {//把s1这个栈 当中的所有数据 倒过来while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek(){if (empty()) {return -1;}if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}