1. 栈

1.1 概念

• 栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
• 特点：栈中的数据元素遵循先进后出的原则，但要注意进的同时也可以出，元素不是要全部进展后才能出栈
• 栈顶：进行数据插入和删除操作的一端
• 栈底：栈顶的另一端
• 压栈：栈的插入操作就做进栈/压栈/入栈，入数据在栈顶
• 出栈：栈的删除操作就叫做出栈，出数据在栈顶

1.2 助解图题

助解图：

手枪的弹夹其实就类似是一个栈

当我们压子弹的时候，就是压栈

当我们上膛后，打枪时，就是出栈

助解题：

题一： 一个栈的入栈顺序是 a、b、c、d、e，该栈不可能的出栈顺序是（ ） A.edcba B.decba C.dceab D.abcde
结果为：C
*
题二： 中缀表达式为 a + b /* c + ( d /* e + f ) /* g，那么它的后缀表达式为什么？
结果为：a b c /* + d e /* f + g /* +

方法步骤（快捷方法）：

该方法中将括号的运算符移到括号前面得到的结果就是前缀表达式

本题背景：我们平常使用的表达式一般为中缀表达式，中缀表达式便于人们的理解与计算。而后缀表达式的运算符更方便计算机的运算（如二叉树、堆栈的方法计算）
*
题三： 通过栈返回后缀表达式 a b c /* + d e /* f + g /* + 计算的结果
结果为：a + b /* c + ( d /* e + f ) /* g

方法：当参数是数字时就压栈。当参数为运算符时，出栈第一个数作为运算符后的参数，出栈第二个参数作为运算符前的参数，将结果再压入栈中。

1.3 栈的数组实现

在 Java 中栈的底层其实是一个数组，并且它拥有压栈、出栈等等方法，借助这些我们来自己实现一个栈

public class MyStack{
    // 定义一个整型的数组，也可以直接使用泛型
    public int[] elem;
    // 定义数组已经使用的长度，初始时为0
    public int usedSize;
    // 创建 MyStack 的构造方法
    public MyStack(){
        // 用 Mystack 创建对象时初始化数组的长度为10
        this.elem=new int[10];
    }
    // 判断栈是否已满
    public boolean isFull(){
        return usedSize==this.elem.length;
    }
    // 压栈
    public int push(int val){
        if(isFull()){
            // 扩容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize++]=val;
        return val;
    }
    // 出栈
    public int pop(){
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        this.usedSize--;
        return this.elem[this.usedSize];
    }
    // 查看栈顶元素，不删除
    public int peek(){
        if(empty()){
        	throw new RuntimeException("栈为空");
        }
        return this.elem[this.usedSize-1];
    }
    // 判断栈是否为空
    public boolean empty(){
        return usedSize==0;
    }
}

1.4 问题

我们上述的栈是用数组实现的，入栈和出栈的时间复杂度都为 O(1)

那么栈能否用单链表实现呢？
*
使用头插法：入栈时间复杂度为 O(1)，出栈时间复杂度为 O(1)
*
使用尾插法：入栈时间复杂度为 O(N)，出栈时间复杂度为 O(N)

综上分析，栈可以通过单链表的头插头删法实现

1.5 栈的单链表实现

接下来将使用单链表实现栈，注意要使用头插头删法

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyStack{
    Node head=null;
    // 压栈
    public int push(int val){
        Node node=new Node(val);
        node.next = head;
        head = node;
        return head.val;
    }
    // 出栈
    public int pop(){
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        int val=head.val;
        head=head.next;
        return val;
    }
    // 查看栈顶元素，不删除
    public int peek(){
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        return head.val;
    }
    // 判断栈是否为空
    public boolean empty(){
        return head==null;
    }
}

2. 队列

2.1 概念

• 队列：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表。
• 特点：队列具有先进先出的特点
• 对头：进行删除操作的一端
• 队尾：进行插入操作的一段

2.2 问题

在我们实现队列前，要思考队列是靠数组实现呢还是拿链表实现呢？

在 Java 当中，队列是由 LinkedList 实现的，它的底层是一个双向链表。

• 对于双向链表：我们只要在尾节点进行入队操作，在头节点进行出队操作就很容易实现
• 对于单链表：我们只要增加一个尾巴节点，然后尾巴节点进行入队操作，头节点进行出队操作也能实现

至于数组，我们上述通过它实现了栈，而栈的特点其实是先进后出，与队列的先进先出原则矛盾。使用数组来实现队列会很麻烦。

2.3 队列的单链表实现

根据 Java 中队列的一些方法，接下来我们来实现自己的队列

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyQueueLinked {
    private Node front;
    private Node rear;
    private int usedSize;
    // 入队列
    public void offer(int val){
        Node node=new Node(val);
        if(this.front==null){
            this.front=node;
            this.rear=node;
        }else{
            this.rear.next=node;
            this.rear=node;
        }
        this.usedSize++;
    }
    // 出队列
    public int poll(){
       if(isEmpty()){
           throw new RuntimeException("队列为空");
       }
       int val=this.front.val;
       if(this.front.next==null){
           this.front=null;
           this.rear=null;
       }else{
           this.front=this.front.next;
       }
        this.usedSize--;
        return val;
    }
    // 得到队头元素不删除
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }else{
            return this.front.val;
        }
    }
    // 判断队列是否为空
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    // 得到队列长度
    public int size(){
        return this.usedSize;
    }
}

上述队列是用单链表实现的，也叫链式队列。大家也可以自行尝试一下双链表实现队列。

2.4 数组实现队列

假设现在我们用数组模拟入队列和出队列的模型

解决方法：

• 方法一：出队时，移动数组将后面的元素往前覆盖（时间复杂度为 O(N)）
• 方法二：使用循环的方法，实现循环队列（时间复杂度为 O(1)）

2.5 循环队列

循环队列即数组使用了循环的方式，让数组方便队列的入队和出队。那么怎么实现呢？模型如下

• front：指向的位置就是队列的头，既已经存放数据的第一个下标（删除数据一端）
• rear：指向的位置就是队列的尾巴，即可以存放数据的第一个下标（插入数据一端）

问题1：如何判断 front = rear 时是空还是满？

为了能够区别是空还是满，我们常假定当 front = rear 时为空。而对于满的话，我们则会将这个数组保留一个空的位置，那么当 rear+1 = front 时，则队列满了

问题2：当 front 在数组最后一个位置时，如何再移它到数组的第一个位置呢？

(下标+1)%数组长度

接下来让我们实现循环队列

public class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k){
        this.elem=new int[k+1];
    }
    // 判断队列是否满了
    public boolean isFull(){
        return (this.rear+1)%this.elem.length==this.front;
    }
    // 判断队列是否为空
    public boolean isEmpty(){
        return this.front==this.rear;
    }
    // 入队
    public void enQueue(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.rear]=val;
        this.rear=(this.rear+1)%this.elem.length;
    }
    // 出队
    public int deQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int val=this.elem[this.front];
        this.front=(this.front+1)%this.elem.length;
        return val;
    }
    // 得到队头元素
    public int getFront(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return this.elem[this.front];
    }
    // 得到队尾元素
    public int getRear(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear - 1];
    }
}

注意：

假设一个数组长度为3，做题时可能人家用例入队了3次，但是按照上述队列为满的方式，我们其实是保留了一个位置是不能存放数据的。因此对于这种题目我们可以将我们的数组开大一位

2.6 双端队列

双端队列：是指允许两端都可以进行入队和出队操作的队列
*
特点：元素可以从队头出队和入队，也可以从队尾出队和入队

双端队列较简单，可以使用双向链表实现，这里就展示一下双端队列的模型

3. 栈和队列练习题

3.1 有效的括号

题目（OJ 链接）：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

题解：使用栈，遍历字符串，是左括号就进行入栈，是右括号就与栈顶元素比较。

public boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char ch=s.charAt(i);
        switch(ch){
            case ')':
                if(stack.empty()||stack.pop()!='('){
                    return false;
                }
                break;
            case '}':
                if(stack.empty()||stack.pop()!='{'){
                    return false;
                }
                break;
            case ']':
                if(stack.empty()||stack.pop()!='['){
                    return false;
                }
                break;
            default:
                stack.push(ch);
                break;
        }
    }
    if(stack.empty()){
        return true;
    }
    return false;
}

3.2 用队列实现栈

题目（OJ链接）：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

题解：

由于队列是先进先出，栈是先进后出，故一个队列无法满足实现栈的能力。而使用两个队列，对于入栈，我们我只要找到栈不为空的队列进行入队就行；对于出栈，我们只要将不为空的队列的除最后一个入队的元素全部转移到另一个空队列中，再将留下的元素出队

代码：

class MyStack {
    private Queue<Integer> q1;
    private 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.offer(x);
        }
    }
    // 出栈
    public int pop() {
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                if(!q1.isEmpty()){
                    q2.offer(val1);
                }
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                if(!q2.isEmpty()){
                    q1.offer(val2);
                }
            }
            return val2;
        }
    }
    // 得到栈顶元素不删除
    public int top() {
        if(empty()){
            throw new RuntimeException("栈为空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                q2.offer(val1);
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                q1.offer(val2);
            }
            return val2;
        }
    }
    // 判断栈是否为空
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

3.3 用栈实现队列

题目（OJ 链接）：
请你仅使用两个栈实现先入先出队列。

题解：

我们可以创建两个栈 s1、s2，s1 用来入队，s2 用来出队

代码：

class MyQueue {
    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.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    // 返回队首元素，不删除
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    // 判断队列是否为空
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

3.4 实现一个最小栈

题目（OJ 链接）：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

题解：

我们可以创建两个栈，一个栈就是用来存储删除元素，另一个就是专门用来存储最小值的栈。注意这个最小值是存储该元素时该栈的最小值

代码：

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() {
        int val=stack.pop();
        if(minStack.peek()==val){
            minStack.pop();
        }
    }
    // 得到栈顶元素，不删除
    public int top() {
        return stack.peek();
    }
    // 得到此时栈的最小值
    public int getMin() {
        return minStack.peek();
    }
}

3.5 设计循环队列

题目（OJ 链接）：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

题解：

通过 (下标+1)%数组长度 的方式将数组形成一个循环，先设定好数组为空和为满的条件。注意防止题目将数组存满，开数组时的大小要注意。

代码：

class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elem=new int[k+1];
    }
    // 入队列
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.elem[rear]=value;
        this.rear=(this.rear+1)%this.elem.length;
        return true;
    }
    // 出队列
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.elem.length;
        return true;
    }
    // 得到队首元素，不删除
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.elem[front];
    }
    // 得到队尾元素，不删除
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear-1];
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return this.rear==this.front;
    }
    // 判断队列是否满了
    public boolean isFull() {
        return (this.rear+1)%this.elem.length==this.front;
    }
}