【数据结构】 栈和队列

一、栈

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

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);//45
        val = stack.pop();
        System.out.println(val);//34

        int val2 = stack.peek();//只获取，不删除
        System.out.println(val2);//23

        int val3 = stack.peek();//只获取，不删除
        System.out.println(val3);//23

        boolean 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：当前数组有多少个元素， 默认为0
    private 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);//45
        val = stack.pop();
        System.out.println(val);//34

        int val2 = stack.peek();//只获取，不删除
        System.out.println(val2);//23

        int val3 = stack.peek();//只获取，不删除
        System.out.println(val3);//23

        boolean 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 here
        Stack<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 添加元素12
        queue.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());//12
        System.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个队列都为空，放到qu1
            qu1.offer(x);
            return;
        }

        //有1个队列不为空
        if(!qu1.isEmpty()){//如果qu1不为空，放到qu1
            qu1.offer(x);
        }else{
            qu2.offer(x);
        }
    }

    //模拟出栈
    public int pop() {
        if(empty()){//栈本身是空的
            return -1;
        }

        if(!qu1.isEmpty()){//如果qu1不为空，放到qu1
            int 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();
    }
}