大数据知识体系
  • 数据结构与算法
  • 线性表
Will
2022-03-26
目录

线性表 - 栈

# 概念

栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。将允许插入和删除的一端成为栈顶（top），另一端称为栈底（bottom），不包含任何元素的栈称为空栈。栈的插入操作叫做进栈或压栈、入栈，栈的删除操作叫做出栈。

栈的最大特点是后进先出（LIFO），就像弹夹里的子弹一样。需要注意的是，栈是一种特殊的线性表，只是限制了插入和删除的位置，始终在栈顶进行操作。

# 顺序结构实现

顺序结构实现中采用数组来实现栈，下标为哦的一段作为栈底，空栈的判定条件为 top = -1。

# 抽象数据类型

public class ArrayStack {

    class StackNode {
        public Object[] data;
        public int top;
    }

    private int maxSize;
    private StackNode stack;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new StackNode();
        stack.data = new Object[maxSize];
        stack.top = -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 进栈

    public void push(Object obj) {
        if (stack.top == maxSize - 1) {
            System.out.println("栈已满，入栈失败！");
        } else {
            stack.top++;
            stack.data[stack.top] = obj;
        }
    }
1
2
3
4
5
6
7
8

# 出栈

    public Object pop() {
        if (stack.top == -1) {
            System.out.println("栈已空，出栈失败~");

            return null;
        } else {
            Object data = stack.data[stack.top];
            stack.data[stack.top] = null;
            stack.top--;

            return data;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 完整代码

package com.sqlboy.lineartable;

public class ArrayStack {

    class StackNode {
        public Object[] data;
        public int top;
    }

    private int maxSize;
    private StackNode stack;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new StackNode();
        stack.data = new Object[maxSize];
        stack.top = -1;
    }

    /**
     * 入栈
     *
     * @param obj
     */
    public void push(Object obj) {
        if (stack.top == maxSize - 1) {
            System.out.println("栈已满，入栈失败！");
        } else {
            stack.top++;
            stack.data[stack.top] = obj;
        }
    }

    /**
     * 出栈
     *
     * @return
     */
    public Object pop() {
        if (stack.top == -1) {
            System.out.println("栈已空，出栈失败~");

            return null;
        } else {
            Object data = stack.data[stack.top];
            stack.data[stack.top] = null;
            stack.top--;

            return data;
        }
    }

    /**
     * 打印栈
     */
     public void show() {
        for (int i = stack.top; i >= 0; i--) {
            System.out.println(stack.data[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(5);
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        arrayStack.push(4);
        arrayStack.push(5);

        arrayStack.show();

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

        arrayStack.show();
    }
}
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

# 链式结构实现

栈的链式存储结构是通过链表来实现，简称链栈。链栈中通常不需要头结点，将栈顶放在单链表的头部。

对于链栈来说基本不存在栈满的情况，除非内存不够用。对于链栈而言，空栈的判断条件是 top = null。

链栈进栈：

链栈出栈：

# 抽象数据类型

public class LinkStack {
    class StackNode {
        public Object data;
        public StackNode next;

        public StackNode() {
        }

        public StackNode(Object data) {
            this.data = data;
        }
    }

    private int size;
    private StackNode top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 进栈

    public void push(Object obj) {
        StackNode node = new StackNode(obj);
        node.next = top;
        top = node;
        size++;
    }
1
2
3
4
5
6

# 出栈

    public Object pop() {
        if (size < 1) {
            System.out.println("栈已空，出栈失败！");

            return null;
        }

        StackNode t = top;
        top = top.next;
        size--;

        return t.data;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

# 完整代码

package com.sqlboy.lineartable;

public class LinkStack {
    class StackNode {
        public Object data;
        public StackNode next;

        public StackNode() {
        }

        public StackNode(Object data) {
            this.data = data;
        }
    }

    private int size;
    private StackNode top;

    /**
     * 入栈
     *
     * @param obj
     */
    public void push(Object obj) {
        StackNode node = new StackNode(obj);
        node.next = top;
        top = node;
        size++;
    }

    /**
     * 出栈
     *
     * @return
     */
    public Object pop() {
        if (size < 1) {
            System.out.println("栈已空，出栈失败！");

            return null;
        }

        StackNode t = top;
        top = top.next;
        size--;

        return t.data;
    }

    /**
     * 打印栈
     */
    public void show() {
        StackNode node = top;
        for (int i = 0; i < size ; i++) {
            System.out.println(node.data);
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkStack linkStack = new LinkStack();
        linkStack.push(1);
        linkStack.push(2);
        linkStack.push(3);
        linkStack.push(4);
        linkStack.push(5);

        linkStack.show();
        System.out.println(linkStack.top.data);

        System.out.println(linkStack.pop());
        System.out.println(linkStack.pop());
        System.out.println(linkStack.pop());
        System.out.println(linkStack.pop());
        System.out.println(linkStack.pop());
        System.out.println(linkStack.pop());
    }
}
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

# 两栈共享空间

两栈共享空间即两个栈共同使用一个数组实现，栈 A 从数组下标最小开始入栈，栈 B 从数组下标最大开始入栈。如图所示：

# 抽象数据类型

class StackNode {
        public Object[] data;

        public int maxSize;
        // 第一个栈的指针
        public int top1;
        // 第二个栈的指针
        public int top2;

        public StackNode(int maxSize) {
            this.maxSize = maxSize;
            data = new Object[maxSize];
            top1 = -1;
            top2 = maxSize;
        }
    }

    private StackNode stack;
    private int maxSize;

    public ShareStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new StackNode(maxSize);
    }
}
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

# 进栈

    /**
     * 进栈
     *
     * @param obj        入栈元素
     * @param stackIndex 栈编号，只能为1或2
     */
    public void push(Object obj, int stackIndex) throws Exception {
        if (stack.top1 + 1 == stack.top2) {
            throw new Exception("栈已满");
        }

        if (stackIndex != 1 && stackIndex != 2) {
            throw new Exception("栈下标错误，只能为1或2");
        }

        if (stackIndex == 1) {
            stack.top1++;
            stack.data[stack.top1] = obj;
        } else {
            stack.top2--;
            stack.data[stack.top2] = obj;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 出栈

    /**
     * 出栈
     *
     * @param stackIndex 栈编号
     * @return
     */
    public Object pop(int stackIndex) throws Exception {
        if (stackIndex != 1 && stackIndex != 2) {
            throw new Exception("栈下标错误，只能为1或2");
        }

        if (stackIndex == 1) {
            if (stack.top1 < 0){
                throw new Exception("栈1为空");
            }

            Object data = stack.data[stack.top1];
            stack.data[stack.top1] = null;
            stack.top1 --;

            return data;
        } else {
            if(stack.top2 >= stack.maxSize){
                throw new Exception("栈2为空");
            }

            Object data = stack.data[stack.top2];
            stack.data[stack.top2] = null;
            stack.top2 ++;

            return data;
        }
    }
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

# 完整代码

package com.sqlboy.lineartable;

public class ShareStack {

    class StackNode {
        public Object[] data;

        public int maxSize;
        // 第一个栈的指针
        public int top1;
        // 第二个栈的指针
        public int top2;

        public StackNode(int maxSize) {
            this.maxSize = maxSize;
            data = new Object[maxSize];
            top1 = -1;
            top2 = maxSize;
        }
    }

    private StackNode stack;
    private int maxSize;

    public ShareStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new StackNode(maxSize);
    }

    /**
     * 打印栈
     */
    public void show() {
        for (int i = 0; i < stack.maxSize; i++) {
            System.out.println(stack.data[i]);
        }
        System.out.println();
    }

    /**
     * 进栈
     *
     * @param obj        入栈元素
     * @param stackIndex 栈编号，只能为1或2
     */
    public void push(Object obj, int stackIndex) throws Exception {
        if (stack.top1 + 1 == stack.top2) {
            throw new Exception("栈已满");
        }

        if (stackIndex != 1 && stackIndex != 2) {
            throw new Exception("栈下标错误，只能为1或2");
        }

        if (stackIndex == 1) {
            stack.top1++;
            stack.data[stack.top1] = obj;
        } else {
            stack.top2--;
            stack.data[stack.top2] = obj;
        }
    }

    /**
     * 出栈
     *
     * @param stackIndex 栈编号
     * @return
     */
    public Object pop(int stackIndex) throws Exception {
        if (stackIndex != 1 && stackIndex != 2) {
            throw new Exception("栈下标错误，只能为1或2");
        }

        if (stackIndex == 1) {
            if (stack.top1 < 0){
                throw new Exception("栈1为空");
            }

            Object data = stack.data[stack.top1];
            stack.data[stack.top1] = null;
            stack.top1 --;

            return data;
        } else {
            if(stack.top2 >= stack.maxSize){
                throw new Exception("栈2为空");
            }

            Object data = stack.data[stack.top2];
            stack.data[stack.top2] = null;
            stack.top2 ++;

            return data;
        }
    }

    public static void main(String[] args) throws Exception {
        ShareStack stack = new ShareStack(10);

        stack.push(0, 1);
        stack.push(1, 1);
        stack.push(2, 1);

        stack.push(3, 2);
        stack.push(4, 2);
        stack.push(5, 2);
        stack.push(5, 2);
        stack.push(5, 2);
        stack.push(5, 2);

        stack.show();

        stack.pop(2);
        stack.pop(2);
        stack.pop(1);

        stack.show();
    }
}
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

# 栈的应用

# 递归

将一个直接调用自己或通过一系列调用语句间接调用自己的函数，称作递归函数。每个递归都至少有一个终止条件，满足该条件是不再进行递归，否则会陷入死循环。

# 四则运算

上次更新: 2023/11/01, 03:11:44

← 线性表 - 队列→

Theme by Vdoing | Copyright © 2022-2023 Will 蜀ICP备2022002285号-1