数据结构之栈和队列_数据结构栈

线性表的定义

前面文章有讲过，线性表就是一次保存单个同类型元素，多个元素之间逻辑上连续

例子：数组，栈，队列，字符串

一、栈

1.1 栈和队列的特点

栈和队列都是操作受限的线性表。

前面学过的数组，链表，是可以菜任意位置插入和删除的

而栈和队列只能在一端插入元素和删除元素

1.2 栈的定义

只能在一段插入元素，也只能从这一段取出元素（栈顶）

从上图可以看出，入栈顺序时A->B->C，出栈顺序是C->B->A。栈顶的元素最先出栈，这与入栈的顺序刚好相反。也就是说：栈是LIFO（Last In First Out，后进先出的）。

栈的实际应用也很多：操作系统的函数调用、各类编辑器的撤销操作的实现都离不开栈。

1.3 栈的实现

顺序栈

顺序栈用数组实现,我们之前知道了动态数组 ArrayList，实际上用数组实现栈，就是将数组的增、删操作限制在头部或者尾部，即只能在数组的一端操作元素，就成了顺序栈。

栈的常用操作

栈的实现代码

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

//这里是从尾部入栈出栈，感兴趣的可以试试从头部入栈出栈
public class Mystack<E> {
    //记录栈中元素个数
    private int size;
    //实际存储数据的动态数组
    private List<E> data = new ArrayList<>();

    /**
     * 向栈中添加元素
     * @param val
     */
    public void push(E val){
        //在数组插入元素-尾插
        data.add(val);
        size ++;
    }

    /**
     * 出栈
     */
    public E pop(){
        if (isEmpty()){
            throw new NoSuchElementException("栈为空，无法弹出");
        }
        //弹出数组末尾的元素
        //List的remove方法会返回删除的值，我们只要接收就好了
        E oldVal = data.remove(size - 1);
        size --;
        return oldVal;
    }

    private boolean isEmpty() {
        return size == 0;
    }

    /**
     * 查看栈顶元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("栈为空");
        }
        //栈顶元素就是数组最后一个元素
       return data.get(size - 1);
    }

    @Override
    public String toString() {
      //拼接字符串
      StringBuilder sb = new StringBuilder();
      sb.append("(栈顶)[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if (i != size - 1){
                sb.append(",");
            }
        }
        sb.append("](栈顶)");
      return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

1.4 栈的小练习

LeetCode20-有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

输入：s = “{[]}”
输出：true

思路:一般判断题，最好的方法就是找反例，只要有一对括号不匹配，就返回false

利用栈这个结构

遍历这个字符串，将左括号入栈，当遍历到右括号的时候，左括号出栈看是否匹配。当遍历完整个字符串并且栈为空的时候，可以说明括号全都匹配上了，返回true。

这里判断栈为空是因为有左括号个数大于右括号个数的情况，这样遍历完了，栈内还会剩余左括号，无法闭合。最极端的情况是给的字符串全是左括号。

还有一种极端情况，当给的字符串全是右括号的时候，栈为空，也返回false。

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 {
             //遇到了右括号，弹出匹配
            //字符全是右括号，栈也为空
            if (stack.isEmpty()){
                //第一个就遇到了右括号，没办法闭合
                return false;
            }
            //栈不为空，说明有左括号，进行匹配
            //弹出栈顶元素
            char top = stack.pop();
            //找反例
            if (ch == ')' && top != '('){
                return false;
            }
            if (ch == ']' && top != '['){
                return false;
            }
            if (ch == '}' && top != '{'){
                return false;
            }
        }
    }
    //栈不为空就是左括号大于右括号的情况
    return stack.isEmpty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

思路：对于栈的问题，常用套路可以用双栈，既然题目要求要直接找到最小值，那不妨创建一个栈专门用来放最小值s2，另一个栈用来存放实际入栈元素s1。需要注意，这两个栈的入栈和出栈操作都是要同步的，否则会造成s2栈空了，s1还有元素的情况，这样就找不到最小值了。

核心：1. 当s2为空，元素直接入栈

2. 当s2的栈顶元素 > 当前元素，元素直接入栈
3. 当s2的栈顶元素 < 当前元素,将s2栈顶元素重新入栈一次（s1和s2的元素个数须保持一致）

图示

class MinStack {
    //存放实际保存的元素
    Stack<Integer> s1 = new Stack<>();
    //栈顶存放最小值
    Stack<Integer> s2 = new Stack<>();
    public MinStack() {}

    public void push(int val) {
        s1.push(val);
        if (s2.isEmpty()){
            s2.push(val);
        } else {
            //记录s2栈顶的值
            int peek = s2.peek();
            //比较大小
            s2.push(Math.min(val,peek));
        }
    }

    public void pop() {
        s1.pop();
        s2.pop();
    }

    public int top() {
        return s1.peek();
    }

    public int getMin() {
        return s2.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二、队列

FIFO,先进先出的数据结构，元素从队尾添加到队列中，元素从队首出队列。像排队一样

队列的常用方法

图示

2.1 队列的分类

队列有很多子类，比如普通FIFO队列，双端队列Deque，循环队列LoopQueue，优先级队列PriorityQueue

2.2 队列的实现

队列也有数组和链表两种实现方法，这里使用链表实现。原因是采用数组的方案，每次出队一个元素后面的元素就要向前移动一个单位，所以链表更适合队列的结构。

核心：

出队列：删除头节点

入队列：在链表尾部添加元素

/**
 * 队列的实现子类比较多，所以创建一个接口，所有子类都要实现这个接口
 */
public interface Queue<E> {
    //入队列
    void offer(E val);
    //查看队首元素
    E peek();
    //出队列
    E poll();
    //判断是否为空
    boolean isEmpty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13

普通队列FIFO实现

class Node<E>{
    E val;
    Node<E> next;
    public Node(E val) {
        this.val = val;
    }
}
public class LinkedQueue<E> implements Queue<E> {
    private int size;
    private Node<E> head; //队首
    private Node<E> tail; //队尾
    @Override
    public void offer(E val) {
        //尾插
        Node node = new Node(val);
        if (head == null){
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size ++;
    }

    @Override
    public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
        return head.val;
    }

