队列/栈

数据结构

栈与队列

栈（Stack）和队列（Queue）是两种非常重要且常用的线性数据结构。它们都限制了数据的插入和删除方式，使得它们在特定场景下表现出独特的优势。

栈（Stack）

栈是一种“后进先出”（Last In, First Out - LIFO）的数据结构。你可以把它想象成一叠盘子，你最后放上去的盘子，总是最先被拿走。

栈的基本概念

  • 栈顶（Top）: 栈中允许插入和删除元素的一端。
  • 栈底（Bottom）: 栈中不允许插入和删除元素的另一端。
  • 压栈/入栈（Push）: 向栈中添加元素的操作。
  • 弹栈/出栈（Pop）: 从栈中移除元素的操作。

C 语言中栈的实现

栈可以使用数组或链表来实现。这里我们主要介绍基于链表的实现，因为它在动态大小方面更灵活。

栈节点定义

由于栈的特性，我们只需要单向链表的节点结构即可。

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <stdlib.h> // 包含 malloc 和 free 函数

// 定义栈节点结构体
typedef struct StackNode {
    int data;             // 数据域
    struct StackNode *next; // 指向下一个节点的指针
} StackNode;
栈的初始化

栈的初始化就是将栈顶指针设为 NULL。

1
2
3
4
// 初始化一个空栈（栈顶指针）
StackNode* initStack() {
    return NULL; // 空栈的栈顶指向NULL
}
压栈/入栈操作 (Push)

新元素总是插入到栈顶。这与链表的头部插入操作类似。

1
2
3
4
5
6
7
8
9
10
11
// 压栈操作：向栈中添加元素
StackNode* push(StackNode* top, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode)); // 分配内存
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value; // 设置数据
    newNode->next = top;   // 新节点的next指向原来的栈顶
    return newNode;        // 返回新节点作为新的栈顶
}
弹栈/出栈操作 (Pop)

从栈顶移除元素。这与链表的头部删除操作类似，需要处理栈空的情况。

1
2
3
4
5
6
7
8
9
10
11
12
// 弹栈操作：从栈中移除元素
int pop(StackNode** top) { // 注意这里使用二级指针，因为需要修改top的值
    if (*top == NULL) {
        printf("栈为空，无法弹栈！\n");
        exit(1); // 或者返回一个错误码
    }
    StackNode* temp = *top;     // 临时保存当前栈顶
    int poppedValue = temp->data; // 获取栈顶数据
    *top = (*top)->next;       // 栈顶下移
    free(temp);                // 释放原栈顶内存
    return poppedValue;
}
查看栈顶元素 (Peek/Top)

不移除元素，只返回栈顶元素的值。

