本文是算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)筆記第四篇，將持續(xù)更新，歡迎小伙伴們閱讀學(xué)習(xí) 。有不懂的或錯(cuò)誤的地方，歡迎交流

棧

棧是一種線性數(shù)據(jù)結(jié)構(gòu)，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂 (Top）, 另一端稱為棧底 (Bottom)。棧中的數(shù)據(jù)元素遵守后進(jìn)先出 LIFO（Last In First Out）的原則，即最后進(jìn)入的元素最先被訪問。

壓棧（push）：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧（pop）：棧的刪除操作叫做出棧，出數(shù)據(jù)也在棧頂。

下面的動(dòng)圖可以更直觀的理解棧的出入棧

棧的特點(diǎn)

1. 后進(jìn)先出（LIFO）：最后進(jìn)入棧的元素最先被訪問，而最先進(jìn)入棧的元素最后被訪問。
2. 只允許在一端進(jìn)行插入和刪除操作：棧通常只允許在棧頂進(jìn)行插入和刪除操作，而不允許在其他位置進(jìn)行操作。
3. 棧頂指針：棧頂指針指向棧頂元素，它隨著元素的插入和刪除而改變。

棧的應(yīng)用

1. 函數(shù)調(diào)用：編程語(yǔ)言中的函數(shù)調(diào)用過程使用棧來(lái)保存函數(shù)的返回地址、參數(shù)和局部變量等信息。每當(dāng)一個(gè)函數(shù)被調(diào)用，其相關(guān)信息被壓入棧中；當(dāng)函數(shù)執(zhí)行完畢，這些信息被彈出棧，控制權(quán)回到調(diào)用函數(shù)。
2. 表達(dá)式求值：棧在表達(dá)式求值中起到重要作用。通過將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并使用棧來(lái)存儲(chǔ)操作數(shù)和運(yùn)算符，可以實(shí)現(xiàn)對(duì)表達(dá)式的求值。
3. 括號(hào)匹配：棧常用于檢查表達(dá)式中括號(hào)是否匹配的問題。遍歷表達(dá)式時(shí)，遇到左括號(hào)就將其壓入棧中，遇到右括號(hào)時(shí)與棧頂元素進(jìn)行匹配，如果匹配則彈出棧頂元素，繼續(xù)遍歷；如果不匹配，則括號(hào)不匹配。
4. 撤銷操作：在文本編輯器或圖形處理軟件中，?？捎糜趯?shí)現(xiàn)撤銷操作。每次執(zhí)行操作時(shí)，相關(guān)信息被壓入棧中，當(dāng)用戶需要撤銷操作時(shí)，將棧頂元素彈出，回退到上一個(gè)狀態(tài)。
5. 中斷處理和現(xiàn)場(chǎng)保護(hù)：中斷是計(jì)算機(jī)系統(tǒng)中常見的事件，例如硬件故障、外部設(shè)備請(qǐng)求等。當(dāng)系統(tǒng)發(fā)生中斷時(shí)，當(dāng)前正在執(zhí)行的程序需要被暫停，轉(zhuǎn)而處理中斷事件。棧在中斷處理中扮演著重要角色，用于保存和恢復(fù)程序的執(zhí)行現(xiàn)場(chǎng)。當(dāng)發(fā)生中斷時(shí)，系統(tǒng)會(huì)自動(dòng)將當(dāng)前程序的執(zhí)行現(xiàn)場(chǎng)（包括程序計(jì)數(shù)器、寄存器等狀態(tài)信息）保存到棧中。然后，中斷服務(wù)程序（Interrupt Service Routine，ISR）被執(zhí)行，處理中斷事件。處理完成后，系統(tǒng)從棧中恢復(fù)之前保存的執(zhí)行現(xiàn)場(chǎng)，繼續(xù)原來(lái)被中斷的程序的執(zhí)行。通過棧的保存和恢復(fù)操作，確保中斷處理的流程正確且不會(huì)破壞原有的程序執(zhí)行。

棧的基本操作

