99这里视只精品,青青草超碰国产

本文首發(fā)于 LOGI'S BLOG，由作者轉(zhuǎn)載。

棧 是一種操作受限的線性表，只支持從一端插入和刪除。后進(jìn)先出是它的最大特點(diǎn)。棧既可用數(shù)組也可用鏈表實(shí)現(xiàn)，前者叫順序棧，后者叫鏈棧，無(wú)論哪種，出入棧操作的時(shí)間復(fù)雜度都是 O(1)。從功能上說，數(shù)組和鏈表都可代替棧，但特定的數(shù)據(jù)結(jié)構(gòu)是對(duì)特定場(chǎng)景的抽象，盡管數(shù)組和鏈表操作靈活，但它們暴露了太多接口，使用時(shí)不可控因素增多，自然也就更容易出錯(cuò)。當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿足后進(jìn)先出、先進(jìn)后出的特性時(shí)，就應(yīng)首選棧這種數(shù)據(jù)結(jié)構(gòu)。

現(xiàn)實(shí)生活中的棧

我們平時(shí)放盤子的時(shí)候，都是從下往上一個(gè)一個(gè)放；取的時(shí)候從上往下一個(gè)一個(gè)取，不能從中間任意抽出，這種先進(jìn)后出的結(jié)構(gòu)便是棧。

順序棧的實(shí)現(xiàn)

class ArrayBasedStack {
    Object[] items;
    int capacity;
    int size;

    public ArrayBasedStack(int capacity) {
        this.items = new Object[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    // 入棧
    public void push(Object item) {
        // 動(dòng)態(tài)擴(kuò)容
        if (this.capacity == this.size) {
            this.capacity = this.capacity << 1;
            Object[] newItems = new Object[this.capacity];
            System.arraycopy(items, 0, newItems, 0, this.size);
            /*
            for (int i = 0; i < this.size; i++) {
                newItems[i] = this.items[i];
            }
            */
            this.items = newItems;
        }
        this.items[this.size++] = item;
    }

    // 出棧
    public Object pop() {
        return this.size == 0 ? null : this.items[--this.size];
    }
}

鏈?zhǔn)綏５膶?shí)現(xiàn)

class SinglyLinkedListBasedStack {
    SinglyLinkedListNode head;
    int size;

    public void push(Object item) {
        SinglyLinkedListNode current = new SinglyLinkedListNode(item);
        current.next = this.head.next;
        this.head.next = current;
        this.size++;
    }

    public Object pop() {
        SinglyLinkedListNode current = this.head.next;
        if (current != null) {
            this.head.next = this.head.next.next;
        }
        this.size--;
        return current;
    }
}

class SinglyLinkedListNode {
    SinglyLinkedListNode next;
    Object item;

    public SinglyLinkedListNode(Object item) {
        this.item = item;
    }
}

出入棧的時(shí)空復(fù)雜度分析

對(duì)于鏈?zhǔn)綏?，push 操作實(shí)際上是鏈表頭插，時(shí)間復(fù)雜度為 O(1)。pop 操作是刪除第一個(gè)有效節(jié)點(diǎn)，時(shí)間復(fù)雜度同樣為 O(1)。兩個(gè)操作都未使用額外空間，因此空間復(fù)雜度為 O(1)。

對(duì)于順序棧，push 操作在鏈表滿時(shí)需要數(shù)據(jù)搬移，時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)，這是最壞情況。最好情況是數(shù)組未滿，直接將 item 放入 size 位置，時(shí)空復(fù)雜度都是 O(1)。pop 操作直接返回 size-1 位置，時(shí)空復(fù)雜度都是 O(1)。

我們發(fā)現(xiàn)，順序棧的 push 操作，大多數(shù)情況下可在 O(1) 時(shí)間完成，只有少數(shù)情況需要 O(n) 時(shí)間，并且它們之間存在時(shí)間先后關(guān)系，具體是，每 n-1 次 O(1) 操作跟隨 1 次 O(n) 操作。在算法的時(shí)空復(fù)雜度分析這篇文章中，我們介紹過，遇到上述情況，在分析平均復(fù)雜度時(shí)，應(yīng)使用攤還分析代替平均加權(quán)，得到均攤復(fù)雜度，并且通常情況下，均攤復(fù)雜度等于最好情況復(fù)雜度。本例中，將 n 個(gè)數(shù)據(jù)搬移均攤到 n 次上，相當(dāng)于一次只需一次搬移，均攤復(fù)雜度為 O(1)，這也更符合較長(zhǎng)時(shí)間的性能測(cè)量。

