『数据结构与算法』—— 栈

字数统计: 2,094 字   |   阅读时长: 11 分   |   本文总阅读量: 次


数据结构与算法

定义

先入后出，有点类似将书放在抽屉里，先放进去的书，如果想拿到他，必须将他上面书拿完才可以，粗俗的形容可以这么比喻：“吃了吐”叫栈，“吃了拉”叫队列，话粗理不粗。栈是一种“操作受限”的线性表，只允许一段插入和删除数据。

从功能上看，数组或链表确实可代替栈，但是在特定的情况中，数组和链表暴露的接口太多，操作上虽然灵活，但是很多条件不可控，使用上当然容易出现问题。

当某个数据集合只涉及在一段插入和删除数据，并且满足先进后出的特性，我们就应该首选栈这种数据结构。

实现

根据其定义和特点，栈主要包含两个操作，入栈和出栈。数组和链表都可以实现，用数组实现的栈叫做 顺序栈，用链表实现的栈叫做 链式栈。后面会贴上具体的实现代码和测试用例。

栈存储数据只需要一个大小为 n 的数组就足够了，在操作数据的过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)，至于入栈和出栈的时间复杂度也是 O(1)。

练习

数组实现栈(支持动态扩容)

需要注意点：

  1. 当数据不断增加，大小达到阈值，也就是容器满了，此时大小需要扩容到原来的两倍。
  2. 当数据不断减小，大小达到整个大小四分之一时，此时大小需要缩小为原来的 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
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
class ArrayStack<T> implements Iterable<T>{
    private T[] data;
    private int totalCount;
    private int count;

    ArrayStack(int capacity) {
        data = (T[]) new Object[capacity];
        totalCount = capacity;
    }

    private boolean push(T t) {
        if (count == totalCount) {
            resize(totalCount * 2);
        }
        data[count] = t;
        count++;
        System.out.println("push: " + t + "  data:\t" + Arrays.toString(data));
        return true;
    }

    private T pop() {
        if (count == 0) return null;
        T t = data[count - 1];
        data[count - 1] = null;
        count --;
        if (count == totalCount / 4 && totalCount / 2 != 0) {
            resize(totalCount / 2);
        }
        System.out.println("pop: " + t + "  data:\t" + Arrays.toString(data));
        return t;
    }

    boolean isEmpty() {
        return count == 0;
    }

    int size() {
        return count;
    }

    T peek() {
        if (count == 0) {
            return null;
        }
        T t = data[count - 1];
        System.out.println("peek: " + t + "  data:\t" + Arrays.toString(data));
        return t;
    }

    private void resize(int newSize) {
        T[] newData = (T[]) new Object[newSize];
        for (int i = 0; i < count; i++) {
            newData[i] = data[i];
        }
        totalCount = newData.length;
        System.out.println("扩容前：" + data.length);
        data = newData;
        System.out.println("重新调整大小:\t" + data.length + "  data:\t" + Arrays.toString(data));
    }

    public static void main(String[] args) {
        ArrayStack<Integer> data = new ArrayStack<Integer>(4);
        data.push(1);
        data.push(2);
        data.push(3);
        data.push(4);
        data.push(5);
        data.push(6);
        System.out.println("size:\t" + data.size());
        System.out.println("isEmpty:\t" + data.isEmpty());
        for (Integer datum : data) {
            System.out.print(datum);
        }
        System.out.println();
        data.pop();
        data.pop();
        data.pop();
        data.pop();
        data.peek();
        data.peek();
        data.peek();
    }

    @Override
    public Iterator<T> iterator() {
        return new ArrayIterator();
    }
    class ArrayIterator implements Iterator<T> {
        int i = count;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            return data[--i];
        }

        @Override
        public void remove() {

        }
    }
}

