8. 栈¶

8.1. 栈的术语与实现¶

栈是一种类似线性表的结构，只允许从一端插入或删除元素。这一限制使栈不如线性表灵活，但也让栈既高效（对它能做的那些操作而言）又易于实现。许多应用只需要栈所提供的那种受限形式的插入和删除操作。在这类情况下，使用更简单的栈数据结构比使用通用的线性表更高效。例如，空闲链表实际上就是一个栈。

尽管有这些限制，栈的用途仍然很多。因此，为栈发展出一套专门的词汇。会计师早在计算机发明之前就在使用栈。他们把栈称为"LIFO"表，即"后进先出"（Last-In, First-Out）。注意，LIFO 策略的一个含义是：栈按元素到达的相反顺序将其删除。

栈中可访问的元素称为 top 元素。元素的加入不叫插入，而叫入栈。元素被移除时，称为从栈中出栈。下面是一个简单的栈 ADT。

Java
Java (Generic)

public interface Stack { // Stack class ADT
  // Reinitialize the stack.
  public void clear();

  // Push "it" onto the top of the stack
  public boolean push(Object it);

  // Remove and return the element at the top of the stack
  public Object pop();

  // Return a copy of the top element
  public Object topValue();

  // Return the number of elements in the stack
  public int length();
  
  // Return true if the stack is empty 
  public boolean isEmpty();
}

public interface Stack<E> { // Stack class ADT
  // Reinitialize the stack.
  public void clear();

  // Push "it" onto the top of the stack
  public boolean push(E it);

  // Remove and return the element at the top of the stack
  public E pop();

  // Return a copy of the top element
  public E topValue();

  // Return the number of elements in the stack
  public int length();
  
  // Tell if the stack is empty or not
  public boolean isEmpty();
}

与线性表一样，栈的实现也有很多变体。这里介绍两种方法：基于数组的栈和链式栈，分别与基于数组的线性表和链表类似。

8.1.1. 基于数组的栈¶

下面是基于数组的栈类的完整实现。

Java
Java (Generic)

class AStack implements Stack {
  private Object stackArray[];    // Array holding stack
  private static final int DEFAULT_SIZE = 10;
  private int maxSize;            // Maximum size of stack
  private int top;                // First free position at top

  // Constructors
  AStack(int size) {
    maxSize = size;
    top = 0;
    stackArray = new Object[size]; // Create stackArray
  }
  AStack() { this(DEFAULT_SIZE); }

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

// Push "it" onto stack
  public boolean push(Object it) {
    if (top >= maxSize) return false;
    stackArray[top++] = it;
    return true;
  }

// Remove and return top element
  public Object pop() {
    if (top == 0) return null;
    return stackArray[--top];
  }

  public Object topValue() {          // Return top element
    if (top == 0) return null;
    return stackArray[top-1];
  }

  public int length() { return top; } // Return stack size

  public boolean isEmpty() { return top == 0; } // Check if the stack is empty
}

class AStack<E> implements Stack<E> {
  private E stackArray[];         // Array holding stack
  private static final int DEFAULT_SIZE = 10;
  private int maxSize;            // Maximum size of stack
  private int top;                // First free position at top

  // Constructors
  @SuppressWarnings("unchecked") // Generic array allocation
  AStack(int size) {
    maxSize = size;
    top = 0;
    stackArray = (E[])new Object[size]; // Create stackArray
  }
  AStack() { this(DEFAULT_SIZE); }

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

// Push "it" onto stack
  public boolean push(E it) {
    if (top >= maxSize) { return false; }
    stackArray[top++] = it;
    return true;
  }

// Remove and return top element
  public E pop() {
    if (top == 0) { return null; }
    return stackArray[--top];
  }

  public E topValue() {          // Return top element
    if (top == 0) { return null; }
    return stackArray[top-1];
  }

  public int length() { return top; } // Return stack size

  public boolean isEmpty() { return top == 0; }  // Tell if the stack is empty
}