1. 初始化棧。
2. 壓棧，往棧中添加一個(gè)元素。
3. 出棧，從棧頂刪除一個(gè)元素。
4. 獲取棧頂元素。
5. 判斷棧是否為空、是否滿棧。
6. 棧的銷毀。

注意：在操作棧時(shí)，要避免“上溢”和“下溢”
上溢：指棧已滿，若繼續(xù)存數(shù)據(jù)，則會(huì)上溢，出現(xiàn)報(bào)錯(cuò)（棧滿再存出現(xiàn)上溢）
下溢：指棧已空，若繼續(xù)取數(shù)據(jù)，則會(huì)下溢，出現(xiàn)報(bào)錯(cuò)（?？赵偃〕霈F(xiàn)下溢）

C 語(yǔ)言

棧有兩種實(shí)現(xiàn)方式，一種是使用數(shù)組來(lái)實(shí)現(xiàn)，另一種是使用鏈表來(lái)實(shí)現(xiàn)。下面是總結(jié)的用數(shù)組和鏈表實(shí)現(xiàn)的優(yōu)缺點(diǎn)。

用數(shù)組實(shí)現(xiàn)的優(yōu)點(diǎn)
1 . 數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，因此訪問元素時(shí)速度較快。CPU高速緩存命中率會(huì)更高。
2. 下標(biāo)的隨機(jī)訪問。尾插尾刪效率不錯(cuò).
3. 數(shù)組實(shí)現(xiàn)相對(duì)簡(jiǎn)單，不需要額外的指針來(lái)維護(hù)元素之間的關(guān)系。
數(shù)組實(shí)現(xiàn)的缺點(diǎn)
1 . 數(shù)組的大小是固定的，因此在棧空間不足時(shí)需要進(jìn)行擴(kuò)容操作，這可能會(huì)導(dǎo)致性能下降。
2 . 在刪除元素時(shí)，需要移動(dòng)數(shù)組中的其他元素，這也可能會(huì)導(dǎo)致性能下降。

用鏈表實(shí)現(xiàn)的優(yōu)點(diǎn)
1 .鏈表的大小可以動(dòng)態(tài)調(diào)整，因此可以更好地利用空間。
2 . 任意位置插入刪除O(1) ，鏈表的性能較高，因?yàn)椴恍枰苿?dòng)其他元素。
鏈表實(shí)現(xiàn)的缺點(diǎn)
1 . CPU高速緩存命中率會(huì)更低,不是連續(xù)存儲(chǔ)的，因此訪問元素時(shí)速度較慢。
2. 不支持下標(biāo)的隨機(jī)訪問.

用鏈表還是用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)，這個(gè)問題的答案取決于具體的應(yīng)用場(chǎng)景和需求，下面我們給出了數(shù)組棧和鏈表?xiàng)５?C 語(yǔ)言實(shí)現(xiàn)。

數(shù)組棧

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// 定義棧結(jié)構(gòu)
typedef struct {
    int data[MAX_SIZE]; // 用數(shù)組存儲(chǔ)棧的元素
    int top; // 棧頂指針
} Stack;

// 初始化棧
void init(Stack *stack) {
    stack->top = -1; // 初始化棧頂指針為-1，表示棧為空
}

// 判斷棧是否為空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判斷棧是否已滿
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入棧操作
void push(Stack *stack, int item) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->top++; // 棧頂指針加1
    stack->data[stack->top] = item; // 將元素入棧
}

// 出棧操作
int pop(Stack *stack) {
    int item;
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    item = stack->data[stack->top]; // 獲取棧頂元素
    stack->top--; // 棧頂指針減1
    return item;
}

// 獲取棧頂元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->data[stack->top];
}

// 銷毀棧
void destroy(Stack *stack) {
    stack->top = -1; // 將棧頂指針重置為-1，表示棧為空
}

int main() {
    Stack stack;
    init(&stack);

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Top element: %d\n", peek(&stack));

    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));

    printf("Top element: %d\n", peek(&stack));

    destroy(&stack);

    return 0;
}

