9. 链接栈¶

9.1. 链接栈实现¶

链表栈的实现非常简单。元素仅在列表头部插入和删除。不使用头节点，因为零个或一个元素的列表不需要特殊情况的代码。以下是完整的链表栈实现。

Java
Java (Generic)

// Linked stack implementation
class LStack implements Stack {
  private Link top;               // Pointer to first element
  private int size;               // Number of elements

  // Constructors
  LStack() { top = null; size = 0; }
  LStack(int size) { top = null; size = 0; }

  // Reinitialize stack
  public void clear() { top = null; size = 0; }

// Put "it" on stack
  public boolean push(Object it) {  
    top = new Link(it, top);
    size++;
    return true;
  }

// Remove "it" from stack
  public Object pop() {           
    if (top == null) return null;
    Object it = top.element();
    top = top.next();
    size--;
    return it;
  }

  public Object topValue() {      // Return top value
    if (top == null) return null;
    return top.element();
  }

  // Return stack length
  public int length() { return size; }
  
  // Check if the stack is empty
  public boolean isEmpty() { return size == 0; }
}

// Linked stack implementation
class LStack<E> implements Stack<E> {
  private Link<E> top;            // Pointer to first element
  private int size;               // Number of elements

  // Constructors
  LStack() { top = null; size = 0; }
  LStack(int size) { top = null; size = 0; }

  // Reinitialize stack
  public void clear() { top = null; size = 0; }

// Put "it" on stack
  public boolean push(E it) {  
    top = new Link<E>(it, top);
    size++;
    return true;
  }

// Remove "it" from stack
  public E pop() {           
    if (top == null) { return null; }
    E it = top.element();
    top = top.next();
    size--;
    return it;
  }

  public E topValue() {      // Return top value
    if (top == null) { return null; }
    return top.element();
  }

  // Return stack length
  public int length() { return size; }
  
  // Tell if the stack is empty
  public boolean isEmpty() { return size == 0; }
}