栈（Stack）

Stack 定义

是限定在仅在表尾进行插入和删除操作的线性表。表尾端成为栈顶（top），表头端称为栈底（bottom），不含元素的空表成为空栈。在栈顶进行元素的插入和删除，是一先进后出的线性表。

栈的存储表示方式

1. 顺序栈

   栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时指针top指示栈顶元素在循序栈中的位置。

2. 链式栈

• 插入和删除元素操作仅仅在链头位置进行

• 栈顶指针就是链表头指针

实现

Java

package stack;

/**
 * 基于数组实现的顺序栈
 *
 * @param 
 */
public class Stack {

    private Object[] data = null;
    /**
     * 栈的容量
     */
    private int maxSize = 0;
    /**
     * 栈顶的指针(下标)
     */
    private int top = -1;

    Stack() {
        this(10);
    }

    public Stack(int initialSize) {
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            top = -1;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }

    /**
     * 入栈
     *
     * @param e
     */
    public boolean push(E e) {
        if (top == maxSize - 1) {
            throw new RuntimeException("栈已满，元素无法入栈");
        } else {
            data[++top] = e;
            return true;
        }
    }

    /**
     * 出栈
     */
    public E pop() {
        if (top == -1) {
            throw new RuntimeException("空栈");
        } else {
            return (E) data[top--];
        }
    }

    /**
     * 只查询栈顶元素
     */
    public E peek() {
        if (top == -1) {
            throw new RuntimeException("空栈");
        } else {
            return (E) data[top--];
        }
    }

    public static void main(String[] args) {
        Stack s = new Stack();
        s.push("1");
        s.push("2");
        s.push("3");
        System.out.println(s.pop());
        System.out.println(s.peek());
    }
}

参考

《数据结构 （C语言版）》 严蔚敏

《Java面试核心知识点》 王磊