第4章 棧與隊列
4.2 棧的定義
棧(stack) 是限定僅在表層進(jìn)行插入和刪除操作的線性表
允許插入和刪除的一端稱為棧頂(top)
另一端稱為棧底(bottom)
后進(jìn)先出(Last In First Out) 線性表, 簡稱 LIFO

棧的插入操作: 進(jìn)棧, 壓棧, 入棧
棧的刪除操作: 出棧, 彈棧

棧本身是一個線性表, 之前討論的有關(guān)線性表的順序存儲和鏈?zhǔn)酱鎯τ跅Ｍ瑯舆m用

4.4 棧的順序存儲結(jié)構(gòu)及實現(xiàn)

4.5 兩棧共享空間

4.6 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)

4.6.2 棧的鏈?zhǔn)浇Y(jié)構(gòu)-----進(jìn)棧操作
棧是由棧元素構(gòu)成的線性鏈表, 其中有一個棧元素為棧頂元素.
不存在棧溢出情況. 除非整個內(nèi)存都用完了
空棧: 當(dāng) top = NULL 時候
棧元素:

        typedef struct StackNode
        {
            sElemType data;// 元素內(nèi)容
            struct StackNode *next; //指向下一個元素地址
        } StackNode, *LinkStackPtr;

棧頂元素

        typedef struct LinkStack
        {
            LinkStackPtr top;// 指向棧頂元素位置
            int count;// 棧元素的數(shù)量
        }LinkStack;

進(jìn)棧操作 (棧為鏈?zhǔn)酱鎯Y(jié)構(gòu)時, 不用考慮棧溢出)

過程:

• 創(chuàng)建新的棧元素 s , s 的數(shù)據(jù)data 裝我們的新數(shù)據(jù), s 的 next 指針 指向棧頂top元素

• 把棧頂元素top指向這個新的棧元素 s, 讓s 稱為新的棧頂, 棧頂元素的cout屬性加一

代碼如下:

        // 先配置 新的棧元素
        // 再配置 棧頂元素
        Status push(LinkStack *S, sElemType e)
        {
            // 大寫 S 是整個棧, e 是單純的數(shù)據(jù)
            // 小寫 s 是棧元素 
            LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
            // 棧元素的數(shù)據(jù) 為 e
            s->data = e;
            // 棧元素的 next 指向之前的棧頂元素.
            s->>next = S->top;
            // 棧頂元素現(xiàn)在是 s
            S->top = s;
            // 棧元素數(shù)量加1
            S->count++;
            return OK;
        }
        

4.6.3 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)-----出棧結(jié)構(gòu)

當(dāng)棧頂 top = NULL 時 為空棧, 不能執(zhí)行出棧操作(Pop)

過程:

• 拿到棧頂數(shù)據(jù)

• 取出棧頂元素

• 棧頂元素更新為下一個棧元素

• 釋放取出的棧頂元素

代碼如下:

        Status Pop(LinkStack *S, sElemType *e)
        {
            // 傳入?yún)?shù) S: 整個棧
            // 傳入?yún)?shù) *e : 用來存棧頂數(shù)據(jù)的存儲位置
            //p : 棧頂元素 
            LinkStackPtr p;
            // 先判斷是否是空棧
            if(StackEmpty( *s )){
            return ERROR;
            }
            // *e 獲取棧頂?shù)臄?shù)據(jù)
            *e = S->top-data;
            // 給 p 賦值為 棧頂元素
            p = S->top;
            // 棧頂元素指向下一個元素(出棧)
            S->top = S->top->next;
            // 釋放被出棧的棧頂元素p
            free(p);
            // 跟新棧元素數(shù)量
            S->count--;
            // 出棧操作結(jié)束
            return OK;
        }
        

總結(jié): 如果棧的使用過程中元素變化不可預(yù)料, 有時很小, 有時非常大, 那么最好用鏈棧,

反之, 如果它的變化在可控范圍內(nèi), 建議使用順序棧會更好一些

4.8 棧的應(yīng)用----遞歸

4.8.1 斐波那契數(shù)列實現(xiàn)

    F(n) = 0, 當(dāng)n=0
    F(n) = 1, 當(dāng)n=1
    F(n) = F(n-1) + F(n-2), 當(dāng)n>1

打印前40位的斐波那契數(shù)列

