Java 数组|链表实现栈数据结构_java以数组 链表存储栈中元素

只要了解过数据结构的，就大概能说出栈的特点：
先进后出，插入和删除都只能在栈顶操作。下面我将分别用数组和链表来实现简单的栈数据结构，我自己也是在学习的过程中，发现不就这两个操作嘛，自己写的时候却有点难以下笔，经过这次总结，感觉理解更多了呢

实现

我们可以用数组（顺序栈）和链表（链式栈）来实现栈；

下面的两段代码里面注释已经很详尽了，其实栈几乎就这两个操作，pop(出栈)/push(压栈)；不存在在中间某个地方插入一个东西。

Java 数组实现栈 - 数据结构

public class Stack {

    private String[] data;//存储数据的数组
    private int size; //栈的大小
    private int top; //栈顶位置

    public Stack(int size) {
        this.size = size;
        data = new String[size];
        this.top = -1;
    }

    /**
     * 这里我写了个单纯的打印函数；但是真的单纯吗？
     * 其实我们定义的 top 相当于一个“指针”；虽然好像你没有进行 pop() 操作
     * 但是你“指针”的值已经变为 -1。即这个栈又为空了。
     *
     * 所以直接在 pop() 操作中返回每一次 pop() 操作的值是一样的，即不用单独写一个 print() 来打印栈里面的值
     * @return
     */
    /*public String[] print() {
        String[] temp = new String[size];

        for (int i = 0; i < size; i++) {
            temp[i] = data[top--];
            if (top == -1) {
                break;
            }
        }
        return temp;
    }*/


    //入栈操作
    public void push(String str) {
        if (top > size) {
            System.out.println("栈空间已用完");
        } else {
            data[++top] = str;
        }
    }

    //出栈操作
    public String pop() {
        if (top == -1) {
            System.out.println("栈中没有元素");
            return null;
        } else {
            return this.data[top--];
        }
    }

    public static void main(String[] args) {
        Stack stack = new Stack(10);
        stack.push("1");
        stack.push("2");
        stack.push("3");

        /*使用打印函数时的写法*/
//        String print[] = stack.print();
//        for (int i = 0; i < print.length; i++) {
//            if(null==print[i]){
//                break;
//            }
//            System.out.println(print[i]);
//        }
       //通过每次 pop() 操作打印栈中的元素
        while(stack.top!=-1){
            System.out.println(stack.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

Java 链表实现栈

class Node {
    String data;
    Node next;

    public Node(String data) {
        this.data = data;
    }
}

public class Stack {
    private Node top = null;//栈顶元素

    //栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    public void push(String str) {
        Node newNode = new Node(str);
        //top 是当前的顶点，当压栈一次：
        /**
         * 1.将新节点指向 top(当前的顶点)
         * 2.将 top 赋给最新节点(保证 top 始终在最上面)
         */
        newNode.next = top;
        top = newNode;
    }

    public String pop() {
        if (isEmpty()) {
            System.out.println("栈为空");
            return null;
        } else {
            String temp = top.data;
            top = top.next;
            return temp;
        }
    }

    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push("1");
        stack.push("2");
        stack.push("3");
        while(!stack.isEmpty()){
            System.out.println(stack.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

可能看完栈之后，你在 push() 中的 newNode.next 和 pop() 中的 top.next 有点稍许疑惑。没关系，画个图帮助自己分析一波

总结一波

• 学会用画图辅助自己思考，可能有时候只靠想，脑子会不够用哦。画图是真香啊
• 不要觉得自己看懂了，我要我觉得你应该去自己独立的写出来。
• 如果觉得自己代码没有问题，但是结果并不是自己想象那样的，那么请 Debug。IDEA Debug 了解一下。