用链表实现栈数据结构(JAVA版）_数据结构——用链表实现栈(java)理论基础

链表实现栈

链表也可以实现栈，通过在表头插入元素的方式实现push操作，删除链表的表头结点的方式实现pop操作

链表结构

/**
 * 单向链表
 */
public class ListNode {

    private int data;

    private ListNode next;

    public ListNode(int data) {
        this.data = data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getData() {
        return this.data;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    public ListNode getNext() {
        return this.next;
    }
    
}
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

链表的栈实现

/**
 * 基于链表的栈的实现
 */
public class LinkedListStack {

    private ListNode head = null;

    public LinkedListStack() {
        head = new ListNode(0);
    }

    public void Push(int data) {
        if (head == null) {
            head = new ListNode(data);
        } else if (head.getData() == 0) {
            head.setData(data);
        } else {
            ListNode node = new ListNode(data);
            node.setNext(head);
            head = node;
        }
    }

    public int pop() {
        if (head == null) {
            throw new EmptyStackException();
        } else {
            int data = head.getData();
            head = head.getNext();
            return data;
        }
    }

    public int top() {
        if (head == null) {
            return 0;
        } else {
            return head.getData();
        }
    }

    public boolean isEmpty() {
        return head == null;
    }

    public void deleteStack() {
        head = 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