棧（Stack），輕松解決數制轉換和括號匹配問題！

http://data.biancheng.net/view/9.html

棧，線性表的一種特殊的存儲結構。與學習過的線性表的不同之處在于棧只能從表的固定一端對數據進行插入和刪除操作，另一端是封死的。

圖1 棧結構示意圖

由于棧只有一邊開口存取數據，稱開口的那一端為“棧頂”，封死的那一端為“棧底”（類似于盛水的木桶，從哪進去的最后還得從哪出來）。

棧的“先進后出”原則

使用棧存儲數據元素，對數據元素的 “存” 和 “取” 有嚴格的規定：數據按一定的順序存儲到棧中，當需要調取棧中某數據元素時，需要將在該數據元素之后進棧的先出棧，該數據元素才能從棧中提取出來。

如圖 1 ，棧中存放了 4 個數據元素，進棧的順序是 A 先進棧，然后 B 進，然后 C 進，最后 D 進棧；當需要調取 A 時，首先 D 出棧，然后 C 出棧，然后 B 出棧，最后 A 才能出棧被調用。

就好比只有一個門的車庫（每次僅允許一輛車通過），每輛車好比一個數據元素，只有離門最近的車先開出來，里邊的車才能出來；最里邊的車是最先開進去的，注定要最后出來。

棧操作數據元素的方法

棧操作數據元素只有兩種動作：

數據元素用棧的數據結構存儲起來，稱為“入棧”，也叫“壓棧”。
數據元素由于某種原因需要從棧結構中提取出來，稱為“出棧”，也叫“彈棧”。

棧的兩種表示方式

既然棧也是線性表，那么它就同樣有線性表的兩種表示形式：順序棧 ?和? 鏈式棧（簡稱 “鏈棧” ）。

兩者的區別在于存儲的數據元素在物理結構上是否是相互緊挨著的。順序棧存儲元素預先申請連續的存儲單元；鏈棧需要即申請，數據元素不緊挨著。

棧的“上溢”和“下溢”

棧存儲結構調取棧中數據元素時，要避免出現“上溢”和“下溢”的情況：

“上溢”：在棧已經存滿數據元素的情況下，如果繼續向棧內存入數據，棧存儲就會出錯。

“下溢”：在棧內為空的狀態下，如果對棧繼續進行取數據的操作，就會出錯。

棧的“上溢”和“下溢”，可以總結為：棧滿還存會“上溢”，棧空再取會“下溢”。

對于棧的兩種表示方式來說，順序棧兩種情況都有可能發生；而鏈棧由于“隨時需要，隨時申請空間”的存儲結構，不會出現“上溢”的情況。

順序棧

順序棧的實現采用的是數組。

在順序棧中設定一個隨時指向棧頂元素的變量（一般命名為 top ），當 top 的值為 -1 時，說明數組中沒有數據，即棧中沒有數據元素，為 “空棧” ；只要數據元素進棧，top 就加 1 ；數據元素出棧， top 就減 1 。

例如，使用順序棧的存儲結構將（’a’,’b’,’c’,’d’）四個元素逐個壓棧并輸出棧頂元素。

實現代碼：

#include <stdio.h>
//元素elem進棧
int push(char* a,int top,char elem){
    a[++top]=elem;
    return top;
}
//數據元素出棧
int pop(char * a,int top){
    if (top==-1) {
        printf("空棧");
        return -1;
    }
    printf("彈棧元素：%c\n",a[top]);
    top--;
    return top;
}
int main() {
    char a[100];
    int top=-1;
    top=push(a, top, 'a');
    top=push(a, top, 'b');
    top=push(a, top, 'c');
    top=push(a, top, 'd');
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}

輸出結果：

彈棧元素：d
彈棧元素：c
彈棧元素：b
彈棧元素：a
空棧

鏈棧

鏈棧，用線性表的鏈式存儲結構實現。

鏈棧一般不需要創建頭結點，頭結點會增加程序的復雜性，只需要創建一個頭指針就可以了。

用鏈表表示棧時，用鏈表頭結點的一端作為棧的棧頂端，這樣做的好處是當數據元素壓棧或者彈棧時，直接使用頭指針就可以完成，不需要增設額外的指針。

