数据结构-栈和队列

发表于 | 分类于 | | 阅读次数: |
字数统计: 2,974 字 | 阅读时长 ≈ 14 分钟
栈

栈（Stack）也是一种线性结构。

相比数组，栈对应的操作是数组的子集。

只能从一端添加元素，也只能从一端取出元素，这一端成为栈顶。

栈是一种后进先出的数据结构，Last In First Out（LIFO）

栈的应用：

  1. 无处不在的Undo操作（撤销）即编译器会使用一个栈来记录我们的输入数据，当我们想撤销输入的时候就是栈的元素出栈。

  2. 程序调用的系统栈

    image-20181227154401491

    当我们在写代码的时候，存在函数调用的情况下，就会使用系统栈。系统栈会记录每次切换函数的位置当系统不知道下步执行方向的时候，将会去系统栈中查找之前入栈的位置。这就是代码中存在子逻辑调用的原理。这个对于理解递归很有帮助。

栈的实现

1
2
3
4
5
6
Stack<E>
void push(E)  //入栈
E pop()	//出栈
E peek()  // 看一眼栈顶的元素是什么
int getSize()  // 获得栈有多少元素
boolean isEmpty() // 判断栈是否为空

从用户的角度看，支持这些操作就好，具体底层实现，用户不关心。实际底层有多种实现方式。

这里栈的实现通过先做一个接口然后继承接口来实现

image-20181227161559293

我们的我们创建的这个ArrayStack 是基于之前创建的Array的 因此内部很多方法都是之前的

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
public class ArrayStack<E> implements Stack<E> {
    Array<E> array; // 我们创建的这个ArrayStack 是基于之前创建的Array的

    // 构造函数 指定长度
    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void push(E e) {
        array.addLast(e);

    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append("[");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1)
                res.append(", ");
        }

        res.append("] top");
        return res.toString();
    }

}

我们测试下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {

    public static void main(String[] args) {
        // write your code here

        ArrayStack<Integer> stack = new ArrayStack<>();

        for (int i = 0; i < 5; i++) {
            stack.push(i);
        }
        System.out.println(stack);

        stack.pop();
        System.out.println(stack);

    }
}

// 结果
Stack: [0, 1, 2, 3, 4] top
Stack: [0, 1, 2, 3] top

栈的时间复杂度

image-20181227180209093

栈的应用

我们上面说过两个栈的应用：

undo操作 – 编辑器

系统调用栈 – 操作系统

接下来我们学习下另一个应用：括号匹配—编译器

我们按照LeetCode上的一个题目有效的括号来学习下。

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

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
import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{')
                stack.push(c);
            else {
                // 如果 不上面三个字符 则是 ） ] }
                if (stack.isEmpty())
                    // 存在右侧符号但是栈为空则是 false
                    return false;

                char topChar = stack.pop();

                if (c == ')' && topChar != '(')
                    return false;

                if (c == ']' && topChar != '[')
                    return false;

                if (c == '}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

上面是我们使用内置的Stack来实现的。

我们用Python实现下。

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
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        left_char = ["(", "[", "{"]
        right_char = [")", "]", "}"]
        stack = []
        for char in s:
            if char in left_char:
                stack.append(char)
            else:
                if not stack:
                    return False
                top_char = stack.pop()
                if char == ')' and top_char != "(":
                    return False
                if char == ']' and top_char != "[":
                    return False
                if char == '}' and top_char != "{":
                    return False
                
        return not stack

我们如果想使用自己定义的ArrayStack只需改动一行代码

image-20181227224202490

当我们想在LeetCode中使用我们自己写的代码的时候，就需要将之前创建的类当成Solution类的一个内部类。

image-20181227224624955

队列

队列（Queue）也是一种线性结构

相比数组，队列对应的操作是数组的子集

只能从一段（队尾）添加元素，只能从另一端（队首）取出元素

队列是一种先进先出的数据结构（先到先得）Frist In First Out（FIFO）

队列的实现

1
2
3
4
5
6
Queue<E>
void enqueue(E e)
E dequeue()
E getFront()
int getSize()
boolean isEmpty()

我们要实现自己的队列，需要实现上面的方法。

image-20181228095526806

和之前学习栈一样，我们使用最开始的Array进行复用。

先看下目录结构

image-20181228102400468

其中Array为复用的

接口Queue主要规范我们要实现的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
public interface Queue<E> {

    int getSize();

    boolean isEmpty();

    void enqueue(E e);

    E dequeue();

    E getFront();

}

类ArrayQueue是我们自己实现的类

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
67
68
69
70
71
72
73
74
75
76
77
78
79
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    // 构造方法 用户事先知道要创建多大的队列
    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
        array = new Array<>();
    }


    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    // 入队
    @Override
    public void enqueue(E e) {

        array.addLast(e);

    }

    // 出队
    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    // 获得队首
    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: "));
        res.append("front [");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();

        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);

            // 每隔3次取出一个数
            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);

            }
        }

    }
}