这里如果需要支持加强 for 循环，则需要创建自定义实现 Iterator 类。

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
push: 1  data:	[1, null, null, null]
push: 2  data:	[1, 2, null, null]
push: 3  data:	[1, 2, 3, null]
push: 4  data:	[1, 2, 3, 4]
扩容前：4
重新调整大小:	8  data:	[1, 2, 3, 4, null, null, null, null]
push: 5  data:	[1, 2, 3, 4, 5, null, null, null]
push: 6  data:	[1, 2, 3, 4, 5, 6, null, null]
size:	6
isEmpty:	false
654321
pop: 6  data:	[1, 2, 3, 4, 5, null, null, null]
pop: 5  data:	[1, 2, 3, 4, null, null, null, null]
pop: 4  data:	[1, 2, 3, null, null, null, null, null]
扩容前：8
重新调整大小:	4  data:	[1, 2, null, null]
pop: 3  data:	[1, 2, null, null]
peek: 2  data:	[1, 2, null, null]
peek: 2  data:	[1, 2, null, null]
peek: 2  data:	[1, 2, null, null]

链表实现栈

需要注意的是临界值的判断。

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
class LinkedStack<T> implements Iterable<T> {
    Node<T> head = null;
    int count = 0;

    void push(T t) {
        Node<T> node = createNode(t);
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
        count++;
        System.out.println("push:\t" + t + "  data:\t" + head.toString());
    }

    T pop() {
        if (head == null) {
            return null;
        }
        T t = head.value;
        head = head.next;
        if (head != null) {
            System.out.println("pop:\t" + t + "  data:\t" + head.toString());
        } else {
            System.out.println("pop:\t" + t + "  data:\tnull");
        }
        count--;
        return t;
    }

    boolean isEmpty() {
        return count == 0;
    }

    int size() {
        return count;
    }

    T peek() {
        if (head == null) {
            return null;
        }
        T t = head.value;
        System.out.println("peek:\t" + t + "  data:\t" + head.toString());
        return t;
    }

    Node<T> createNode(T t) {
        return new Node<T>(t, null);
    }

    public static void main(String[] args) {
        LinkedStack<Integer> stack = new LinkedStack<Integer>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("size:\t" + stack.size());
        System.out.println("isEmpty:\t" + stack.isEmpty());
        for (Integer integer : stack) {
            System.out.println(integer);
        }
        stack.peek();
        stack.peek();
        stack.peek();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (T t : this) {
            sb.append(t).append(" ");
        }
        sb.append("\n");
        return sb.toString();
    }

    void clear() {
        head = null;
        count = 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedIterator();
    }

    class LinkedIterator implements Iterator<T> {
        Node<T> first = head;
        int n = count;

        @Override
        public boolean hasNext() {
            return n > 0;
        }

        @Override
        public T next() {
            T t = first.value;
            first = first.next;
            n--;
            return t;
        }

        @Override
        public void remove() {

        }
    }
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
push:	1  data:	1 
push:	2  data:	2 1 
push:	3  data:	3 2 1 
push:	4  data:	4 3 2 1 
size:	4
isEmpty:	false
4321
peek:	4  data:	4 3 2 1 
peek:	4  data:	4 3 2 1 
peek:	4  data:	4 3 2 1 
pop:	4  data:	3 2 1 
pop:	3  data:	2 1 
pop:	2  data:	1 
pop:	1  data:	null

栈在括号匹配中的应用

括号一般都是一一对应的，那可以用栈保存未匹配的左括号，从左到又进行扫描。

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
class StackTest1 {
    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack<String>();
        stack.push("[");
        stack.push("{");
        stack.push("『");
        stack.push("「");
        stack.push("」");
        stack.push("』");
        stack.push("}");
        stack.push("]");
        System.out.println(stack.toString());
        System.out.println("is correct:\t" + isCorrect(stack));
    }

    private static boolean isCorrect(LinkedStack<String> stack) {
        boolean isCorrect = true;
        LinkedStack<String> stack1 = new LinkedStack<String>();
        for (String s : stack) {
            stack1.push(s);
        }
        Iterator<String> iterator = stack.iterator();
        Iterator<String> iterator1 = stack1.iterator();
        while (iterator.hasNext() && iterator1.hasNext()) {
            if (!equals(iterator.next(), iterator1.next())) {
                return false;
            }
        }
        return isCorrect;
    }