鏈表?xiàng)?/h4>

#include <stdio.h>
#include <stdlib.h>

// 定義鏈表節(jié)點(diǎn)
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定義棧結(jié)構(gòu)
typedef struct {
    Node* top; // 棧頂指針
} Stack;

// 初始化棧
void init(Stack* stack) {
    stack->top = NULL; // 初始化棧頂指針為空
}

// 判斷棧是否為空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

/* 由于鏈表實(shí)現(xiàn)的棧理論上沒有大小限制，因此不存在“棧滿”的情況。在入棧操作時(shí)只需要?jiǎng)?chuàng)建新節(jié)點(diǎn)，并將其插入到鏈表頭部即可。
如需限制棧的大小，可以通過設(shè)置一個(gè)變量來(lái)記錄當(dāng)前棧中存儲(chǔ)的元素個(gè)數(shù)，然后在入棧時(shí)進(jìn)行判斷，若已滿則不允許再次入棧。*/

// 入棧操作
void push(Stack* stack, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 創(chuàng)建新節(jié)點(diǎn)
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = item; // 設(shè)置新節(jié)點(diǎn)的數(shù)據(jù)為要入棧的元素
    newNode->next = stack->top; // 將新節(jié)點(diǎn)插入到棧頂
    stack->top = newNode; // 更新棧頂指針
}

// 出棧操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    Node* topNode = stack->top; // 獲取棧頂節(jié)點(diǎn)
    int item = topNode->data; // 獲取棧頂元素
    stack->top = topNode->next; // 更新棧頂指針
    free(topNode); // 釋放棧頂節(jié)點(diǎn)的內(nèi)存
    return item;
}

// 獲取棧頂元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->top->data;
}

// 銷毀棧
void destroy(Stack* stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
}

int main() {
    Stack stack;
    init(&stack);

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Top element: %d\n", peek(&stack));

    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));

    printf("Top element: %d\n", peek(&stack));

    destroy(&stack);

    return 0;
}

隊(duì)列

隊(duì)列是棧的兄弟結(jié)構(gòu)，是只允許在一端進(jìn)行插入元素操作，在另一端進(jìn)行刪除元素操作的線性數(shù)據(jù)結(jié)構(gòu)。進(jìn)行插入操作的一端稱為隊(duì)尾，進(jìn)行刪除操作的一端稱為隊(duì)頭。隊(duì)列中的數(shù)據(jù)元素遵守先進(jìn)先出 FIFO（First In First Out）的原則，即最先進(jìn)入的元素最先被訪問。

隊(duì)列的特點(diǎn)

1. 先進(jìn)先出（FIFO）：第一個(gè)插入的元素是第一個(gè)被刪除的元素，因此表現(xiàn)為先進(jìn)先出的順序。
2. 元素只能從隊(duì)尾插入（入隊(duì)）和從隊(duì)頭刪除（出隊(duì)）。

隊(duì)列的應(yīng)用

1. 消息傳遞:在消息傳遞模型中，消息被發(fā)送到隊(duì)列中等待接收方進(jìn)行處理。發(fā)送方可以通過入隊(duì)操作向隊(duì)列發(fā)送消息，而接收方則通過出隊(duì)操作從隊(duì)列中獲取消息。
2. 緩存區(qū)管理：在網(wǎng)絡(luò)通信、磁盤I/O等場(chǎng)景中，隊(duì)列被用于管理數(shù)據(jù)的緩沖區(qū)。接收到的數(shù)據(jù)被放入隊(duì)列中，然后按照一定的規(guī)則從隊(duì)列中取出，保證數(shù)據(jù)按照順序傳輸。
3. 任務(wù)調(diào)度：操作系統(tǒng)中的任務(wù)調(diào)度通常使用隊(duì)列來(lái)管理待執(zhí)行的任務(wù)，按照先來(lái)先服務(wù)（First-Come-First-Served，F(xiàn)CFS）的原則進(jìn)行調(diào)度。
4. 廣度優(yōu)先搜索：圖的廣度優(yōu)先搜索算法（BFS）使用隊(duì)列來(lái)保存待訪問的節(jié)點(diǎn)。從起始節(jié)點(diǎn)開始，將其放入隊(duì)列中，然后不斷從隊(duì)列中取出節(jié)點(diǎn)，并將其鄰接節(jié)點(diǎn)放入隊(duì)列，直到隊(duì)列為空。

