java分别用链表和数组实现栈_stringbulider 是链表数组吗

一.栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。（来源百度百科）

二.本文内容

本文分别用链表和数组实现了栈

2.1 链表实现

//节点类
public class Node {
    public Object data;
    public Node next;

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

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

/**
 * 方式一: 链表实现
 */
public class MyStack01<E> {
    //栈顶元素
    private Node top;
    //元素个数
    private int count = 0;

    /**
     * 进栈
     * @param element
     */
    public void push(E element){
        Node node = new Node(element);
        if (top != null){
            //若存在栈顶元素，则把新节点的下一个节点指向栈顶元素
            node.next = top;
        }
        //栈顶节点指向新节点
        top = node;
        count++;
    }

    /**
     * 出栈
     * @return
     */
    public E pop(){
        if (count < 1) throw new RuntimeException("栈顶无元素");
        Node node = top;
        top = top.next;
        count--;
        return (E)node.data;
    }

    /**
     * 返回栈内元素个数
     * @return
     */
    public int size(){
        return count;
    }

    /**
     * 打印栈内元素
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("]");
        Node temp = top;
        while (temp != null){
            sb.append(temp.data+",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length()-1 , '[');
        return sb.reverse().toString();
    }
}

//测试类
public class TestMyStack {
    public static void main(String[] args) {
        MyStack01<String> myStack = new MyStack01<>();
        myStack.push("a");
        myStack.push("b");
        myStack.push("c");
        System.out.println("栈内元素为: " + myStack.toString());
        System.out.println("出栈的元素是: " + myStack.pop());
        System.out.println("栈内元素为: " + myStack.toString());
        System.out.println("栈内元素个数为: " + myStack.size());
    }
}
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

测试截图:

2.2 数组实现

/**
 * 方式二: 数组实现
 */
public class MyStack02<E> {
    //操作数组
    private Object[] data;
    //栈顶指针
    int top = -1;
    //数组大小
    int size;

    public MyStack02(int size) {
        this.size = size;
        data = new Object[size];
    }

    /**
     * 入栈
     * @param element
     */
    public void push(E element){
        if (top + 1 == size) throw new RuntimeException("栈已满");
        data[top + 1] = element;
        top ++;
    }

    /**
     * 出栈
     * @return
     */
    public E pop(){
        if (top < 0) throw new RuntimeException("栈内无元素");
        Object obj = data[top];
        data[top--] = null;
        return (E)obj;
    }

    /**
     * 返回栈内元素个数
     * @return
     */
    public int size(){
        return top+1;
    }

    /**
     * 打印栈内元素
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i <= top; i++) {
            sb.append(data[i] + ",");
        }


        sb.setCharAt(sb.length()-1,']');
        return sb.toString();
    }
}

//测试类
public class TestMyStack {
    public static void main(String[] args) {
        MyStack02<String> myStack = new MyStack02<>(4);
        myStack.push("a");
        System.out.println("出栈的元素是: " + myStack.pop());
        myStack.push("b");
        myStack.push("c");
        System.out.println("栈内元素为: " + myStack.toString());
        System.out.println("出栈的元素是: " + myStack.pop());
        System.out.println("栈内元素为: " + myStack.toString());
        System.out.println("栈内元素个数为: " + myStack.size());
    }
}
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

测试截图: