数据结构(一) -- 栈

一，栈

栈是存放对象的一种特殊容器，在插入与删除对象时，这种结构遵循后进先出（Last-in-first-out，LIFO）的原则--也就是说，对象可以任意插入栈中，但每次取出的都是此前插入的最后一个对象。
比如一摞椅子，只能将最顶端的椅子移出，也只能将新椅子放到最顶端--这两种操作分别称作入栈（Push）和退栈（Pop）。

栈是最基本的数据结构之一，在实际应用中几乎无所不在。例如，网络浏览器会将用户最近访问过的地址组织为一个栈：用户每访问一个新页面，其地址就会被存放至栈顶；而用户每次按下“Back”按钮，最后一个被记录下的地址就会被清除掉。再如，当今主流的文本编辑器大都支持编辑操作的历史记录功能：用户的编辑操作会被依次记录在一个栈中；一旦出现误操作，用户只需按下“Undo”按钮，即可撤销最近一次操作并回到此前的编辑状态。

由于栈的重要性，在Java 的java.util 包中已经专门为栈结构内建了一个类--java.util.Stack

---

二，栈ADT(AbstractDataType)

作为一种抽象数据类型，栈必须支持以下方法：

操作方法	功能描述
push(x)	将对象x 压至栈顶 输入：一个对象 输出：无
pop()	若栈非空，则将栈顶对象移除，并将其返回否则，报错 输入：无 输出：对象

此外，还可以定义如下的方法：

操作方法	功能描述
getSize()	返回栈内当前对象的数目 输入：无 输出：非负整数
isEmpty()	检查栈是否为空 输入：无 输出：布尔标志
top()	若栈非空，则返回栈顶对象（但并不移除）否则，报错 输入：无 输出：栈顶对象

---

三，基于数组的简单实现

先定义一个Stack接口：

public interface Stack {
    public int getSize();//返回栈中元素数目
    public boolean isEmpty();//判断栈是否为空
    public Object top() throws ExceptionStackEmpty;//取栈顶元素（但不删除）
    public void push (Object ele) throws ExceptionStackFull;//入栈
    public Object pop() throws ExceptionStackEmpty;//出栈
}

定义用到的两个异常：
一个stack空异常

/*
* 当试图对空栈应用pop或top方法时，本意外将被抛出
*/
package dsa;
    public class ExceptionStackEmpty extends RuntimeException {
    public ExceptionStackEmpty(String err) {
        super(err);
    }
}

一个stack满异常

/*
* 当试图对满栈应用push方法时，本意外将被抛出
*/
package dsa;
    public class ExceptionStackFull extends RuntimeException {
    public ExceptionStackFull (String err) {
        super(err);
    }
}

为了实现栈接口，我们可以用一个数组来存放其中的元素。具体来说，就是使用一个容量为N的数组S，再加上一个变量top 来只是当前栈顶的位置。

由于Java数组的元素都是从0 开始编号，所以top必须初始化为-1；反过来，只要top = -1，就说明栈为空。

基于数组的栈实现细节：

/*
* 借助定长数组实现Stack接口
*/
package dsa;
public class Stack_Array implements Stack {
    public static final int CAPACITY = 1024;//数组的默认容量
    protected int capacity;//数组的实际容量
    protected Object[] S;//对象数组
    protected int top = -1;//栈顶元素的位置
    //按默认容量创建栈对象
    public Stack_Array()
    { this(CAPACITY); }
    //按指定容量创建栈对象
    public Stack_Array(int cap) {
        capacity = cap;
        S = new Object[capacity];
    }
    //获取栈当前的规模
    public int getSize()
    { return (top + 1); }
    //测试栈是否为空
    public boolean isEmpty()
    { return (top < 0); }
    //入栈
    public void push(Object obj) throws ExceptionStackFull {
        if (getSize() == capacity)
        throw new ExceptionStackFull("意外：栈溢出");
        S[++top] = obj;
    }
    //取栈顶元素
    public Object top() throws ExceptionStackEmpty {
        if (isEmpty())
        throw new ExceptionStackEmpty("意外：栈空");
        return S[top];
    }
    //出栈
    public Object pop() throws ExceptionStackEmpty {
        Object elem;
        if (isEmpty())
        throw new ExceptionStackEmpty("意外：栈空");
        elem = S[top];
        S[top--] = null;
        return elem;
    }
}

---

四，栈应用实例

• ** Tip借助栈进行数组倒置**

   public static Integer[] reverse(Integer[] a) {
    Stack_Array S = new Stack_Array(a.length);
    Integer[] b = new Integer[a.length];
    for (int i = 0; i < a.length; i++)
        S.push(a[i]); // 所有元素顺序入栈
    for (int i = 0; i < a.length; i++)
        b[i] = (Integer) (S.pop()); // 逆序退栈
    return b;
  }
  

• ** 括号匹配算法**

• ** HTML文档的标志匹配**