Java链栈（栈的链式存储）用法详解

采用链式存储方式的栈称为链栈或链式栈，链栈可采用单链表实现。

由于栈的插入与删除操作仅限在表头的位置进行，对于带头结点的链栈来说，因此链表的表头指针就作为栈顶指针，带头结点的链栈如下图所示。


在图 1 中，top 为栈顶指针，始终指向栈顶元素前面的头结点。链栈的基本操作与链表类似，在使用完链栈时，应释放其空间。

链栈结点的类描述如下：

class LStackNode {
    char data;
    LStackNode next;
    LStackNode(char data) {
        this.data = data;
        this.next = null;
    }
}

链栈的进栈操作与链表的插入操作类似，出栈操作与链表的删除操作类似。关于链栈的操作说明如下：

• 链栈通过链表实现，链表的第一个结点位于栈顶，最后一个结点位于栈底。
• 设栈顶指针为 top，初始化时，对于不带头结点的链栈，top=null；对于带头结点的链栈，top.next =null。
• 不带头结点的栈空条件为 top==null，带头结点的栈空条件为 top.next ==null。

链栈的基本运算

1) 链栈的初始化

public class LinkStack {
    LStackNode top;
    LinkStack() {
        top = new LStackNode('0');
    }
}

2) 判断链栈是否为空

public boolean StackEmpty() {
    if (top.next == null)
        return true;
    else
        return false;
}

3) 入栈操作

入栈操作就是将新元素结点插入链表的第一个结点之前，分为两个步骤：

• p.next=top.next;
• top.next=p;

public void PushStack(char e) {
    LStackNode p = new LStackNode(e);
    p.next = top.next;
    top.next = p;
}

入栈操作如下图所示：

4) 出栈操作

出栈操作就是将单链表中的第一个结点删除，将结点的元素赋值给 e，并释放结点空间。在元素出栈前，要判断栈是否为空。

public char PopStack() throws Exception {
    if (StackEmpty()) {
        throw new Exception("栈为空，不能进行出栈操作！");
    } else {
        LStackNode p = top.next;
        top.next = p.next;
        return p.data;
    }
}

出栈操作如下图所示：

5) 取栈顶元素

public char GetTop() throws Exception {
    if (StackEmpty()) {
        throw new Exception("栈为空！");
    } else {
        return top.next.data;
    }
}

6) 求栈的长度

public int StackLength() {
    LStackNode p = top.next;
    int len = 0;
    while (p != null) {
        p = p.next;
        len++;
    }
    return len;
}

求栈的长度就是求链栈中的元素个数，必须从栈顶指针，即从链表的头指针开始，依次访问每个结点，并利用计数器计数，直到栈底为止。求栈长度的时间复杂度为O(n)。

创建链栈

创建链栈主要是利用链栈的插入操作思想实现的，根据用户输入的元素序列，将该元素序列存入 s[] 中，然后依次取出每个元素，将其插入链栈中，即将元素依次入栈。

创建链栈的算法实现如下：

public void CreateStack() {
    System.out.print("请输入要入栈的字符（以空格分隔）：");
    Scanner input = new Scanner(System.in);
    String s = input.nextLine();
    String[] arr = s.split(" ");
    for (int i = 0; i < arr.length; i++) {
        LStackNode p = new LStackNode(s.charAt(i));
        p.next = top.next;
        top.next = p;
    }
}