例如，用鏈棧實現將（’a’,’b’,’c’,’d’）四個數據元素壓棧，再依次彈棧：

#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
    char data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,char a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("彈棧元素：%c ",p->data);
        if (stack) {
            printf("棧頂元素：%c\n",stack->data);
        }else{
            printf("棧已空\n");
        }
        free(p);
    }else{
        printf("棧內沒有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 'a');
    stack=push(stack, 'b');
    stack=push(stack, 'c');
    stack=push(stack, 'd');
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

輸出結果：

彈棧元素：d 棧頂元素：c
彈棧元素：c 棧頂元素：b
彈棧元素：b 棧頂元素：a
彈棧元素：a 棧已空
棧內沒有元素

棧的實際應用

實際生活中，使用手機（無論是 iPhone 還是安卓）時，屏幕頁面的跳轉使用的就是棧。當你選擇換一個頁面瀏覽時，之前的頁面被存儲到棧中；每次做回退操作時，會回到上一個頁面，這是進棧的頁面逐個出棧的效果。

另外，在求 n！時，有一種算法會涉及到函數的遞歸（函數自己調用自己的過程），這個過程的底層實現就用到了棧。

除此之外，數制轉換和括號匹配問題，也可以用棧來解決。

數制轉換

實際生活中主要使用 10 進制，而計算機只認識 2 進制，在解決數制轉換的問題上使用棧結構會事半功倍。

例如，將十進制轉化成二進制，代碼實現：

#include <stdio.h>
int top=-1;//top變量時刻表示棧頂元素所在位置
void push(int * a,int elem){
    a[++top]=elem;
}
void pop(int * a){
    if (top==-1) {
        return ;
    }
    printf("%d",a[top]);
    top--;
}
int main() {
    int a[30];
    int div = 0;
    scanf("%d",&div);
  
    while (div/2) {
        push(a,div%2);
        div/=2;
    }
    push(a,div%2);
    while (top!=-1) {
        pop(a);
    }
}

運行結果：
15
1111

2 進制和 10 進制之間的轉換方法為：15 = 1*2^0?+ 1*2¹?+ 1*2²?+ 1*2³

括號匹配的檢查

在編寫代碼的時候，經常會用到兩種括號：圓括號 “()” 和大括號 “{}” 。不管使用哪種括號，程序編譯沒有問題的一個考慮因素就是所使用的括號是否能夠匹配上，在編寫程序時，括號可以嵌套，即： “({()})” 這種形式，但 “({)” 或者 “({}” 都不符合要求。

編寫程序判斷括號匹配問題的時候，使用棧結構會很容易：

如果碰到的是左圓括號或者左大括號，直接壓棧；
如果碰到的是右圓括號或者右大括號，就直接和棧頂元素配對：如果匹配，棧頂元素彈棧；反之，括號不匹配；

實現代碼：

#include <stdio.h>
#include <string.h>
int top=-1;//top變量時刻表示棧頂元素所在位置
void push(char * a,int elem){
    a[++top]=elem;
}
void pop(char* a){
    if (top==-1) {
        return ;
    }
    top--;
}
char visit(char * a){
    //調取棧頂元素，不等于彈棧，如果棧為空，為使程序不發生錯誤，返回空字符
    if (top!=-1) {
        return a[top];
    }else{
        return ' ';
    }
}
int main() {
    char a[30];
    char bracket[100];
    scanf("%s",bracket);
    int length=(int)strlen(bracket);
    for (int i=0; i<length; i++) {
        //如果是左括號，直接壓棧
        if (bracket[i]=='('||bracket[i]=='{') {
            push(a, bracket[i]);
        }else{
            //判斷與棧頂元素是否匹配，如果匹配，棧頂元素彈棧，程序繼續運行；否則，發現括號不匹配，輸出結果直接退出
            if (bracket[i]==')') {
                if (visit(a)=='(') {
                    pop(a);
                }else{
                    printf("括號不匹配");
                    return 0;
                }
            }else{
                if (visit(a)=='{') {
                    pop(a);
                }else{
                    printf("括號不匹配");
                    return 0;
                }
            }
        }
    }
    //如果所有括號匹配完成，棧內為空，說明所有括號全部匹配成功
    if (top!=-1) {
         printf("括號不匹配");
    }else{
       printf("括號匹配");
    }
}