    @Override
    public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
        E val = head.val;
        Node<E> node = head;
        head = head.next;
        node.next = node = null;
        size --;
        return val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
       StringBuilder sb = new StringBuilder();
       sb.append("front [");
       for (Node x = head; x != null; x = x.next){
           sb.append(x.val);
           if (x.next != null){
               sb.append(",");
           }
       }
       sb.append("] tail");
       return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

JDK中的内置队列实现，子类是LinkedList

public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    queue.offer(4);
    System.out.println(queue);
    queue.poll();
    System.out.println(queue);
}
输出:
[1, 2, 3, 4]
[2, 3, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3队列的题目

用队列实现栈

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

思路：这道题用两个队列，一个队列q1用来保存实际元素的值，也就是栈中值的顺序和q1队列中的顺序要保持一致。另一个队列q2作为辅助。

核心:

1. 新元素永远入q2
2. 将q1的值依次出队在入队到q2，这样就颠倒过来了
3. 将q1和q2的引用交换，这样q1就存了栈的值

图示

class MyStack {
    Queue<Integer> q1 = new LinkedList();
    Queue<Integer> q2 = new LinkedList();
    public MyStack() {}

    public void push(int x) {
        //新元素入q2
        q2.offer(x);
        //q1依次出队入q2
        while (!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        //交换q1,q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

如何用一个队列实现栈

先记录下当前队列的元素个数

将新元素直接入队

让新元素变为队首元素，连续出队n（元素个数）次，将老元素全都出队在入队n次。

class MyStack {
    Queue<Integer> queue = new LinkedList<>();
    public MyStack() {}

    public void push(int x) {
        //记录元素个数
        int size = queue.size();
        //新元素入队
        queue.offer(x);
        //将老元素先出队在入队
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

思路:s1是保存元素的栈

1. 先将s1中的所有元素依次弹出放入s2
2. 将新元素放入s1，此时新元素就变为s1的栈底，也就是队尾元素
3. 将s2中的元素从s2依次弹出到s1

class MyQueue {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
    
    public MyQueue() {}

    public void push(int x) {
        //先将s1的所有元素弹出压入s2中
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        //s1为空，新元素直接入s1，成为栈底，队尾
        s1.push(x);
        //把s2中的所有元素依次弹回s1
        while (!s2.isEmpty()){
            s1.push(s2.pop());
        }
    }

    public int pop() {
        return s1.pop();
    }

    public int peek() {
        return s1.peek();
    }

    public boolean empty() {
        return s1.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.4 循环队列

循环队列基本上使用固定长度的数组来实现。

入队和出队操作，使用两个引用，head和tail，添加元素在数组尾部添加，删除元素只要移动head引用指向的地址（逻辑删除）

数组的头部就是队首（head），数组的尾部就是队尾（tail）。数组[head,tail)是循环队列的有效元素。

head指向循环队列的第一个元素

tail指向循环队列有效元素的后一个元素

这样数组最多只能存放n-1个有效元素，因为浪费的一个空间需要判断队列是否已满

循环队列是指当head或者tail引用走到数组末尾时，下一次在继续向后移动，实际上是返回数组的头部继续操作。

循环队列的好处是在删除元素时，不需要进行数据的搬移。当有新的元素添加时，会覆盖掉之前的元素。

图示

判断循环队列为空:数组为空，循环队列就为空。head == tail

判断循环队列已满：（tail + 1）% n == head

head和tail的移动，使用取模操作，数组的长度n，tail = (tail + 1) % n

对数组长度取模的本质：

当head和tail走到数组最后一个索引位置，下一次要返回数组头部，就必须使用+1对n取模

关于最后一个元素的索引取值

当tail == 0时，最后一个有效元素就在数组的末尾，索引为data.length - 1

tail != 0时，最后一个元素就是tail - 1

2.5 循环队列的实现

public class LoopQueue implements Queue<Integer>{
    //定长数组
    private Integer[] data;
    //指向队首元素的索引
    private int head;
    //指向队尾元素的下一个索引
    private int tail;

    public LoopQueue(int size) {
        //循环队列要浪费一个空间判断是否已满
        data = new Integer[size + 1];
    }

    @Override
    public void offer(Integer val) {
        if (isFull()) {
            throw new ArrayIndexOutOfBoundsException("队列已满");
        }
        data[tail] = val;
        tail = (tail + 1) % data.length;
    }

    @Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
        return data[head];
    }

    @Override
    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个元素的索引
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lastIndex){
                sb.append(",");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2.6 双端对列

JDK中的双端队列是Deque,这是Queue的子接口

这个队列既可以尾插，头出，也可以头插尾出

双端队列的常用子类：LinkedList

//用法和普通的栈和队列完全一样
Deque stack = new LinkedList(); //栈
Deque queue = new LinkedList(); //队列
1
2
3

JDK中双端队列的方法

三、总结

无论使用栈还是队列，统一使用双端队列接口，不推荐用Stack类

用Deque接口，用LinkedList这个子类