// 順序棧 push 操作的時(shí)間復(fù)雜度
// 第一行為次數(shù)
// 第二行為每次的時(shí)間復(fù)雜度
|-  n  -| 1 |- n-1 -| 1 |- n-1 -|
1,1,...,1,n,1,1,...,1,n,1,1,...,1,...

棧的常規(guī)應(yīng)用

處理函數(shù)調(diào)用

我們知道，操作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存空間被組織成棧，用來(lái)存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量。每進(jìn)入一個(gè)函數(shù)，操作系統(tǒng)便將臨時(shí)變量作為棧幀入棧，當(dāng)調(diào)用結(jié)束返回后，再將該棧幀出棧。通過模擬以下代碼的執(zhí)行過程，可以得到函數(shù)調(diào)用棧的結(jié)構(gòu)。

int main() {
   int a = 1;
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   return 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

下圖顯示了執(zhí)行到 add 函數(shù)時(shí)，函數(shù)調(diào)用棧的棧幀分布情況。

|  ·  |-----
|  ·  |  |
|  ·  |
|sum=0| add
|  x=3|
|  y=5|  |
|  ·  |-----
|  ·  |  |
|  ·  |
|res=0| main
|ret=0|
|  a=1|  |
-----------

為什么函數(shù)調(diào)用要用 “棧” 來(lái)保存臨時(shí)變量呢？用其他數(shù)據(jù)結(jié)構(gòu)不行嗎？

其實(shí)，我們不一定非要用棧來(lái)保存臨時(shí)變量，只不過如果這個(gè)函數(shù)調(diào)用符合后進(jìn)先出的特性，用棧這種數(shù)據(jù)結(jié)構(gòu)是最順理成章的選擇。

從調(diào)用函數(shù)進(jìn)入被調(diào)用函數(shù)，對(duì)于數(shù)據(jù)來(lái)說，變化的是什么呢？是作用域。所以從根本上，只要能保證每進(jìn)入一個(gè)新的函數(shù)，都是一個(gè)新的作用域就可以。而要實(shí)現(xiàn)它，用棧就非常方便。在進(jìn)入被調(diào)用函數(shù)的時(shí)候，分配一段棧空間給這個(gè)函數(shù)的變量，在函數(shù)結(jié)束的時(shí)候，將棧頂復(fù)位，正好回到調(diào)用函數(shù)的作用域內(nèi)。

瀏覽器的前進(jìn)后退

思路：

初始化兩個(gè)棧 X 和 Y，把首次瀏覽的頁(yè)面壓入 X
當(dāng)點(diǎn)擊后退時(shí)，依次從 X 出棧，并將其壓入 Y 中
當(dāng)點(diǎn)擊前進(jìn)時(shí)，依次從 Y 出棧，并將其壓入 X 中
打開新頁(yè)面時(shí)，應(yīng)清空前進(jìn)棧 Y
當(dāng) X 中無(wú)數(shù)據(jù)時(shí)，則說明沒有頁(yè)面可以后退了
當(dāng) Y 中無(wú)數(shù)據(jù)時(shí)，則說明沒用頁(yè)面可以前進(jìn)了

舉例：

打開 A，B，C 三個(gè)頁(yè)面，X 和 Y 的棧幀如下

|C|        | |
|B|        | |
|A|        | |
---        ---
 X          Y

點(diǎn)擊兩次后退，從 C 退 B 再退到 A 頁(yè)面

| |        | |
| |        |B|
|A|        |C|
---        ---
 X          Y

點(diǎn)擊前進(jìn)，回到 B 頁(yè)面

| |        | |
|B|        | |
|A|        |C|
---        ---
 X          Y

打開新頁(yè)面 D，從邏輯上講，D 時(shí)最新頁(yè)面，不存在更前面的頁(yè)面了，需要清空 Y

|D|        | |
|B|        | |
|A|        | |
---        ---
 X          Y

括號(hào)匹配

問題：

假設(shè)表達(dá)式中允許三種括號(hào)：圓括號(hào)、方括號(hào)和大括號(hào)。編寫一個(gè)算法，判斷表達(dá)式中的各種左括號(hào)是否與右括號(hào)匹配。例如，輸入 2+(3+4)2+{[3]}-8，輸出匹配正確；輸入 2+(3+4[2)+{[3]}-8，輸出匹配錯(cuò)誤。

思路：

初始化一個(gè)棧，從左到右掃描表達(dá)式。掃描到左括號(hào)時(shí)入棧。掃描到右括號(hào)時(shí)，棧頂彈出，若能匹配，則繼續(xù)掃描，否則匹配失敗。當(dāng)表達(dá)式掃描結(jié)束后，若棧為空，則匹配成功，否則匹配失敗。

復(fù)雜度：

時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)。

實(shí)現(xiàn)：

public boolean braceMatching(String expression) {
    ArrayBasedStack<Character> stack = new ArrayBasedStack<>(8);
    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        switch (c) {
            case '(':
            case '[':
            case '{':
                stack.push(c);
                break;
            case ')':
                if (stack.pop() != '(') {
                    return false;
                }
                break;
            case ']':
                if (stack.pop() != '[') {
                    return false;
                }
                break;
            case '}':
                if (stack.pop() != '{') {
                    return false;
                }
                break;
        }
    }
    if (stack.size != 0) {
        return false;
    }
    return true;
}

算術(shù)表達(dá)式求值

問題：

輸入算術(shù)表達(dá)式，輸出其運(yùn)算結(jié)果。為了簡(jiǎn)化問題，我們只考慮 +、-、*、/ 四種運(yùn)算，他們的優(yōu)先級(jí)規(guī)則如下：

先乘除，后加減
從左算到右
先括號(hào)內(nèi)，再括號(hào)外

算符優(yōu)先法

思路：

設(shè)置兩個(gè)工作棧，一個(gè)存儲(chǔ)操作數(shù)，另一個(gè)存儲(chǔ)操作符
自左向右掃描算術(shù)表達(dá)式，遇到操作數(shù)直接入操作數(shù)棧
若遇到操作符，則根據(jù)算符優(yōu)先規(guī)則決定下一步操作：若優(yōu)先級(jí)高于棧頂操作符則入棧。否則，彈出棧頂算符，并從操作數(shù)棧彈出兩個(gè)操作數(shù)計(jì)算，將計(jì)算結(jié)果入操作數(shù)棧。繼續(xù)與棧頂操作符比較優(yōu)先級(jí)，若相等或低于，則再計(jì)算，直至大于之，此時(shí)方可將操作符入棧
左括號(hào)一定入棧，且優(yōu)先級(jí)低于后續(xù)任何算符，即優(yōu)先級(jí)高于括號(hào)前，低于括號(hào)中。右括號(hào)一定出棧計(jì)算，直至遇到左括號(hào)，即低于括號(hào)中
掃描完畢后，由于剩余算符的優(yōu)先級(jí)相同，直接依次出棧計(jì)算，結(jié)果入操作數(shù)棧，當(dāng)操作符?？諘r(shí)，計(jì)算結(jié)束

復(fù)雜度：

時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)。

實(shí)現(xiàn)：

public class StackReview {
    public static void main(String[] args) {
        String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
        System.out.println(arithmeticExpression + " = " + new StackReview().calculate(arithmeticExpression));
    }

    public double calculate(String arithmeticExpression) {
        SinglyLinkedListBasedStack<Double> operands = new SinglyLinkedListBasedStack<>();
        SinglyLinkedListBasedStack<Character> operators = new SinglyLinkedListBasedStack<>();
        for (int i = 0; i < arithmeticExpression.length(); i++) {
            char c = arithmeticExpression.charAt(i);
            switch (c) {
                case '(':
                    operators.push(c);
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                    while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
                        operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
                    }
                    operators.push(c);
                    break;
                case ')':
                    while (operators.getTop() != '(') {
                        operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
                    }
                    // '()' 匹配完畢，'(' 出棧
                    operators.pop();
                    break;
                default:
                    operands.push((double) (c - '0'));
                    break;
            }
        }
        // 剩余算符優(yōu)先級(jí)相同，直接依次出棧
        while (operators.size > 0) {
            operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
        }
        return operands.pop();
    }

    public boolean isGreater(char operator1, char operator2) {
        if (operator1 == '/' || operator2 == '(') {
            // 自左向右，/ 比 * 優(yōu)先級(jí)高。括號(hào)里面必須先算
            return true;
        } else if (operator1 == '-' && operator2 == '+') {
            // 自左向右，- 比 + 優(yōu)先級(jí)高
            return true;
        } else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
            return true;
        }
        return false;
    }

    public double calSubExpress(double operand1, double operand2, char operator) {
        double result = 0;
        switch (operator) {
            case '+':
                // 第二個(gè)數(shù)在前，因?yàn)樗热霔?                result = operand2 + operand1;
                break;
            case '-':
                result = operand2 - operand1;
                break;
            case '*':
                result = operand2 * operand1;
                break;
            case '/':
                result = operand2 / operand1;
                break;
        }
        return result;
    }
}

后綴表達(dá)式法

步驟：

將中綴表達(dá)式轉(zhuǎn)為后綴
根據(jù)后綴表達(dá)式求值

后綴的定義：

后綴表達(dá)式，指的是不包含括號(hào)，運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的后面，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）。

舉例：

前綴表達(dá)式：操作符在操作數(shù)的前面，比如 +-543
中綴表達(dá)式：操作符在操作數(shù)的中間，這也是人類最容易識(shí)別的算術(shù)表達(dá)式 3+4-5
后綴表達(dá)式：操作符在操作數(shù)的后面，比如 34+5-

中綴轉(zhuǎn)后綴：

設(shè)置兩個(gè)棧，一個(gè)儲(chǔ)存算符，另一個(gè)儲(chǔ)存后綴表達(dá)式
自左向右掃描中綴表達(dá)式，遇到數(shù)字直接入后綴表達(dá)式棧
遇到操作符，比較其與算符棧頂?shù)膬?yōu)先級(jí)：
1. 若不高于棧頂算符優(yōu)先級(jí)，則棧頂出棧并入后綴表達(dá)式棧，繼續(xù)比較后續(xù)棧頂符號(hào)，直到遇到低于自己的符號(hào)，此時(shí)入操作符棧
2. 高于棧頂算符優(yōu)先級(jí)，直接入操作符棧
3. 左括號(hào)直接入操作符棧
4. 右括號(hào)不入棧，且依次彈出棧內(nèi)操作符并入后綴表達(dá)式棧，直到遇到左括號(hào)，將左括號(hào)也出棧
掃描完畢后，將操作符棧依次彈出并壓入后綴表達(dá)式棧
逆序輸出后綴表達(dá)式棧

根據(jù)后綴表達(dá)式求值：

設(shè)置一個(gè)操作數(shù)棧
從左到右掃描后綴表達(dá)式，遇到操作數(shù)入棧
遇到算符便從棧中彈出兩個(gè)操作數(shù)計(jì)算，結(jié)果入棧
直到算符處理完畢，最后入棧的操作數(shù)便是表達(dá)式的值

復(fù)雜度：

時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)。

實(shí)現(xiàn)：

public class StackReview {
    public static void main(String[] args) {
        String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
        StackReview stackReview = new StackReview();
        StringBuilder suffixExpression = stackReview.InfixToSuffix(arithmeticExpression);
        System.out.println(arithmeticExpression + " = " + stackReview.calculateWithSuffixExpression(suffixExpression));
    }

    public double calculateWithSuffixExpression(StringBuilder suffixExpression) {
        ArrayBasedStack<Double> operands = new ArrayBasedStack<>(8);
        for (int i = suffixExpression.length() - 1; i >= 0; i--) {
            char c = suffixExpression.charAt(i);
            switch (c) {
                case '+':
                case '-':
                case '*':
                case '/':
                    operands.push(this.calSubExpress(operands.pop(), operands.pop(), c));
                    break;
                default:
                    operands.push((double) c - '0');
            }
        }
        return operands.pop();
    }

    public StringBuilder InfixToSuffix(String arithmeticExpression) {
        ArrayBasedStack<Character> operators = new ArrayBasedStack<>(8);
        ArrayBasedStack<Character> suffixExpression = new ArrayBasedStack<>(8);
        for (int i = 0; i < arithmeticExpression.length(); i++) {
            char c = arithmeticExpression.charAt(i);
            switch (arithmeticExpression.charAt(i)) {
                case '(':
                    operators.push(c);
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                    while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
                        suffixExpression.push(operators.pop());
                    }
                    operators.push(c);
                    break;
                case ')':
                    while (operators.size > 0 && operators.getTop() != '(') {
                        suffixExpression.push(operators.pop());
                    }
                    operators.pop();
                    break;
                default:
                    suffixExpression.push(c);
            }
        }
        while (operators.size > 0) {
            suffixExpression.push(operators.pop());
        }
        StringBuilder expression = new StringBuilder();
        while (suffixExpression.size > 0) {
            expression.append(suffixExpression.pop());
        }
        return expression;
    }

    public boolean isGreater(char operator1, char operator2) {
        if (operator1 == '/' || operator2 == '(') {
            // 自左向右，/ 比 * 優(yōu)先級(jí)高。括號(hào)里面必須先算
            return true;
        } else if (operator1 == '-' && operator2 == '+') {
            // 自左向右，- 比 + 優(yōu)先級(jí)高
            return true;
        } else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
            return true;
        }
        return false;
    }

    public double calSubExpress(double operand1, double operand2, char operator) {
        double result = 0;
        switch (operator) {
            case '+':
                // 第二個(gè)數(shù)在前，因?yàn)樗热霔?                result = operand2 + operand1;
                break;
            case '-':
                result = operand2 - operand1;
                break;
            case '*':
                result = operand2 * operand1;
                break;
            case '/':
                result = operand2 / operand1;
                break;
        }
        return result;
    }
}

JVM 中的棧

JVM 的內(nèi)存結(jié)構(gòu)大概分為：

堆（Heap）：線程共享。所有的對(duì)象實(shí)例以及數(shù)組都要在堆上分配。回收器主要管理的對(duì)象
方法區(qū)（Method Area）：線程共享。存儲(chǔ)類信息、常量、靜態(tài)變量、即時(shí)編譯器編譯后的代碼
方法棧（JVM Stack）：線程私有。存儲(chǔ)局部變量表、操作棧、動(dòng)態(tài)鏈接、方法出口，對(duì)象指針
本地方法棧（Native Method Stack）：線程私有。為虛擬機(jī)使用到的 Native 方法服務(wù)。如 Java 使用 c 或者 c++ 編寫的接口服務(wù)時(shí)，代碼在此區(qū)運(yùn)行
程序計(jì)數(shù)器（Program Counter Register）：線程私有。有些文章也翻譯成 PC 寄存器（PC Register），同一個(gè)東西。它可以看作是當(dāng)前線程所執(zhí)行的字節(jié)碼的行號(hào)指示器。指向下一條要執(zhí)行的指令

參考文獻(xiàn)

算術(shù)表達(dá)式求值：“算符優(yōu)先級(jí)法”、“后綴表達(dá)式法”
數(shù)據(jù)結(jié)構(gòu)和算法（六）：前綴、中綴、后綴表達(dá)式
JVM 內(nèi)存結(jié)構(gòu)和 Java 內(nèi)存模型

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

棧及其基本應(yīng)用

棧及其基本應(yīng)用

現(xiàn)實(shí)生活中的棧

順序棧的實(shí)現(xiàn)

鏈?zhǔn)綏５膶?shí)現(xiàn)

出入棧的時(shí)空復(fù)雜度分析

棧的常規(guī)應(yīng)用

處理函數(shù)調(diào)用

瀏覽器的前進(jìn)后退

括號(hào)匹配

算術(shù)表達(dá)式求值

算符優(yōu)先法

后綴表達(dá)式法

JVM 中的棧

參考文獻(xiàn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

棧及其基本應(yīng)用

現(xiàn)實(shí)生活中的棧

順序棧的實(shí)現(xiàn)

鏈?zhǔn)綏５膶?shí)現(xiàn)

出入棧的時(shí)空復(fù)雜度分析

棧的常規(guī)應(yīng)用

處理函數(shù)調(diào)用

瀏覽器的前進(jìn)后退

括號(hào)匹配

算術(shù)表達(dá)式求值

算符優(yōu)先法

后綴表達(dá)式法

JVM 中的棧

參考文獻(xiàn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av