簡單的實現(xiàn):

    int main()
    {
        // 從斐波那契數(shù)列這個名字上, 我們就可以看到, 可以用數(shù)組來實現(xiàn).
        // 根據(jù)公式的規(guī)律把數(shù)列和數(shù)組的每個元素對應(yīng)存起來.
        // 直接給 a[0] 設(shè)值 為 0
        // 直接給 a[1] 設(shè)值 為 1
        // a[i] = a[i-1] + a[i-2] 和公式 F(n) = F(n-1) + F(n-2) 對應(yīng)起來.
        int i;
        int a[40];
        a[0] = 0;
        a[1] = 1;
        printf("%d", a[0]);
        printf("%d", a[1]);
        for(i = 2; i< 40; i++){
            a[i] = a[i-1] + a[i-2];
            printf("%d", a[i])
        }
        return 0;
    }

遞歸實現(xiàn)方法:

    /* 上一個實現(xiàn)方法的思路是 從頭到尾 的推斷方式
        先考慮 i=0 再考慮 i=1 一直到 i = 40
    */

    /* 這里的遞歸采用的是 從尾到頭 的推斷方式
       先是 i = 40, i = 39, i = 38, 一直到 i = 1, i = 0  
    */
    // 斐波那契的遞歸函數(shù)
    int Fbi( int i )
    {
        if (i<2)
        {
            // i=0 時 Fbi(0) = 0
            // i=1 時 Fbi(1) = 1
            return i==0 ? 0 : 1; 
        }
        // i >= 2時: Fib(i) = Fib(i-1) + Fib(i-2)
        return Fbi(i - 1) + Fbi(i - 2);// 這里Fbi 就是函數(shù)自己, 它在調(diào)用自己
    }

    int main ()
    {
        int i;
        for (int i = 0; i < 40; i++){
            // 輸出 每一個斐波那契數(shù)列元素
            printf("%d", Fbi(i));
        }
        return 0;
    }

4.8.2 遞歸定義
我們把一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù), 稱作遞歸函數(shù)
每個遞歸定義, 必須至少有一個條件, 滿足時遞歸不再進(jìn)行, 即不再引用自身而是返回值退出

• 遞歸和迭代:

  • 迭代: 使用循環(huán)結(jié)構(gòu), 不需要反復(fù)調(diào)用函數(shù)和占用額外的內(nèi)存,
  • 遞歸: 使用選擇結(jié)構(gòu), 使程序的結(jié)構(gòu)更清晰, 更簡潔, 更容易讓人理解, 從而減少讀懂代碼的時間. 但是大量的遞歸調(diào)用會建立函數(shù)的副本, 會耗費(fèi)大量的時間和內(nèi)存.

  遞歸是用棧這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的. 簡單的說, 在執(zhí)行過程中, 對于每一層遞歸, 函數(shù)的局部變量, 參數(shù)以及返回地址都被壓入棧中, 在退回階段, 位于棧頂?shù)木植孔兞? 參數(shù)值和返回地址被彈出, 用于返回調(diào)用層次中執(zhí)行代碼的其余部分, 也就是恢復(fù)了調(diào)用的狀態(tài).

4.9 棧的應(yīng)用 -- 四則運(yùn)算表達(dá)式求值

4.9.1 后綴 (逆波蘭)表示法定義

4.9.2 后綴表達(dá)式計算結(jié)構(gòu)

4.9.3 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

4.10 隊列的定義
定義: 隊列(queue) 是只允許在一端進(jìn)行插入操作. 而在另一端進(jìn)行刪除操作的線性表.

隊列是一種先進(jìn)先出(First In First Out)線性表, 簡稱FIFO. 允許插入的一端稱為隊尾, 允許刪除的一端稱為隊頭. 假設(shè)隊列是 q = (a1, a2, ......, an) , 那么 a1 就是隊頭元素, 而 an 是隊尾元素, 這樣我們就可以刪除時, 總是從 a1 開始, 插入時, 列在最后.

           隊頭                 隊尾
出隊列 <--- a1, a2, a3, ...... an <---入隊列

4.12 循環(huán)隊列

• 順序隊列的不足: 造成假溢出

• 循環(huán)隊列: 后面滿了, 就再從頭開始, 也就是頭尾相接的循環(huán). 我們把隊列的這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列

c 語言中 區(qū)域運(yùn)算符%

比如 5%4 = 1
4%5 = 4

