数据结构与算法（四）——栈

数据结构与算法

栈介绍

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

数据结构与算法（四）——栈_2021-03-31-14-22-33.png

栈的应用

  • 符号匹配
  • 中缀表达式转换为后缀表达式
  • 计算后缀表达式
  • 实现函数的嵌套调用
  • HTML 和 XML 文件中的标签匹配
  • 网浏览器中已访问页面的历史记录

Java 实现

数组实现( Stack 本是用数组实现的)

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
133
134
135
136
137
138
139
140
public class Stack {
    //小贴士：通常可以利用栈实现字符串逆序，还可以利用栈判断分隔符是否匹配，如<a[b{c}]>，可以正进反出，栈为空则成功。

    /**基于数组实现的顺序栈，连续存储的线性实现，需要初始化容量**/
    //固定数据类型
    //private int[] array;
    //动态数据类型
    private Object[] objArray;

    private int maxSize;

    private int top;

    public Stack() {
    }

    public Stack(int maxSize) {
        if(maxSize > 0){
            objArray = new Object[maxSize];
            this.maxSize = maxSize;
            top = -1;
        }else{
            throw new RuntimeException("初始化大小错误：maxSize=" + maxSize);
        }
    }

    /**
     * 入栈
     * @param obj
     */
    public void objPush(Object obj){
        //扩容
        grow();
        //++在前表示先运算再赋值，优先级高，在后表示先赋值再运算，优先级低
        objArray[++top] = obj;
    }

    /**
     * 出栈
     * @return
     */
    public Object objPop(){
        Object obj = peekTop();
        //声明原顶栈可以回收空间(GC)
        objArray[top--] = null;
        return obj;
    }

    /**
     * 查看栈顶
     * @return
     */
    public Object peekTop(){
        if(top != -1){
            return objArray[top];
        }else{
            throw new RuntimeException("stack is null");
        }
    }

    /**
     * 动态扩容
     */
    public void grow(){
        // << 左移运算符，1表示乘以2的1次方
        if(top == maxSize-1){
            maxSize = maxSize<<1;
            objArray = Arrays.copyOf(objArray,maxSize);
        }
    }



    /**基于链式存储，不连续存储的非线性实现**/
    private class Node<Object>{
        private Object data;

        private Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node nodeTop;

    private int size;

    public void nodePush(Object obj){
        //栈顶指向新元素，新元素的next指向原栈顶元素
        nodeTop = new Node(obj,nodeTop);
        size++;
    }

    public Object nodePop(){
        Node old = nodeTop;
        //声明原顶栈可以回收空间(GC)
        old.next = null;
        //栈顶指向下一个元素
        nodeTop = nodeTop.next;
        size--;
        return old.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");
        for(Node<Object> node = nodeTop; node != null; node = node.next){
            sb.append(node.data.toString() + " ");
        }
        return sb.toString()+"]";
    }

    public static void main(String[] args) {
//        Stack stack = new Stack(1);
//        stack.objPush("abc");
//        stack.objPush(123);
//        stack.objPush("de");
//        stack.objPush("cd");
//        stack.objPush("er");
//        stack.objPush("hello");
//        stack.objPush(666);
//        stack.objPush(545);
//        stack.objPush("word");
//        while (stack.top != -1){
//            System.out.println(stack.objPop());
//        }
//        System.out.println(stack.peekTop());
        Stack stack = new Stack();
        stack.nodePush("111");
        stack.nodePush("222");
        stack.nodePush("aaa");
        stack.nodePush("bbb");
        System.out.println(stack);
        while (stack.size > 1)
        System.out.println(stack.nodePop());
        System.out.println(stack);
    }
}

链表实现

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
/**
 * description:LinkedList 模拟 Stack
 *

 * author: shixinzhang
 *

 * data: 10/23/2016
 */
public class LinkedListStack extends LinkedList{
    public LinkedListStack(){
        super();
    }

    @Override
    public void push(Object o) {
        super.push(o);
    }

    @Override
    public Object pop() {
        return super.pop();
    }

    @Override
    public Object peek() {
        return super.peek();
    }

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

    public int search(Object o){
        return indexOf(o);
    }
}
调用：

@Test
public void testPush() throws Exception {
    LinkedListStack stack = new LinkedListStack();
    System.out.println("栈是否为空: " + stack.isEmpty());

    stack.push("shixin");
    stack.push("好帅");
    stack.push("技巧一流");
    stack.push("haha");

    System.out.println("栈中元素: " + stack);

    System.out.println("获取顶端元素 peek :" + stack.peek());

    System.out.println("顶端元素出栈 pop :" + stack.pop());

    System.out.println("出栈后栈内元素:" + stack);

    System.out.println("search(好帅) 的位置:" + stack.search("好帅"));
}
}

本文标题:数据结构与算法（四）——栈

文章作者:南有乔木

发布时间:2020-02-17, 17:09:50

最后更新:2021-03-31, 14:24:27

原始链接:http://yoursite.com/2020/02/17/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E5%9B%9B%EF%BC%89%E2%80%94%E2%80%94%E6%A0%88/

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

文章目录
  1. 1. 栈介绍
  2. 2. 栈的应用
  3. 3. Java 实现
    1. 3.1. 数组实现( Stack 本是用数组实现的)
    2. 3.2. 链表实现
|