栈 Stack
您目前处于:编程  2013年06月20日

1. 栈 List

定义

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。

栈有时又叫做LIFO(后进先出)表,即last-in,first-out

现实中的栈

栈的接口

public interface StackInterface<T> {
    /**
     * 将新元素加到站定
     * @param newEntry 带插入站的对象 */
    public void push(T newEntry);
    /**
     * 删除并返回栈顶
     * @return 栈顶的对象,如果栈为空则返回null */
    public T pop();
    /**
     * 取出栈顶
     * @return 栈顶的对象,如果栈为空则返回null */
    public T peek();
    /**
     * 检查栈是否为空
     * @return 如果栈为空返回true */
    public boolean isEmpty();
    /**
     * 从栈中删除所有元素 */
    public void clear();
}

程序栈

当一个程序执行时,一个被称为程序计数器的专用存储单元指向当前指令。当一个方法被调用时,程序的运行时环境为这个方法创建一个称为活动记录或栈帧的对象,这个活动记录显示该方法在执行过程中的状态。具体说,活动记录含有方法的实参、局部变量和当前指令的引用,即程序计数器的一个副本。在这个方法被调用时,活动记录被压入称为程序栈(或者称为Java栈)中。

由于一个方法可以调用另一个方法,程序栈往往含有多个活动记录。位于栈顶的活动记录,属于当前正在执行的方法,紧接在栈顶下的记录,属于调用当前方法的方法。

Java类库:类Stack

public class Stack<T> {
                              
    public T push(T item);
    public T pop();
    public T peek();
    public boolean empty();
    /**
     * 在栈中查找指定对象
     * @param desiredItem 待查找的对象
     * @return 如果desiredItem在栈中,则返回其位置;如果不在则返回-1;栈顶的位置是-1 */
    public int search(T desiredItem);
    /**
     * @return 栈的一个遵循Java接口的Iterator的迭代器 */
    public Iterator<T> iteraotr();
    /**
     * @return 栈的一个遵循Java接口ListIterator的迭代器 */
    public ListIterator<T> listIterator();
}

2. 基于链表的实现

如果用链表表示栈,则第一个结点应该引用栈顶元素。

类的框架

栈的链表实现有一个数据域topNode,它是链表的表头引用,默认构造函数将这个数据域设置为null。

public class LinkedStack<T> implements StackInterface<T>, Serializable {
    private Node topNode; //引用链表中第一个结点
    public LinkedStack() {
        topNode = null;
    }
    private class Node implements Serializable {
        private T data; //栈的元素
        private Node next; //指向下一个结点的连接
    }
    // 在栈顶插入
    public void push(T newEntry) {
        Node newNode = new Node(newEntry, topNode);
        topNode = newNode;
    }
    // 删除栈顶
    public T pop() {
        T top = null;
        if (topNode != null) {
            top = topNode.getData();
            topNode = topNode.getNext();
        }
        return top;
    }
    // 检索栈顶
    public T peek() {
        T top = null;
        if (topNode != null)
            top = topNode.getData();
        return top;
    }
    public boolean isEmpty() {
        return topNode == null;
    }
    public void clear() {
        topNode = null;
    }
}

3. 基于数组的实现

public class ArrayStack<T> implements StackInterface<T>, Serializable {
    private T[] stack; //存放栈元素的数组
    private int topIndex; // 栈顶元素索引
    private static final int DEFAULT_MAX_SIZE = 50;
    public ArrayStack() {
        this(DEFAULT_MAX_SIZE);
    }
    public ArrayStack(int initialCapacity) {
        stack = (T[]) new Object[initialCapacity];
        topIndex = -1;
    }
    // 在栈顶插入
    public void push(T newEntry) {
        topIndex++;
        if (topIndex >= stack.length) {
            //若数组已满,扩展数组
        }
        stack[topIndex] = newEntry;
    }
    // 删除栈顶
    public T pop() {
        T top = null;
        if (!isEmpty()) {
            top = stack[topIndex];
            stack[topIndex] = null;
            topIndex--;
        }
        return top;
    }
    // 检索栈顶
    public T peek() {
        T top = null;
        if (!isEmpty())
            top = stack[topIndex];
        return top;
    }
    public boolean isEmpty() {
        return topIndex < 0;
    }
    public void clear() {
        stack = null;
    }
}

4. 基于向量的实现

public class VectorStack<T> implements StackInterface<T>, Serializable {
    private Vector<T> stack; //栈顶是最后一个元素
    public VectorStack() {
        stack = new Vector(); // 需要时向变量大小将成倍增加
    }
    public VectorStack(int maxSize) {
        stack = new Vector(maxSize);
    }
    // 在栈顶插入
    public void push(T newEntry) {
        stack.addElement(newEntry);
    }
    // 删除栈顶
    public T pop() {
        T top = null;
        if (!isEmpty()) {
            top = stack.lastElement();
            stack.removeElement(stack.size() - 1);
        }
        return top;
    }
    // 检索栈顶
    public T peek() {
        T top = null;
        if (!isEmpty())
            top = stack.lastElement();
        return top;
    }
    public boolean isEmpty() {
        return stack.isEmpty();
    }
    public void clear() {
        stack.removeAllElements();
    }
}

转载请并标注: “本文转载自 linkedkeeper.com ”