1
2
3
4
5
6
7
8
// 查看栈顶元素（不移除）
int peek(StackNode* top) {
    if (top == NULL) {
        printf("栈为空，无法查看栈顶元素！\n");
        exit(1);
    }
    return top->data;
}
判断栈是否为空 (isEmpty)
1
2
3
4
// 判断栈是否为空
int isStackEmpty(StackNode* top) {
    return top == NULL;
}
遍历栈并打印数据
1
2
3
4
5
6
7
8
9
10
// 打印栈所有节点的数据
void printStack(StackNode* top) {
    StackNode* current = top;
    printf("栈内容（从栈顶到栈底）：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
释放栈内存
1
2
3
4
5
6
7
8
9
10
// 释放栈所有节点的内存
void freeStack(StackNode* top) {
    StackNode* current = top;
    while (current != NULL) {
        StackNode* temp = current;
        current = current->next;
        free(temp);
    }
    printf("栈内存已释放。\n");
}

完整栈示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>

// 定义栈节点结构体
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// 初始化一个空栈（栈顶指针）
StackNode* initStack() {
    return NULL;
}

// 压栈操作：向栈中添加元素
StackNode* push(StackNode* top, int value) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = top;
    return newNode;
}

// 弹栈操作：从栈中移除元素
int pop(StackNode** top) {
    if (*top == NULL) {
        printf("栈为空，无法弹栈！\n");
        exit(1);
    }
    StackNode* temp = *top;
    int poppedValue = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedValue;
}

// 查看栈顶元素（不移除）
int peek(StackNode* top) {
    if (top == NULL) {
        printf("栈为空，无法查看栈顶元素！\n");
        exit(1);
    }
    return top->data;
}

// 判断栈是否为空
int isStackEmpty(StackNode* top) {
    return top == NULL;
}

// 打印栈所有节点的数据
void printStack(StackNode* top) {
    StackNode* current = top;
    printf("栈内容（从栈顶到栈底）：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 释放栈所有节点的内存
void freeStack(StackNode* top) {
    StackNode* current = top;
    while (current != NULL) {
        StackNode* temp = current;
        current = current->next;
        free(temp);
    }
    printf("栈内存已释放。\n");
}

int main() {
    StackNode* myStack = initStack(); // 初始化空栈

    printf("------ 栈操作 ------\n");
    printf("栈是否为空：%s\n", isStackEmpty(myStack) ? "是" : "否");

    myStack = push(myStack, 10);
    printStack(myStack);

    myStack = push(myStack, 20);
    printStack(myStack);

    myStack = push(myStack, 30);
    printStack(myStack);

    printf("栈顶元素：%d\n", peek(myStack));
    printf("弹栈元素：%d\n", pop(&myStack));
    printStack(myStack);

    printf("弹栈元素：%d\n", pop(&myStack));
    printStack(myStack);

    printf("栈是否为空：%s\n", isStackEmpty(myStack) ? "是" : "否");

    printf("弹栈元素：%d\n", pop(&myStack));
    printStack(myStack);

    printf("栈是否为空：%s\n", isStackEmpty(myStack) ? "是" : "否");

    // 尝试在空栈上弹栈或查看栈顶
    // pop(&myStack); // 会导致程序退出
    // peek(myStack); // 会导致程序退出

    printf("\n------ 内存释放 ------\n");
    myStack = push(myStack, 5);
    myStack = push(myStack, 15);
    printStack(myStack);
    freeStack(myStack);
    myStack = NULL; // 释放后将栈顶指针设为NULL
    
    printStack(myStack); // 尝试打印已释放的栈

    return 0;
}

队列（Queue）

队列是一种“先进先出”（First In, First Out - FIFO）的数据结构。你可以把它想象成排队等候的队伍，最先排队的人总是最先得到服务。

队列的基本概念

  • 队头（Front）: 队列中允许删除元素的一端。
  • 队尾（Rear）: 队列中允许插入元素的一端。
  • 入队（Enqueue）: 向队列中添加元素的操作。
  • 出队（Dequeue）: 从队列中移除元素的操作。

C 语言中队列的实现

队列同样可以使用数组或链表来实现。这里我们主要介绍基于链表的实现，因为它能更好地处理队列的动态增长和收缩。

为了高效地进行入队（在队尾插入）和出队（在队头删除），我们通常会维护两个指针：一个指向队头（front），一个指向队尾（rear）。

队列节点定义

与栈类似，使用单向链表节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <stdlib.h>

// 定义队列节点结构体
typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

// 定义队列结构体，包含队头和队尾指针
typedef struct Queue {
    QueueNode *front; // 队头指针
    QueueNode *rear;  // 队尾指针
} Queue;
队列的初始化

初始化时，队头和队尾指针都指向 NULL。

1
2
3
4
5
6
7
8
9
10
11
// 初始化一个空队列
Queue* initQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}
入队操作 (Enqueue)

新元素总是添加到队尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 入队操作：向队列中添加元素
void enqueue(Queue* q, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL; // 新节点总是队列的最后一个，所以next为NULL

    if (q->rear == NULL) { // 如果队列为空
        q->front = newNode; // 新节点既是队头也是队尾
        q->rear = newNode;
    } else {
        q->rear->next = newNode; // 原队尾的next指向新节点
        q->rear = newNode;       // 更新队尾为新节点
    }
    printf("元素 %d 入队。\n", value);
}
出队操作 (Dequeue)

从队头移除元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 出队操作：从队列中移除元素
int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    QueueNode* temp = q->front; // 临时保存队头
    int dequeuedValue = temp->data; // 获取队头数据
    q->front = q->front->next;   // 队头下移

    if (q->front == NULL) { // 如果队列出队后变为空
        q->rear = NULL;     // 队尾也设为NULL
    }
    free(temp); // 释放原队头内存
    printf("元素 %d 出队。\n", dequeuedValue);
    return dequeuedValue;
}
查看队头元素 (Front)

不移除元素，只返回队头元素的值。

1
2
3
4
5
6
7
8
// 查看队头元素（不移除）
int front(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空，无法查看队头元素！\n");
        exit(1);
    }
    return q->front->data;
}
判断队列是否为空 (isEmpty)
1
2
3
4
// 判断队列是否为空
int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}
遍历队列并打印数据
1
2
3
4
5
6
7
8
9
10
// 打印队列所有节点的数据
void printQueue(Queue* q) {
    QueueNode* current = q->front;
    printf("队列内容（从队头到队尾）：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
释放队列内存
1
2
3
4
5
6
7
8
9
10
11
// 释放队列所有节点的内存
void freeQueue(Queue* q) {
    QueueNode* current = q->front;
    while (current != NULL) {
        QueueNode* temp = current;
        current = current->next;
        free(temp);
    }
    free(q); // 最后释放队列结构体本身
    printf("队列内存已释放。\n");
}

完整队列示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include <stdlib.h>

// 定义队列节点结构体
typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

// 定义队列结构体，包含队头和队尾指针
typedef struct Queue {
    QueueNode *front; // 队头指针
    QueueNode *rear;  // 队尾指针
} Queue;

// 初始化一个空队列
Queue* initQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (q == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    q->front = NULL;
    q->rear = NULL;
    return q;
}

// 入队操作：向队列中添加元素
void enqueue(Queue* q, int value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) { // 如果队列为空
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("元素 %d 入队。\n", value);
}

// 出队操作：从队列中移除元素
int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    QueueNode* temp = q->front;
    int dequeuedValue = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) { // 如果队列出队后变为空
        q->rear = NULL;
    }
    free(temp);
    printf("元素 %d 出队。\n", dequeuedValue);
    return dequeuedValue;
}

