（七）栈的三种实现

目标

• 使用链表、数组或向量实现ADT栈
• 对不同的实现方式及其性能进行对比

6.1 链式实现

　　ADT栈中每个操作push、pop、peek都会涉及栈顶，使用链式，将头结点指向的第一个元素作为栈顶，链的最后一个元素作为栈底。

类的框架

　　有一个数据域topNode，为节点链的头引用，构造时默认为null，实现类包含Node类，每个节点都为Node类的实例对象。

　　链式实现ADT栈的类框架

public class LinkedStack<T> implements StackInterface<T> {
　　private Node topNode;
　　public LinkedStack() {
　　　　topNode = null;
　　} // end default constructor
　　@Override
　　public void push(T newEntry) {
　　　　// TODO Auto-generated method stub
　　} // end push
　　@Override
　　public T pop() {
　　　　// TODO Auto-generated method stub
　　　　return null;
　　} // end pop
　　@Override
　　public T peek() {
　　　　// TODO Auto-generated method stub
　　　　return null;
　　} // end peek
　　@Override
　　public boolean isEmpty() {
　　　　// TODO Auto-generated method stub
　　　　return false;
　　} // end isEmpty
　　@Override
　　public void clear() {
　　　　// TODO Auto-generated method stub
　　} // end clear
　　private class Node{
　　　　private T data;       // Entry in stack
　　　　private Node next;    // Link to next node
　　　　public Node(T data, Node next) {
　　　　　　super();
　　　　　　this.data = data;
　　　　　　this.next = next;
　　　　} // end constructor
　　　　public T getData() {
　　　　　　return data;
　　　　} // end getData
　　　　public void setData(T data) {
　　　　　　this.data = data;
　　　　} // end setData
　　　　public Node getNextNode() {
　　　　　　return next;
　　　　} // end getNextNode
　　　　public void setNextNode(Node next) {
　　　　　　this.next = next;
　　　　} // end setNextNode
　　} // end Node
} // end LinkedStack

在栈顶添加  O(1)

　　即在链表中添加一个项到链表头

/**
 * Adds a new entry to the top of this stack.
 * @param newEntry: An object to be added to the stack.
 */
@Override    // O(1)
public void push(T newEntry) {
　　topNode = new Node(newEntry, topNode);
} // end push

获取栈顶 O(1)

　　返回头结点指向的节点的数据域，栈为空抛出异常

/**
 * Retrieves this stack's top entry.
 * @return: The object at the top of the stack.
 * @throws: EmptyStackException if the stack is empty.
 */
@Override
public T peek() {
　　if (isEmpty()) {
　　　　throw new EmptyStackException();
　　}
　　else {
　　　　return topNode.getData();
　　} // end if
} // end peek
/**
 * Detects whether this stack is empty.
 * @return: True if the stack is empty.
 */
@Override
public boolean isEmpty() {
　　return topNode == null;
} // end isEmpty

　　将异常抽出为私有方法

public T peek() {
　　checkStactEmpty();
　　return topNode.getData();
} // end peek
private void checkStactEmpty() {
　　if (isEmpty()) {
　　　　throw new EmptyStackException();
　　} // end if
} // end checkStackEmpty

删除栈顶  O(1) 

　　即删除头结点指向的第一个节点，处理栈为空的异常

/**
 * Romoves and returns this stack's top entry.
 * @return: The object at the top of the stack.
 * @throws: EmptyStackException if the stack is empty before the operation.
 */
@Override
public T pop() {
　　T top = peek();  // Might throw EmptyStackException
　　assert topNode != null;
　　topNode = topNode.getNextNode();
　　return top;
} // end pop

其他方法

public boolean isEmpty() {
　　return topNode == null;
} // end isEmpty
public void clear() {
　　topNode = null;
} // end clear

总：

import java.util.EmptyStackException;

/**
 * A class of stacks whose entries are stored in a chain of nodes.
 * @author Administrator
 *
 * @param <T>
 */
public class LinkedStack<T> implements StackInterface<T> {
    private Node topNode;
    //private int numberOfEntries;
    
    public LinkedStack() {
        topNode = null;
    } // end default constructor

    /**
     * Adds a new entry to the top of this stack.
     * @param newEntry: An object to be added to the stack.
     */
    @Override    // O(1)
    public void push(T newEntry) {
        topNode = new Node(newEntry, topNode);
        //numberOfEntries++;
    } // end push