    private static boolean equals(String one, String two) {
        return ("[".equals(one) && "]".equals(two)) || ("[".equals(two) && "]".equals(one)) ||
                ("{".equals(one) && "}".equals(two)) || ("{".equals(two) && "}".equals(one)) ||
                ("「".equals(one) && "」".equals(two)) || ("「".equals(two) && "」".equals(one)) ||
                ("『".equals(one) && "』".equals(two)) || ("『".equals(two) && "』".equals(one));
    }
}

浏览器在栈的应用

一般浏览器支持回退和前进功能，其实可以通过栈来实现这个功能。

  1. 使用两个栈，一个存储后退的数据，一个存储前进的数据
  2. 每次打开新的网址，后退栈压入，前进栈清空
  3. 每次回退网站，后退栈出栈，前进栈压入
  4. 在已经后退基础上前进，后退栈压入，前进栈出栈
  5. 每次前进和后退都需要判断各自栈是否可以进行数据操作
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
class StackTest2 {
    String currentPage = "";
    LinkedStack<String> backStack;
    LinkedStack<String> forwardStack;

    StackTest2() {
        backStack = new LinkedStack<String>();
        forwardStack = new LinkedStack<String>();
    }

    void open(String url) {
        if (currentPage != null) {
            backStack.push(url);
            forwardStack.clear();
        }
        showPage(url, "open");
    }

    boolean canGoBack() {
        return !backStack.isEmpty();
    }

    boolean canGoForward() {
        return !forwardStack.isEmpty();
    }

    void goBack() {
        if (canGoBack()) {
            String back = backStack.pop();
            forwardStack.push(currentPage);
            showPage(back, "go back");
        }
    }

    void goForward() {
        if (canGoForward()) {
            String forward = forwardStack.pop();
            backStack.push(currentPage);
            showPage(forward, "go forward");
        }
    }

    void showCurrentPage() {
        System.out.println("current page url:\t" + currentPage);
    }


    void showPage(String url, String desc) {
        this.currentPage = url;
        System.out.println("current page url:\t" + this.currentPage + "  desc:\t" + desc);
    }

    public static void main(String[] args) {
        StackTest2 stack = new StackTest2();
        stack.open("http://www.baidu.com");
        stack.open("http://news.baidu.com/");
        stack.open("http://news.baidu.com/ent");
        stack.goBack();
        stack.goBack();
        stack.goForward();
        stack.open("http://www.qq.com");
        stack.goForward();
        stack.goBack();
        stack.goForward();
        stack.goBack();
        stack.goBack();
        stack.goBack();
        stack.goBack();
        stack.showCurrentPage();
    }
}

参考自极客时间

本文标题:『数据结构与算法』—— 栈

文章作者:下位子

发布时间:2018-10-15, 15:10:00

最后更新:2018-12-01, 14:09:52

原始链接:http://xiaweizi.cn/article/2e31/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

#rewardButton { background-color: #ea6f5a; } .btn-pay { margin-bottom: 20px; padding: 8px 25px; font-size: 16px; color: #fff; background-color: #ea6f5a; } .btn { display: inline-block; margin-bottom: 0; font-weight: 400; text-align: center; vertical-align: middle; touch-action: manipulation; cursor: pointer; background-image: none; border: 1px solid transparent; white-space: nowrap; padding: 6px 12px; font-size: 14px; line-height: 1.42857; border-radius: 4px; -webkit-user-select: none; -moz-user-select: none; -ms-user-select: none; user-select: none; } #QR img{ height: 200px; height: 200px; margin: 20px; }
文章目录
  1. 1. 定义
  2. 2. 实现
  3. 3. 练习
    1. 3.1. 数组实现栈(支持动态扩容)
    2. 3.2. 链表实现栈
    3. 3.3. 栈在括号匹配中的应用
    4. 3.4. 浏览器在栈的应用
您是第 位小伙伴 | 本站总访问量 次 | 已经写了 120.4k 字啦

载入天数...载入时分秒...