隊(duì)列的基本操作

1. 入隊(duì)（enqueue）：將元素插入到隊(duì)列的末尾。
2. 出隊(duì)（dequeue）：從隊(duì)列的頭部刪除一個(gè)元素并返回。
3. 獲取隊(duì)列頭部元素的值。
4. 獲取隊(duì)列中元素的個(gè)數(shù)。
5. 判斷隊(duì)列是否為空、是否已滿。
6. 隊(duì)列的銷毀

C 語(yǔ)言

隊(duì)列有兩種實(shí)現(xiàn)方式，一種是使用數(shù)組來(lái)實(shí)現(xiàn)，另一種是使用鏈表來(lái)實(shí)現(xiàn)。下面是總結(jié)的用數(shù)組和鏈表實(shí)現(xiàn)的優(yōu)缺點(diǎn)。

用數(shù)組實(shí)現(xiàn)的優(yōu)點(diǎn)
1 . 數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，因此訪問元素時(shí)速度較快。CPU高速緩存命中率會(huì)更高。
2 . 數(shù)組實(shí)現(xiàn)相對(duì)簡(jiǎn)單，不需要額外的指針來(lái)維護(hù)元素之間的關(guān)系。
數(shù)組實(shí)現(xiàn)的缺點(diǎn)
1 . 需要事先確定隊(duì)列的最大長(zhǎng)度，這可能會(huì)導(dǎo)致性能下降。
2 . 需要移動(dòng)元素來(lái)保持隊(duì)列的順序。

用鏈表實(shí)現(xiàn)的優(yōu)點(diǎn)
1 . 不需要事先確定隊(duì)列的最大長(zhǎng)度，可以動(dòng)態(tài)擴(kuò)展。
2 . 插入和刪除操作只需要修改指針，不需要移動(dòng)元素。
3 . 可以實(shí)現(xiàn)多個(gè)隊(duì)列共享一個(gè)鏈表。
鏈表實(shí)現(xiàn)的缺點(diǎn)
1 . CPU高速緩存命中率會(huì)更低,不是連續(xù)存儲(chǔ)的，因此訪問元素時(shí)速度較慢。
2 .實(shí)現(xiàn)相對(duì)復(fù)雜。

用鏈表還是用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)，這個(gè)問題的答案取決于具體的應(yīng)用場(chǎng)景和需求，下面我們給出了數(shù)組隊(duì)列和鏈表隊(duì)列的 C 語(yǔ)言實(shí)現(xiàn)。

數(shù)組隊(duì)列

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // 隊(duì)列的最大大小

// 定義隊(duì)列結(jié)構(gòu)體
struct queue {
    int* arr; // 數(shù)組指針
    int front; // 隊(duì)首位置
    int rear; // 隊(duì)尾位置
    int size; // 當(dāng)前隊(duì)列中存儲(chǔ)的元素個(gè)數(shù)
};

// 初始化隊(duì)列
struct queue* init() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->arr = (int*)malloc(MAX_SIZE * sizeof(int));
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    return q;
}

// 判斷隊(duì)列是否為空
int is_empty(struct queue* q) {
    return q->size == 0;
}

// 判斷隊(duì)列是否已滿
int is_full(struct queue* q) {
    return q->size == MAX_SIZE;
}