    /**
     * Romoves and returns this stack's top entry.
     * @return: The object at the top of the stack.
     * @throws: EmptyStackException if the stack is empty before the operation.
     */
    @Override
    public T pop() {
        T top = peek();  // Might throw EmptyStackException
        assert topNode != null;
        topNode = topNode.getNextNode();
        //numberOfEntries--;
        return top;
    } // end pop

    /**
     * Retrieves this stack's top entry.
     * @return: The object at the top of the stack.
     * @throws: EmptyStackException if the stack is empty.
     */
    @Override
    public T peek() {
        checkStactEmpty();
        return topNode.getData();    
    } // end peek

    private void checkStactEmpty() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } // end if
    } // end checkStackEmpty
    
    /**
     * Detects whether this stack is empty.
     * @return: True if the stack is empty.
     */
    @Override
    public boolean isEmpty() {
        //return numberOfEntries == 0;
        return topNode == null;
    } // end isEmpty

    /*
    public int getCurrentSize() {
        return numberOfEntries;
    }
    */
    
    /**
     * Removes all entries from this stack.
     */
    @Override
    public void clear() {
        topNode = null;
    } // end clear
    
    private class Node{
        private T data;       // Entry in stack
        private Node next;    // Link to next node
        public Node(T data, Node next) {
            super();
            this.data = data;
            this.next = next;
        } // end constructor
        public T getData() {
            return data;
        } // end getData
        public void setData(T data) {
            this.data = data;
        } // end setData
        public Node getNextNode() {
            return next;
        } // end getNextNode
        public void setNextNode(Node next) {
            this.next = next;
        } // end setNextNode
        
    } // end Node
} // end LinkedStack

6.2 基于数组的实现 

　　数组第一个位置为栈底，最后一个为栈顶

类的框架

public class ArrayStack<T> implements StackInterface<T> {
　　private T[] stack;      // Array of stack entries
　　private int topIndex;   // Index of top entry
　　private boolean initialized = false;
　　private static final int DEFAULT_CAPACITY = 50;
　　private static final int MAX_CAPACITY = 10000;
　　public ArrayStack() {
　　　　this(DEFAULT_CAPACITY);
　　} // end default constructor
　　public ArrayStack(int initialCapacity) {
　　　　checkCapacity(initialCapacity);
　　　　@SuppressWarnings("unchecked")
　　　　T[] tempStack = (T[])new Object[initialCapacity];
　　　　stack = tempStack;
　　　　topIndex = -1;
　　　　initialized = true;
　　} // end ArrayStack
　　private void checkCapacity(int capacity) {
　　　　if (capacity > MAX_CAPACITY) {
　　　　　　throw new IllegalStateException("Attempt to create a stack whose "
　　　　　　　　　　　　　　　　　　　　+ "capacity exceeds allowed maximum.");
　　　　} // end if
　　} // end checkCapacity
　　@Override
　　public void push(T newEntry) {
　　　　// TODO Auto-generated method stub
　　}
　　@Override
　　public T pop() {
　　　　// TODO Auto-generated method stub
　　　　return null;
　　}
　　@Override
　　public T peek() {
　　　　// TODO Auto-generated method stub
　　　　return null;
　　}
　　@Override
　　public boolean isEmpty() {
　　　　// TODO Auto-generated method stub
　　return false;
　　}
　　@Override
　　public void clear() {
　　　　// TODO Auto-generated method stub
　　}
} // end ArrayStack

在栈顶添加

　　不需要改变数组大小时，为O(1)，改变数组大小的操作是O(n)的，所以数组满时，push为O(n)。下一次又为O(1)，公平起见，所有push操作应均摊偶尔的数组调整改变的开销。即将数组倍增的开销分摊到栈的所有入栈操作上。除非必须多次地调整数组大小，否则每次push几乎都是O(1)的。

public void push(T newEntry) {
　　checkInitialization();
　　ensureCapacity();
　　stack[topIndex + 1] = newEntry;
　　topIndex++;
} // end push
private void ensureCapacity() {
　　if (topIndex == stack.length - 1) {  // If array is full, double its size
　　　　int newLength = stack.length * 2;
　　　　checkCapacity(newLength);
　　　　stack = Arrays.copyOf(stack, newLength);
　　} // end if
} // end ensureCapacity
// Throws an exception if this ovject is not initialized.
private void checkInitialization() {
　　if(!initialized) {
　　　　throw new SecurityException("ArrayStack object is not initialized properly.");
　　}
} // end checkInitialized
private void checkCapacity(int capacity) {
　　if (capacity > MAX_CAPACITY) {
　　　　throw new IllegalStateException("Attempt to create a stack whose "
　　　　　　　　　　　　　　　　　　+ "capacity exceeds allowed maximum.");
　　} // end if
} // end checkCapacity