循環(huán)隊列的順序存儲結(jié)構(gòu)代碼

        //隊列結(jié)構(gòu)體
        typedef int QElemType; // QElemType 為 int 類型(類型按照實際情況來定, 這里假設(shè)為 int)
        typedef struct
        {
            QElemType data[MAXSIZE];// int 類型數(shù)組
            int front;              // 頭指針
            int rear;               // 尾指針
        }sqQueue
        

循環(huán)隊列的初始化代碼

        Status InitQueue(sqQueue *Q)
        {
            Q->front=0;
            Q->rear=0;
            return OK;
        }

循環(huán)隊列求隊列長度代碼如下:

當(dāng) rear > front 時, 隊列長度為: QueueLength = rear - front
當(dāng) rear < front 時, 隊列長度為: QueueLength = (QueueSize - front) + (0 + rear)
把上面兩個條件結(jié)合在一起得到公式: QueueLength = (rear - front + QueueSize) % QueueSize

        int QueueLength(sqQueue Q)
        {
            return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
        }

循環(huán)隊列的入隊列操作代碼如下:

        Status EnQueue(SqQueue *Q, QElemType d)
        {
            // 判斷是否隊列已經(jīng)滿了
            if((Q->rear + 1) % MAXSIZE == Q->front)
            {
                return ERROR;
            }
            // 隊列中插入值
            Q->data[Q->rear] = e;
            // 后移隊尾指針
            Q->rear = (Q->rear+1)%MAXSIZE;
            return OK;
        }

循環(huán)隊列的出隊列操作代碼如下:

        Status DeQueue(sqQueue *Q, QElemType *e)
        {
            // 判斷隊列是否為空
            if(Q->front == Q->rear)
            {
                return ERROR;
            }
            // 取出隊首數(shù)據(jù)
            *e = Q->data[Q->front];
            // 隊首 指針后移
            Q->front = (Q->front+!)%MAXSIZE;
            return OK;
        }
        

4.13 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu), 其實就是線性表的單鏈表, 只不過它只能尾進(jìn)頭出而已, 我們把它簡稱為鏈隊列
空隊列時, front 和 rear 都指向頭結(jié)點

鏈隊列的結(jié)構(gòu):
- 頭指針指向鏈隊列的頭結(jié)點.
- 隊尾指針指向終點結(jié)點

    typedef int QElemType; // QElemType 是int 類型, (可以根據(jù)實際情況自己設(shè)定類型)

    typedef struct QNode  // 結(jié)點結(jié)構(gòu) 
    {
        QElemType data;   // 結(jié)點數(shù)據(jù)
        struct QNode *next;//存放下一個結(jié)點的指針
    }

    typedef struct
    {
        QueuePtr front, rear; // 隊頭, 隊尾 指針

    } LinkQueue;
    

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)-----入隊操作

    Status EnQueue(LinkQueue *Q, QElemType e)
    {
        // 給新的隊列元素分配內(nèi)存
        QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
        if(!s)
        {
            exit(OVERFLOW); // 退出程序, 并返回 OVERFLOW 的值給主程序.(當(dāng)運(yùn)算溢出時)
        }
        s->data = e;        // 新的隊列元素賦值
        s->next = Null;     // 新的隊列元素的下一個元素為 Null
        Q->rear->next = s;  // 隊尾指針的下一個元素 為 s

        Q->rear = s;        // 隊尾指針指向 s
        return OK;
    }

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)---出隊操作

    // 若隊列不空, 刪除Q的隊頭元素, 用e返回其值, 并返回OK, 否則返回ERROR
    Status DeQueue(LinkQueue *Q, QElemType *e)
    {
        QueuePtr p;
        // 判斷隊列是否為空
        if(Q->front == Q->rear)
        {
            return ERROR;
        }
        // p 為隊首
        p = Q->front->next;
        // 取出隊首的值
        *e = p->data;
        // 隊頭指針后移
        Q->front->next = p->next
        // 如果隊列被清空
        if(Q->rear == p)
        {
            Q->rear = Q -> front;
        }
        // 釋放p
        free(p);
        return OK
    }
    

• 循環(huán)隊列和鏈隊列比較:
  • 時間上: 沒有什么大的區(qū)別
  • 空間上: 循環(huán)隊列必須有一個固定的長度, 就有了存儲元素個數(shù)和空間浪費(fèi)的問題.空間上,鏈隊列會更加靈活.

  可以確定隊列長度最大值時,使用循環(huán)隊列
  不能預(yù)估隊列長度時, 使用鏈隊列