// 入隊(duì)
void enqueue(struct queue* q, int value) {
    if (is_full(q)) {
        printf("Queue Overflow\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->arr[q->rear] = value;
    q->size++;
}

// 出隊(duì)
int dequeue(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    int value = q->arr[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return value;
}

// 獲取隊(duì)首元素
int front(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    return q->arr[q->front];
}

// 獲取隊(duì)列長(zhǎng)度
int size(struct queue* q) {
    return q->size;
}

// 銷毀隊(duì)列
void destroy(struct queue* q) {
    free(q->arr);
    free(q);
}

int main() {
    struct queue* q = init();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("%d\n", dequeue(q)); // 輸出10
    printf("%d\n", front(q)); // 輸出20
    enqueue(q, 40);
    printf("%d\n", dequeue(q)); // 輸出20
    printf("%d\n", dequeue(q)); // 輸出30
    printf("%d\n", dequeue(q)); // 輸出40
    printf("%d\n", dequeue(q)); // 輸出Queue Underflow
    destroy(q); // 銷毀隊(duì)列
    return 0;
}

鏈表隊(duì)列

#include <stdio.h>
#include <stdlib.h>

// 定義隊(duì)列節(jié)點(diǎn)結(jié)構(gòu)體
struct queue_node {
    int data;
    struct queue_node* next;
};

// 定義隊(duì)列結(jié)構(gòu)體
struct queue {
    struct queue_node* front; // 隊(duì)首指針
    struct queue_node* rear; // 隊(duì)尾指針
    int size; // 當(dāng)前隊(duì)列中存儲(chǔ)的元素個(gè)數(shù)
};

// 初始化隊(duì)列
struct queue* init() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    return q;
}

// 判斷隊(duì)列是否為空
int is_empty(struct queue* q) {
    return q->size == 0;
}

// 同鏈表?xiàng)?，鏈表?duì)列沒有固定的大小限制，因此不需要判斷隊(duì)列是否已滿

// 入隊(duì)
void enqueue(struct queue* q, int value) {
    // 創(chuàng)建新節(jié)點(diǎn)
    struct queue_node* new_node = (struct queue_node*)malloc(sizeof(struct queue_node));
    new_node->data = value;
    new_node->next = NULL;

    if (is_empty(q)) {
        q->front = new_node;
        q->rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }

    q->size++;
}

// 出隊(duì)
int dequeue(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }

    struct queue_node* temp = q->front;
    int value = temp->data;

    if (q->front == q->rear) {
        q->front = NULL;
        q->rear = NULL;
    } else {
        q->front = q->front->next;
    }

    free(temp);
    q->size--;

    return value;
}

// 獲取隊(duì)首元素
int front(struct queue* q) {
    if (is_empty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    return q->front->data;
}

// 獲取隊(duì)列長(zhǎng)度
int size(struct queue* q) {
    return q->size;
}

// 銷毀隊(duì)列
void destroy(struct queue* q) {
    while (!is_empty(q)) {
        dequeue(q);
    }
    free(q);
}

int main() {
    struct queue* q = init();
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    printf("%d\n", dequeue(q)); // 輸出10
    printf("%d\n", front(q)); // 輸出20
    enqueue(q, 40);
    printf("%d\n", dequeue(q)); // 輸出20
    printf("%d\n", dequeue(q)); // 輸出30
    printf("%d\n", dequeue(q)); // 輸出40
    printf("%d\n", dequeue(q)); // 輸出Queue Underflow
    destroy(q); // 銷毀隊(duì)列
    return 0;
}

結(jié)論

棧和隊(duì)列作為常見的數(shù)據(jù)結(jié)構(gòu)，在算法和程序設(shè)計(jì)中扮演著重要的角色。本文總結(jié)了棧和隊(duì)列的特點(diǎn)、應(yīng)用場(chǎng)景以及C語(yǔ)言實(shí)現(xiàn)。通過深入理解它們的原理和應(yīng)用，可以更好地解決問題和優(yōu)化算法。希望本文能夠?qū)ψx者對(duì)棧和隊(duì)列的學(xué)習(xí)和應(yīng)用提供幫助。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-474034.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列——算法與數(shù)據(jù)結(jié)構(gòu)入門筆記（四）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！