[數據結構] 03 - 棧和隊列詳情 - 數據結構,棧,隊列 GVenusLeo 動態日志

動態

詳情

[數據結構] 03 - 棧和隊列 - 動態詳情

06:20 下午 · 11月 06 ,2025

從數據結構角度看，棧和隊列也是線性表，其特殊性在於棧和隊列的基本操作是線性表操作的子集，它們是操作受限的線性表，因此，可稱為限定性的數據結構。但從數據類型角度看，它們是和線性表大不相同的兩類重要的抽象數據類型。由於它們廣泛應用在各種軟件系統中，因此在面向對象的程序設計中，它們是多型數據類型。

1 棧

1.1 抽象數據類型棧的定義

棧（stack）是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來説，表尾端有其特殊含義，稱為棧頂（top），相應地，表頭端稱為棧底（bottom）。不含元素的空表稱為空棧。

假設棧 \(S=(a_1,a_2,\cdots,a_n)\)，則稱 \(a_1\) 為棧底元素，\(a_n\) 為棧頂元素。棧中元素按 \(a_1,a_2,\cdots,a_n\) 的次序進棧，退棧的第一個元素應為棧頂元素。即棧的修改是按後進先出的原則進行的，因此，棧又稱為後進先出（last in first out）的線性表（簡稱 LIFO 結構）。

棧的抽象數據類型定義如下：

ADT Stack {
    數據對象：D = {ai | ai ∈ ElemSet, i = 1, 2, ..., n}
    數據對象: R1 = {<a_{i-1}, ai> | a_{i-1}, ai ∈ D, i = 2, 3, ..., n}
        約定 an 端為棧頂，a1 端為棧底
    基本操作:
        InitStack(&S)
            操作結果: 構造一個空棧 S
        DestroyStack(&S)
            初始條件: 棧 S 存在
            操作結果: 銷燬棧 S 
        StackEmpty(S)
            初始條件: 棧 S 存在
            操作結果: 若棧 S 為空棧，則返回 TRUE，否則返回 FALSE
        StackLenght(S)
            初始條件: 棧 S 存在
            操作結果: 返回棧 S 的元素個數
        GetTop(S, &e)
            初始條件: 棧 S 存在且非空
            操作結果: 用 e 返回棧 S 的棧頂元素
        Push(&S, e)
            初始條件: 棧 S 存在
            操作結果: 插入新元素 e 為棧 S 的新的棧頂元素
        Pop(&S, &e)
            初始條件: 棧 S 存在且非空
            操作結果: 刪除棧 S 的棧頂元素，並用 e 返回其值
        StackTraverse(S, visit())
            初始條件: 棧 S 存在
            操作結果: 從棧底到棧頂依次對棧 S 中每個元素調用函數 visit()。一旦 visit() 失敗，則操作失敗
} ADT Stack

1.2 棧的表示與實現

和線性表類似，棧也有兩種存儲表示方式。

順序棧，即棧的順序存儲結構是利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針 top 指示棧頂元素在順序棧中的位置。通常的習慣做法是以 top=0 表示空棧；另一方面，由於棧在使用過程中所需最大空間的大小很難估計，因此，一般來説，在初始化設空棧時不應限定棧的最大容量。一個較合理的做法是：先為棧分配一個基本容量，然後在應用過程中，當棧的空間不夠使用時再逐段擴大。為此，可設定兩個常量：STACK_INIT_SIZE（存儲空間初始分配量）和 STACKINCREMENT（存儲空間分配增量），並以下述類型説明作為順序棧的定義。

typedef struct {
    SElemType * base;
    SElemType * top;
    int stacksize;
} SqStack;

其中，stacksize 指示棧的當前可用最大容量。

棧的初始化操作為：按設定的初始分配量進行第一次存儲分配，base 可稱為棧底指針，在順序棧中，它始終指向棧底的位置，若 base 的值為 NULL，則表明棧結構不存在。稱 top 為棧頂指針，其初值指向棧底，即 top=base 可作為棧空的標記，每當插入新的棧頂元素時，指針 top 增 1；刪除棧頂元素時，指針 top 減 1，因此，非空棧中的棧頂指針始終在棧頂元素的下一個位置上。