获取栈顶  O(1)

　　注意栈空抛出异常

public T peek() {
　　checkInitialization();
　　checkStackEmpty();
　　return stack[topIndex];
} // end peek
public boolean isEmpty() {
　　return topIndex < 0;
} // isEmpty
private void checkStackEmpty() {
　　if (isEmpty()) {
　　　　throw new EmptyStackException();
　　} // end if
} // end checkStackEmpty

删除栈顶  O(1)

　　注意栈空抛异常

public T pop() {
　　T result = peek();
　　stack[topIndex] = null;
　　topIndex--;
　　return result;
} // end pop

isEmpty和clear方法

public boolean isEmpty() {
　　return topIndex < 0;
} // isEmpty
public void clear() {
　　while (!isEmpty()) {
　　　　pop();
　　} // end while
} // end clear

数组实现：

涉及到数组数据的方法均需要检查初始化是否成功；

peek，pop注意检查栈是否为空，为空则抛异常。

import java.util.Arrays;

public class ArrayStack<T> implements StackInterface<T> {
    private T[] stack;      // Array of stack entries
    private int topIndex;   // Index of top entry
    private boolean initialized = false;
    private static final int DEFAULT_CAPACITY = 50;
    private static final int MAX_CAPACITY = 10000;
    
    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    } // end default constructor
    
    public ArrayStack(int initialCapacity) {
        checkCapacity(initialCapacity);
        @SuppressWarnings("unchecked")
        T[] tempStack = (T[])new Object[initialCapacity];
        stack = tempStack;
        topIndex = -1;
        initialized = true;
    } // end ArrayStack

    private void checkCapacity(int capacity) {
        if (capacity > MAX_CAPACITY) {
            throw new IllegalStateException("Attempt to create a stack whose "
                    + "capacity exceeds allowed maximum.");
        } // end if
    } // end checkCapacity

    /**
     * Adds a new entry to the top of this stack.
     * @param newEntry: An object to be added to the stack.
     */
    @Override
    public void push(T newEntry) {
        checkInitialization();
        ensureCapacity();
        stack[topIndex + 1] = newEntry;
        topIndex++;
    } // end push

    
    private void ensureCapacity() {
        if (topIndex == stack.length - 1) {  // If array is full, double its size
            int newLength = stack.length * 2;
            checkCapacity(newLength);
            stack = Arrays.copyOf(stack, newLength);
        } // end if
    } // end ensureCapacity

    /**
     * Romoves and returns this stack's top entry.
     * @return: The object at the top of the stack.
     * @throws: EmptyStackException if the stack is empty before the operation.
     */
    @Override
    public T pop() {
        T result = peek();
        stack[topIndex] = null;
        topIndex--;
        return result;
    } // end pop

    /**
     * Retrieves this stack's top entry.
     * @return: The object at the top of the stack.
     * @throws: EmptyStackException if the stack is empty.
     */
    @Override
    public T peek() {
        checkInitialization();
        checkStackEmpty();
        return stack[topIndex];
    } // end peek

    @Override
    public boolean isEmpty() {
        return topIndex < 0;
    } // isEmpty
    
    private void checkStackEmpty() {
        if (isEmpty()) {
            throw new EmptyStackException();
        } // end if
    } // end checkStackEmpty

    // Throws an exception if this ovject is not initialized.
    private void checkInitialization() {
        if(!initialized) {
            throw new SecurityException("ArrayStack object is not initialized properly.");
        }
    } // end checkInitialized
    
    /**
     * Removes all entries from this stack.
     */
    @Override
    public void clear() {
        while (!isEmpty()) {
            pop();
        } // end while
    } // end clear
} // end ArrayStack

6.3 基于向量的实现

　　让栈按需增大的一种办法是将元素保存在可变大小的数组中，另一种办法是使用向量（vector）替代数组。向量是一个对象，其行为类似于高级数组。与数组中的项一样向量中的项也有下标，且从0开始。与向量不同的是，向量有设置或访问项的方法。可以创建一个指定大小的向量，而且它的大小按需增长，实现细节对客户隐藏。

