堆栈提供了一种后进先出（LIFO, last-in first-out）存储结构。在 数据结构之堆栈（数组实现）中，我们介绍了数组实现的堆栈，这篇文章将介绍通过链表的方式实现堆栈这种数据结构。
堆栈的实现方式
在 C 语言中，可以使用以下方法来实现堆栈（stack）数据结构：
-
使用数组：可以使用一个固定大小的数组来表示堆栈。堆栈有两个重要的指针：一个是指向栈顶的指针，另一个是指向栈底的指针。在数组中，栈顶指针指向最新添加的元素，栈底指针指向最旧的元素。可以使用数组的索引来实现栈的推入 (push) 和弹出 (pop) 操作。
-
使用链表：可以使用链表来表示堆栈。链表中的每个节点包含一个元素和一个指向下一个节点的指针。栈顶指针指向链表的第一个节点，栈底指针指向链表的最后一个节点。入栈操作将创建一个新节点，并将其插入链表的开头；出栈操作将删除链表的第一个节点。
链表实现堆栈时，采用头插法，即在链表头结点前插入新节点、删除节点。这样做，方便 push 和 pop 操作；如果在链表的最后插入新节点，那么在 pop 操作时，更新栈顶的节点指针将会很麻烦 & 费时。
链表实现堆栈的优点
链表实现堆栈相比于数组实现堆栈有以下几个优点：
- 动态大小：链表实现的堆栈可以根据需要动态调整大小，而数组实现的堆栈需要预先指定大小。这意味着链表实现的堆栈可以根据实际需求进行扩展或缩小，而不会浪费内存或导致栈溢出。
- 内存管理：链表实现的堆栈只使用必要的内存空间，而数组实现的堆栈在创建时需要一定大小的连续内存空间。这意味着链表实现的堆栈可以更好地处理内存管理，避免浪费内存或导致内存溢出。
总的来说，链表实现的堆栈更加灵活和动态，适用于需要频繁插入和删除操作的场景，而数组实现的堆栈更适用于事先知道栈大小且不需要频繁调整大小的场景。
链表实现堆栈
定义并初始化堆栈结构
1
2
3
4
5
6
7
8
9
10
| typedef struct node {
int data;
struct node *next;
} Node;
typedef struct stack {
int size;
int max;
Node *top;
} Stack;
|
在这里，我们使用一个结构体实现具有先进先出的堆栈结构，其中的两个成员标记这堆栈中的数据量和最大存储数据量大小，另一个成员标记着栈顶地址。
- 这里的栈顶地址，即为链表的头结点地址，所有这个成员的数据类型为链表结构：
- 链表结构中需要包含存放的数据和指向下一个数据的地址。
其中，成员 size 和成员 max 主要用于执行堆栈是否为空和堆栈是否已满操作，top指针主要用于执行堆栈的入栈、出栈和栈顶查询等操作。
初始化堆栈
1
2
3
4
5
6
7
8
9
10
11
12
| #define EXCEPTION_VALUE (-1)
int max_size = 10;
Stack *initStack(int max_size)
{
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->size = 0;
stack->max = max_size;
stack->top = NULL;
return stack;
}
|
判断堆栈是否为空
1
2
3
4
|
bool isEmpty(Stack *stack) {
return stack->size == 0;
}
|
判断堆栈是否已满
1
2
3
4
|
bool isFull(Stack *stack) {
return stack->size >= stack->max;
}
|
入栈操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int push(Stack *stack, int element) {
if (isFull(stack)) {
printf("Stack is full\n");
return EXCEPTION_VALUE;
} else {
Node *node = (Node *)malloc(sizeof(Node));
node->data = element;
node->next = stack->top;
stack->size++;
stack->top = node;
return 0;
}
}
|
出栈操作
1
2
3
4
5
6
7
8
9
10
11
12
|
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
int topVal = stack->top->data;
stack->top = stack->top->next;
stack->size--;
return topVal;
}
}
|
为了区分栈空时的返回值与正常出栈的数据，需要定义异常值为不会出现在正常数据中的值；或者修改函数的返回值为指针类型，返回值不为空时对应着有效数据。
获取栈顶元素
1
2
3
4
5
6
7
8
9
|
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
return stack->top->data;
}
}
|
打印堆栈数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void printStack(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
} else {
printf("Stack: ");
Node *head = stack->top;
while (head) {
printf("%d ", head->data);
head = head->next;
}
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
| #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define EXCEPTION_VALUE (-1)
typedef struct node {
int data;
struct node *next;
} Node;
typedef struct stack {
int size;
int max;
Node *top;
} Stack;
Stack *initStack(int max_size)
{
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->size = 0;
stack->max = max_size;
stack->top = NULL;
return stack;
}
bool isEmpty(Stack *stack) {
return stack->size == 0;
}
bool isFull(Stack *stack) {
return stack->size >= stack->max;
}
int push(Stack *stack, int element) {
if (isFull(stack)) {
printf("Stack is full\n");
return EXCEPTION_VALUE;
} else {
Node *node = (Node *)malloc(sizeof(Node));
node->data = element;
node->next = stack->top;
stack->size++;
stack->top = node;
return 0;
}
}
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
int topVal = stack->top->data;
stack->top = stack->top->next;
stack->size--;
return topVal;
}
}
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
return stack->top->data;
}
}
void printStack(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
} else {
printf("Stack: ");
Node *head = stack->top;
while (head) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
}
int main(int *argc, char *argv[]) {
Stack *stack1 = NULL;
stack1 = initStack(3);
printStack(stack1);
push(stack1, 1);
push(stack1, 2);
push(stack1, 3);
printStack(stack1);
push(stack1, 4);
printStack(stack1);
printf("Pop element: %d\n", pop(stack1));
printStack(stack1);
printf("Top element: %d\n", peek(stack1));
printStack(stack1);
return 0;
}
|
程序的输出结果为：
1
2
3
4
5
6
7
8
| Stack is empty
Stack: 3 2 1
Stack is full
Stack: 3 2 1
Pop element: 3
Stack: 2 1
Top element: 2
Stack: 2 1
|