// 棧基本操作的部分算法描述
Status InitStack(SqStack &S) {
    // 構造一個空棧
    S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)exit(OVERFLOW);  // 存儲分配失敗
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
} // InitStack
Status GetTop(SqStack S, SElemType &e) {
  // 若棧不空，則用 e 返回 S 的頂棧元素，並返回 OK；否則返回 ERROR
  if(S.top == S.base) return ERROR;
  e = *(S.top - 1);
  return OK;
} // GetTop
Status Push(SqStack &S, SElemType e) {
    // 插入元素 e 為新的棧頂元素
    if(S.top - S.base >= S.stacksize) {
        // 棧滿，追加存儲空間
        S.base = (SElemType * )realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base) exit(OVERFLOW);  // 存儲分配失敗
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
} // Push
Status Pop(SqStack &S, SElemType &e) {
    // 若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，並返回 OK；否則返回 ERROR
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
} // Pop

2 隊列

2.1 抽象數據類型隊列的定義

和棧相反，隊列（queue）是一種先進先出（first in first out，縮寫為 FIFO）的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。

在隊列中，允許插入的一端叫隊尾（rear），允許刪除的一端叫隊頭（front）。在隊列 \(q=(a_1,a_2,\cdots,a_n)\) 中，\(a_1\) 時隊頭元素，\(a_n\) 時隊尾元素，隊列中元素按照 \(a_1,a_2,\cdots,a_n\) 的順序進入，推出隊列也只能按照這個順序依次退出。

隊列的抽象數據類型定義如下：

ADT Queue {
    數據對象: D = {ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0}
    數據關係: R1 = {<a_{i-1}, ai> | a_{i-1}, ai ∈ D, i = 2,..., n}
        約定其中 a1 為隊頭元素，an 為隊尾元素
    基本操作:
        InitQueue(&Q)
            操作結果: 構造一個空隊列 Q
        DestroyQueue(&Q)
            初始條件: 隊列 Q 已存在
            操作結果: 銷燬隊列 Q
        ClearQueue(&Q)
            初始條件: 隊列 Q 已存在
            操作結果: 將 Q 清為空隊列
        QueueEmpty(Q)
            初始條件: 隊列 Q 已存在
            操作結果: 若 Q 為空隊列，則返回 TRUE，否則返回 FALSE
        GueueLength(Q)
            初始條件: 隊列 Q 已存在
            操作結果: 返回 Q 的元素個數，即隊列的長度
        GetHead(Q, &e)
            初始條件: 隊列 Q 已存在
            操作結果: 若隊列不空，則用 e 返回 Q 的隊頭元素，並返回 OK；否則返回 ERROR
        EnQueue(&Q, e)
            初始條件: 隊列 Q 已存在
            操作結果: 插入新元素 e 為 Q 的新的隊尾元素
        DeQueue(&Q, &e)
            初始條件: 隊列 Q 已存在
            操作結果: 若隊列不空，則刪除 Q 的隊頭元素，用 e 返回其值，並返回 OK；否則返回 ERROR
        QueueTraverse(Q, visit())
            初始條件: 隊列 Q 已存在
            操作結果: 從隊頭到隊尾依次對 Q 的每個元素調用函數 visit()。一旦 visit() 失敗，則操作失敗
} ADT Queue

除了棧和隊列外，還有一種限定性數據結構是雙端隊列（deque）。雙端隊列是限定插人和刪除操作在表的兩端進行的線性表。這兩端分別稱做端點 1 和端點 2。在實際使用中，還可以有輸出受限的雙端隊列（即一個端點允許插人和刪除，另一個端點只允許插人的雙端隊列）和輸入受限的雙端隊列（即一個端點允許插人和刪除，另一個端點只允許刪除的雙端隊列）。而如果限定雙端隊列從某個端點插人的元素只能從該端點刪除，則該雙端隊列就蜕變為兩個棧底相鄰接的棧了。儘管雙端隊列看起來似乎比棧和隊列更靈活，但實際上在應用程序中遠不及棧和隊列有用。