数组队列的复杂度分析

image-20181228103131569

我们看到在入队的时候因为可能扩容，因此在均摊算法下，时间复杂度为O(1)

在出队的时候，因为所有的元素都需要往前挪一位，因此时间复杂度为O(n)

有没有什么方法可以使这两个方法的复杂度都为O(1)呢？

循环队列

对于基于Array的队列，每次删除第一个元素的时候，后面的元素全部往前挪一位。因此其时间复杂度是O(n)

image-20181228114040705

我们可以将队首和队尾标识出来，即使队首被删除我们只需要将队首维护的指针增加1就好了。

image-20181228114009872

在循环队列中front指向的是第一个值位置，tail指向的是下一个要存放值的位置。

我们看下在最开始队列为空的情况下

image-20181228133527119

在最开始队列为空的时候front和tail指向同一个位置。其他时候这两个是不会指向同一个位置的。

image-20181228133808666

每次新增数据，我们将tail的位置往后挪移位即tail++。

image-20181228133902439

当有元素出队的时候，只需要将front位置往后挪一位即front++。

为什么说是循环数组呢？我们看下在初始数组存放到第七位的时候

image-20181228134724141

当数据存放到第七个位置的时候tail并没有tail++而是直接挪到了第一位。这是因为我们在之前删除了前面的元素，导致队列前面为空。我们可以利用起来这些被删除的空间，因此被称为循环队列。

我们把上面的数组看成一个环形，当数据填充到第七位的时候我们的下以为不是tail加一而是tail+1 % 数据长度。因此tial从7变成0的公式是(7+1)%8。

image-20181228140521663

上面我们说过当tail和front指向同一个位置的时候表示队列为空，在上图这种情况是不能再往队列中新增数据了。我们规定(tail + 1) % c == fron表示队列为满。因为当我们再新增一个元素的时候，front和tail将指向同一个位置。因此当队列只剩最后一个空间的时候，我们可以认为队列已经满了。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;  // 有多少元素

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;
    }

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

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void enqueue(E e) {

        // 判断是否已满
        if ((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {

        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity) {

        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}
// 输出
Queue: size = 1 , capacity = 10
front [0] tail
Queue: size = 2 , capacity = 10
front [0, 1] tail
Queue: size = 3 , capacity = 10
front [0, 1, 2] tail
Queue: size = 2 , capacity = 5
front [1, 2] tail
Queue: size = 3 , capacity = 5
front [1, 2, 3] tail
Queue: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Queue: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Queue: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Queue: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Queue: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Queue: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Queue: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Queue: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail

循环队列和数组队列的输出是一样的，并且对外的函数是一致的。不过解决了出队的O(n)。

循环队列的复杂度分析

image-20181228164224629

因为出队可能涉及到缩容操作，因此使用均摊算法的时间复杂度为o(n)。

我们看下ArrayQueue和LoopQueue实际运行比较

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
import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q, int opCount) {

        long startTime = System.nanoTime();

        Random random = new Random();
        for (int i = 0; i < opCount; i++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for (int i = 0; i < opCount; i++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
    }
}
// 输出
ArrayQueue, time: 3.870676546 s
LoopQueue, time: 0.01901037 s

两者的主要区别是在出队的时候使用ArrayQueue是O(n)而LoopQueue的出队在均摊算法下是O(1)。

知识就是财富
如果您觉得文章对您有帮助, 欢迎请我喝杯水！