数据结构与算法(2): 线性结构-栈

栈：一种线性存储结构，是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。

• 栈中数据是按照“先进后出（LIFO）”方式进行出栈的
• 栈通常包括三种的三种操作：push（向栈中添加元素）、peek（返回栈顶元素）、pop（返回并删除栈顶元素）

栈的实现方式

数组实现

/**
 * 栈: 数组实现
 */
public class ArrayStack<T> {
    private Object[] elementData;

    // 栈顶位置
    int top;

    public ArrayStack(int maxSize) {
        this.elementData = new Object[maxSize];
        this.top = -1;
    }

    /**
     * 获取栈中元素的个数
     * Returns the number of elements in this stack.
     * @return
     */
    public int size(){
        return top + 1;
    }

    /**
     * 判断栈空
     * @return
     */
    public boolean isEmpty(){
        return top == -1;
    }

    /**
     * 判断栈满
     * @return
     */
    public boolean isFull(){
        return top == elementData.length - 1;
    }

    /**
     * 入栈: 依次加入数据
     * @param data
     * @return
     */
    public boolean push(Object data) throws Exception {
        if (isFull()){
            throw new Exception("栈满");
        }

        this.elementData[++top] = data;
        return true;
    }

    /**
     * 出栈: 从栈顶取出元素
     * @return
     * @throws Exception
     */
    @SuppressWarnings("unchecked")
    public T pop() throws Exception {
        if (isEmpty()){
            throw new Exception("栈空");
        }

        return (T) this.elementData[top--];
    }

    /**
     * 返回栈顶元素
     * @return
     */
    @SuppressWarnings("unchecked")
    public T peek(){
        return (T) this.elementData[top];
    }
}

单链表实现

/**
 * Created by Roger on 2016/10/26.
 * 栈: 单链表实现
 */
public class SingleLinkedListStack<T> {

    private SingleLinkedList<T> elementList;

    public SingleLinkedListStack() {
        this.elementList = new SingleLinkedList<>();
    }

    /**
     * 入栈
     * @param v
     */
    public void push(T v){
        elementList.add(0, v);
    }

    /**
     * 出栈: 单链表的实现，栈顶始终位于索引为0的结点
     * @return
     * @throws Exception
     */
    public T pop() throws Exception {
        if (elementList.isEmpty()){
            throw new Exception("栈为空");
        }
        return elementList.remove(0);
    }

    /**
     * 返回栈顶元素
     * @return
     */
    public T peek(){
        return elementList.get(0);
    }

    /**
     * 判断栈空
     * @return
     */
    public boolean isEmpty(){
        return elementList.size() == 0;
    }

    public int size(){
        return elementList.size();
    }
}

---

栈的应用

平衡符号

编译器检查程序的语法错误，这个可以利用栈来实现。做一个空栈，读入字符直到文件末尾，如果字符是一个开放符号，则将其入栈；如果字符是一个封闭符号，则当栈空的时候报错，否则将栈元素弹出，如果弹出的不是对应的开放符号，则报错。文件结尾时，栈非空也报错。

表达式的记法

中缀表达式

就是常用的将操作符放在操作数中间的算术表达式，中缀表达式是人们常用的算术表示方法。
eg: (1 + 2) * 3 - 4

前缀表达式（波兰式记法）

将运算符写在前面操作数写在后面的不包含括号的表达式。
eg: - * + 1 2 3 4

后缀表达式（逆波兰式记法）

运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。
eg: 1 2 + 3 * 4 -

前缀表达式计算求值

1. 从右至左 扫描表达式，遇到数字时，将数字压入堆栈;
2. 遇到运算符时，弹出栈顶的两个数，用运算符做相应的计算，并将结果入栈；
3. 重复上述过程直到表达式扫描完毕，最后运算得出的值即为表达式的结果。

中缀表达式转换为前缀表达式

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级
   • 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   • 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
   • 否则，将S1栈顶的运算符弹出并压入到S2中；
5. 遇到括号时
   • 如果是右括号“)”，则直接压入S1；
   • 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤2~5，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次从栈顶弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

后缀表达式计算求值

1. 从左至右 扫描表达式，遇到数字时，将数字压入堆栈；
2. 遇到运算符时，弹出栈顶的两个数，用运算符做相应的计算，并将结果入栈；
3. 重复上述过程直到表达式扫描完毕，最后运算得出的值即为表达式的结果。

中缀表达式转换为后缀表达式

1. 初始化两个栈：运算符栈S1和输出队列D2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其存入D2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级
   • 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   • 否则，若优先级比栈顶运算符的高，也将运算符压入S1（++注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况++）；
   • 否则，将S1栈顶的运算符弹出并存入到D2中；
5. 遇到括号时
   • 如果是左括号“(”，则直接压入S1；
   • 如果是右括号“)”，则依次弹出S1栈顶的运算符，并存入D2，直到遇到左括号为止，此时将这一对括号丢弃；
6. 重复步骤2~5，直到表达式的最右边；
7. 将S1中剩余的运算符依次弹出并存入D2；
8. 队列D2依次出队，结果即为中缀表达式对应的后缀表达式。

注：该部分引用自http://blog.csdn.net/antineutrino/article/details/6763722

方法调用

当调用一个新方法时，主调方法的所有局部变量需要由系统存储起来，否则被调用的新方法将会重写由主调方法的变量所使用的内存，不仅如此，该主调方法的当前位置也必须存储，以便在新方法运行完后知道向哪转移。

方法调用和方法返回的问题类似于平衡符号问题中的开括号和闭括号。

---