2.2 鏈隊列

和線性表類似，隊列也可以有兩種存儲表示。

用鏈表表示的隊列簡稱為鏈隊列。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為頭指針和尾指針）才能惟一確定。這裏，和線性表的單鏈表一樣，為了操作方便起見，給鏈隊列添加一個頭結點，並令頭指針指向頭結點。由此，空的鏈隊列的判決條件為頭指針和尾指針均指向頭結點。

鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況，只需修改尾指針或頭指針。

// 單鏈隊列的存儲結構
typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr front; // 隊頭指針
    QUeuePtr rear;  // 隊尾指針
} LinkQueue;

// 基本操作的部分算法描述
Status InitQueue(LinkQueue &Q) {
    // 構造一個空隊列
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front) exit(OVERFLOW);  // 存儲分配失敗
    Q.front->next = NULL;
    return OK;
}
Status DestroyQueue(LinkQueue &Q) {
    // 銷燬隊列 Q
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}
Status EnQueue(LinkQueue &Q, QElemType e) {
    // 插入元素 e 為 Q 的新的隊尾元素
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) exit(OVERFLOW); // 存儲分配失敗
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}
Status DeQueue(LinkQueue &Q, QElemType &e) {
    // 若隊列不空，則刪除 Q 的隊頭元素，用 e 返回其值，並返回 OK；否則返回 ERROR
    if (Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    free(p);
    return OK;
}

注意：在上述模塊的算法描述中，應注意刪除隊列頭元素算法中的特殊情況。一般情況下，刪除隊列頭元素時僅需修改頭結點中的指針，但當隊列中最後一個元素被刪後，隊列尾指針也丟失了，因此需對隊尾指針重新賦值（指向頭結點）。

2.3 循環隊列

循環隊列是一種特殊的隊列，它的隊頭和隊尾指針可以在隊列的存儲空間上形成一個環，從而使得隊列的存儲空間可以重複利用。指針和隊列元素之間的關係不變。

循環隊列的判空和判滿條件為：

隊空條件：front == rear
隊滿條件：(rear + 1) % MAXSIZE == front

其中，MAXSIZE 為循環隊列的最大容量。

循環隊列的入隊和出隊操作如下：

Status EnQueue(CirQueue &Q, QElemType e) {
    // 插入元素 e 為 Q 的新的隊尾元素
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; // 隊列滿
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}
Status DeQueue(CirQueue &Q, QElemType &e) {
    // 若隊列不空，則刪除 Q 的隊頭元素，用 e 返回其值，並返回 OK；否則返回 ERROR
    if (Q.front == Q.rear) return ERROR; // 隊列空
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

Reference：

嚴蔚敏 / 吳偉民《數據結構（C語言版）》

數據結構 , 隊列 , 棧

GVenusLeo 動態日志

@gvenusleo

標簽

數據結構 (48)

隊列 (24)

棧 (7)

動態

[數據結構] 03 - 棧和隊列 - 動態詳情

1 棧

1.1 抽象數據類型棧的定義

1.2 棧的表示與實現

2 隊列

2.1 抽象數據類型隊列的定義

2.2 鏈隊列

2.3 循環隊列

Add a new 評論

GVenusLeo 動態日志

@gvenusleo

標簽

數據結構 (48)

隊列 (24)

棧 (7)

動態

[數據結構] 03 - 棧和隊列 - 動態 詳情

1 棧

1.1 抽象數據類型棧的定義

1.2 棧的表示與實現

2 隊列

2.1 抽象數據類型隊列的定義

2.2 鏈隊列

2.3 循環隊列

Add a new 評論

[數據結構] 03 - 棧和隊列 - 動態詳情