6.3.1 Java类库：类Vector

　　Java类库中包含类Vector，其实例（称为向量）的行为类似于一个可变大小的数组，下面是实现ADT栈时会用到的Vector的构造方法和方法：

public Vector()

创建一个空向量或类似于数组的容器，初始大小为10.当向量需要扩展容量时，容量倍增。

public Vector(int initialCapacity)

创建一个带指定初始容量的空向量。当向量需要扩展容量时，容量倍增。

public boolean add(T newEntry)

将新元素添加到向量的末尾。数组扩增也是通过数组复制得到的。

public T remove(int index)

删除向量中指定下标的项并返回，后续操作和ArrayList相同，将后面的数据向前复制。

public void clear()

删除向量中的所有项。将所有项设为null。

public T lastElement()

返回向量中的最后一项。

public boolean isEmpty()

如果向量为空则返回真。

public int size()

返回向量中当前的元素个数。

　　注：Java类库中的类Vector在Java.util包中。向量类似于可变大小的数组，其元素有从0开始的下标。可以使用类中的方法来处理向量。

6.3.2 使用向量实现ADT栈

　　使用向量保存栈的元素，类似于使用数组保存栈的元素，但更容易。让向量的第一个元素指向栈底元素。所以，向量看起来与之前的数组一样。不需要维护栈顶元素的下标，可以从向量的大小推出这个下标，向量大小很容易得到。

　　注：如果使用向量实现栈，则向量的首元应该指向栈底元素。而向量最后的占用位置指向栈顶元素。

类的框架

　　实现栈的类首先要声明一个向量作为数据域，并在构造方法中分配向量。

import java.util.Vector;
/**
 * A class of stacks whose entries are stored in a vector.
 * @author Administrator
 *
 */
public class VectorStack<T> implements StackInterface<T> {
　　private Vector<T> stack;    // Last element is the top entry in stack
　　private boolean initialized = false;
　　private static final int DEFAULT_CAPACITY = 50;
　　private static final int MAX_CAPACITY = 10000;
　　public VectorStack() {
　　　　this(DEFAULT_CAPACITY);
　　} // end default constructor
　　public VectorStack(int initialCapacity) {
　　　　checkCapacity(initialCapacity);
　　　　stack = new Vector<>(initialCapacity);   // Size double as need
　　　　initialized = true;
　　} // end constructor
　　private void checkCapacity(int capacity) {
　　　　if (capacity > MAX_CAPACITY) {
　　　　　　throw new IllegalStateException("Attempt to create a stack whose "
　　　　　　　　　　　　　　　　　　　　　　+ "capacity exceeds allowed maximum.");
　　　　} // end if
　　} // end checkCapacity
} // end VectorStack

在栈顶添加

　　使用类Vector的方法add，可以将元素添加到向量尾，即栈顶。

public void push(T newEntry) {
　　checkInitialization();
　　stack.add(newEntry);
} // end push

获取栈顶

　　使用类Vector的方法lastElement，可以获取栈顶元素

public T peek() {
　　checkInitialization();
　　checkStackEmpty();
　　return stack.lastElement();
} // end peek

　删除栈顶

　使用Vector的方法remove，可以删除栈顶元素。方法的参数是向量最后一个元素的下标，因为那个元素是栈顶。下标是向量当前大小stack.size()减1.

public T pop() {
　　checkInitialization();
　　checkStackEmpty();
　　return stack.remove(stack.size() - 1);
} // end pop

类的其他方法

public boolean isEmpty() {
　　return stack.isEmpty();
} // end isEmpty
public void clear() {
　　stack.clear();
} // end clear

　　注：写VectorStack比写基于数组实现的代码容易，因为调用了Vector的方法，而运行时间要多于ArrayStack方法的运行时间。但是，多出的这些时间常常微不足道。

小结

链式实现中栈的操作都是O(1)的；

调整数组大小可避免栈满时不能容纳新元素。但是数组中往往含有未用的位置；

基于数组的实现中，栈操作是O(1)的。数组满时push为O(n),分摊所有入栈则为O(1)；

因为Vector的实现是基于动态可变大小的数组的，所以基于向量实现的栈的性能类似于基于数组实现的性能。