// 查看队头元素（不移除）
int front(Queue* q) {
    if (q->front == NULL) {
        printf("队列为空，无法查看队头元素！\n");
        exit(1);
    }
    return q->front->data;
}

// 判断队列是否为空
int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}

// 打印队列所有节点的数据
void printQueue(Queue* q) {
    QueueNode* current = q->front;
    printf("队列内容（从队头到队尾）：");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 释放队列所有节点的内存
void freeQueue(Queue* q) {
    QueueNode* current = q->front;
    while (current != NULL) {
        QueueNode* temp = current;
        current = current->next;
        free(temp);
    }
    free(q);
    printf("队列内存已释放。\n");
}

int main() {
    Queue* myQueue = initQueue(); // 初始化空队列

    printf("------ 队列操作 ------\n");
    printf("队列是否为空：%s\n", isQueueEmpty(myQueue) ? "是" : "否");

    enqueue(myQueue, 100);
    printQueue(myQueue);

    enqueue(myQueue, 200);
    printQueue(myQueue);

    enqueue(myQueue, 300);
    printQueue(myQueue);

    printf("队头元素：%d\n", front(myQueue));
    dequeue(myQueue);
    printQueue(myQueue);

    dequeue(myQueue);
    printQueue(myQueue);

    printf("队列是否为空：%s\n", isQueueEmpty(myQueue) ? "是" : "否");

    printf("队头元素：%d\n", front(myQueue)); // 此时队列只有一个元素
    dequeue(myQueue);
    printQueue(myQueue);

    printf("队列是否为空：%s\n", isQueueEmpty(myQueue) ? "是" : "否");

    // 尝试在空队列上出队或查看队头
    // dequeue(myQueue); // 会导致程序退出
    // front(myQueue);   // 会导致程序退出

    printf("\n------ 内存释放 ------\n");
    enqueue(myQueue, 50); // 再次入队一些元素
    enqueue(myQueue, 60);
    printQueue(myQueue);
    freeQueue(myQueue);
    myQueue = NULL; // 释放后将队列指针设为NULL
    
    // 尝试打印已释放的队列
    // printQueue(myQueue); // 会导致段错误，因为q已是NULL

    return 0;
}

Title:队列/栈

Author:

Created:2025-06-04, 15:21:05

Updated:2025-06-04, 15:26:39

Full URL:http://example.com/2025/06/04/%E9%98%9F%E5%88%97-%E6%A0%88/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 栈与队列
    1. 1.1. 栈（Stack）
      1. 1.1.1. 栈的基本概念
      2. 1.1.2. C 语言中栈的实现
        1. 1.1.2.1. 栈节点定义
        2. 1.1.2.2. 栈的初始化
        3. 1.1.2.3. 压栈/入栈操作 (Push)
        4. 1.1.2.4. 弹栈/出栈操作 (Pop)
        5. 1.1.2.5. 查看栈顶元素 (Peek/Top)
        6. 1.1.2.6. 判断栈是否为空 (isEmpty)
        7. 1.1.2.7. 遍历栈并打印数据
        8. 1.1.2.8. 释放栈内存
      3. 1.1.3. 完整栈示例代码
    2. 1.2. 队列（Queue）
      1. 1.2.1. 队列的基本概念
      2. 1.2.2. C 语言中队列的实现
        1. 1.2.2.1. 队列节点定义
        2. 1.2.2.2. 队列的初始化
        3. 1.2.2.3. 入队操作 (Enqueue)
        4. 1.2.2.4. 出队操作 (Dequeue)
        5. 1.2.2.5. 查看队头元素 (Front)
        6. 1.2.2.6. 判断队列是否为空 (isEmpty)
        7. 1.2.2.7. 遍历队列并打印数据
        8. 1.2.2.8. 释放队列内存
      3. 1.2.3. 完整队列示例代码
|