計算機中的棧

我們把生活中的棧的概念引入到計算機中灾锯，就是供數(shù)據(jù)休息的地方，它是一種數(shù)據(jù)結構嗅榕，數(shù)據(jù)既可以進入到棧中顺饮，又可以從棧中出去。
數(shù)據(jù)結構FILO（先進后出）【疊羅漢凌那，上面的先下來】不同于隊列中的FIFO（先進先出）【水管流水兼雄，只能從一端輸出，和固定的一端方向刪除】
棧是一種只能在一端進行插入和刪除操作的特殊線性表帽蝶。它按照先進后出的原則存儲數(shù)據(jù)赦肋，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂励稳，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）佃乘。我們稱數(shù)據(jù)進入到棧的動作為壓棧，數(shù)據(jù)從棧中出去的動作為彈棧驹尼。

代碼實現(xiàn)（通過鏈表來實現(xiàn)）

public class MyStack<T> implements Iterable<T>{
    Node head ;
    int N;
    public MyStack(){
        this.head = new Node(null,null);
        this.N = 0;
    }


    class Node{
        T item;
        Node next;
        public Node(T item ,Node next){
            this.item = item;
            this.next =next;
        }
    }
    public void clear(){
        head.next = null;
        N = 0;
    }
    public boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return this.N;
    }

    public T pop(){
        Node oldNext = this.head;
        if(oldNext == null){
            return null;
        }
        this.head.next = oldNext.next.next;
        this.N --;
        return oldNext.item;
    }

    public void push(T t){
        Node curr = this.head.next;
        Node newNode = new Node(t, curr);
        this.head.next = newNode;
    }
    @Override
    public Iterator<T> iterator() {
        return new MyIterator();
    }
    private class MyIterator implements Iterator<T>{
        Node node = head ;
        @Override
        public boolean hasNext() {
            return node.next!=null;
        }

        @Override
        public T next() {
            node = node.next;
            return node.item;
        }
    }
}

棧的使用案例（逆波蘭表達式）

逆波蘭表達式求值問題是我們計算機中經(jīng)常遇到的一類問題扶欣，要研究明白這個問題鹅巍，首先我們得搞清楚什么是逆波蘭表達式？要搞清楚逆波蘭表達式料祠，我們得從中綴表達式說起骆捧。

中綴表達式：

• 中綴表達式就是我們平常生活中使用的表達式，例如：1+3*2,2-(1+3)等等髓绽，中綴表達式的特點是：二元運算符總是置于兩個操作數(shù)中間敛苇；

• 中綴表達式是人們最喜歡的表達式方式，因為簡單顺呕，易懂枫攀。但是對于計算機來說就不是這樣了，因為中綴表達式的運算順序不具有規(guī)律性株茶。不同的運算符具有不同的優(yōu)先級来涨，如果計算機執(zhí)行中綴表達式，需要解析表達式語義启盛，做大量的優(yōu)先級相關操作蹦掐。

逆波蘭表達式(后綴表達式)：逆波蘭表達式是波蘭邏輯學家J?盧卡西維茲(J? Lukasewicz)于1929年首先提出的一種表達式的表示方法，后綴表達式的特點：運算符總是放在跟它相關的操作數(shù)之后僵闯。

中綴表達式與逆波蘭表達式轉換表：

假設需求：

給定一個只包含加減乘除四種運算的逆波蘭表達式的數(shù)組卧抗，求出該逆波蘭表達式的結果。
中綴表達式：5*(21-3)+21/7
逆波蘭表達式：5 21 3 - * 21 7 / +

1.創(chuàng)建一個棧對象expression存儲操作數(shù);
2.從左往右遍歷逆波蘭表達式鳖粟，得到每一個字符串;
3.判斷該字符串是不是運算符社裆，如果不是，把該該操作數(shù)壓入oprands棧中;
4.如果是運算符向图，則從expression棧中彈出兩個操作數(shù)o1,o2;
5.使用該運算符計算o1和o2泳秀，得到結果result;
6.把該結果壓入expression棧中;
7.遍歷結束后，拿出棧中最終的結果返回;

代碼實現(xiàn)

class MyStackTest{
    public static void main(String[] args) {
        int i = 5 * (21 - 3) + 21 / 7;
        System.out.println("中綴表達式計算結果："+i);
        String[] str = {"5", "21", "3", "-", "*", "21", "7", "/", "+"};
        Integer calculation = calculation(str);
        System.out.println("逆波蘭表達式計算結果："+calculation);


    }
    public static Integer calculation(String[] arr){
        MyStack<Integer> expression = new MyStack<>();
        for (String s : arr) {
            Integer o1,o2,result;
            switch (s){
                case "+":
                    o1 = expression.pop();
                    o2 = expression.pop();
                    result = o2 + o1;
                    expression.push(result);
                    break;
                case "-":
                    o1 = expression.pop();
                    o2 = expression.pop();
                    result = o2 - o1;
                    expression.push(result);
                    break;
                case "*":
                    o1 = expression.pop();
                    o2 = expression.pop();
                    result = o2 * o1;
                    expression.push(result);
                    break;
                case "/":
                    o1 = expression.pop();
                    o2 = expression.pop();
                    result = o2 / o1;
                    expression.push(result);
                    break;
                default:
                    expression.push(Integer.parseInt(s));
            }
        }
        return expression.pop();
    }
}