栈与数组类似，但功能受限，只能通过 push 将新元素添加到栈的顶部，通过 pop 从栈中移除顶部的元素，并通过 peek 查看顶部的元素而不将其弹出。栈提供了后进先出（LIFO, last-in first-out）的顺序，最后推入的元素将在下一次弹出时首先出栈。
堆栈的实现方式
在 C 语言中，可以使用以下方法来实现堆栈（stack）数据结构：
-
使用数组：可以使用一个固定大小的数组来表示堆栈。堆栈有两个重要的指针：一个是指向栈顶的指针，另一个是指向栈底的指针。在数组中，栈顶指针指向最新添加的元素，栈底指针指向最旧的元素。可以使用数组的索引来实现栈的推入 (push) 和弹出 (pop) 操作。
-
使用链表：可以使用链表来表示堆栈。链表中的每个节点包含一个元素和一个指向下一个节点的指针。栈顶指针指向链表的第一个节点，栈底指针指向链表的最后一个节点。入栈操作将创建一个新节点，并将其插入链表的开头；出栈操作将删除链表的第一个节点。
链表实现堆栈时，采用头插法，即在链表头结点前插入新节点、删除节点。这样做，方便 push 和 pop 操作；如果在链表的最后插入新节点，那么在 pop 操作时，更新栈顶的节点指针将会很麻烦 & 费时。
这篇文章将介绍使用数组实现堆栈这种数据结构。
数组实现堆栈
定义并初始化堆栈结构
使用一个固定长度的数组来实现具有先进先出的堆栈结构。为了将不同的堆栈和栈顶位置对应起来，这里使用一个结构体来组合堆栈和栈顶位置。
1
2
3
4
5
6
7
| #define MAX_SIZE (3)
#define EXCEPTION_VALUE (-1)
typedef struct stack {
int data[MAX_SIZE];
int top;
} Stack;
|
初始化堆栈
1
2
3
4
| void initStack(Stack *stack) {
stack->top = -1;
}
|
判断堆栈是否为空
1
2
3
4
|
bool isEmpty(Stack *stack) {
return stack->top == -1;
}
|
判断堆栈是否已满
1
2
3
4
|
bool isFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
|
入栈操作
1
2
3
4
5
6
7
8
9
10
|
int push(Stack *stack, int element) {
if (isFull(stack)) {
printf("Stack is full\n");
return EXCEPTION_VALUE;
} else {
stack->data[++(stack->top)] = element;
return 0;
}
}
|
出栈操作
1
2
3
4
5
6
7
8
9
|
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
return stack->data[(stack->top)--];
}
}
|
为了区分栈空时的返回值与正常出栈的数据，需要定义异常值为不会出现在正常数据中的值；或者修改函数的返回值为指针类型，返回值不为空时对应着有效数据。
获取栈顶元素
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->data[stack->top];
}
}
|
打印堆栈数据
1
2
3
4
5
6
7
8
9
10
11
12
|
void printStack(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
} else {
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
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
| #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE (3)
#define EXCEPTION_VALUE (-1)
typedef struct stack {
int data[MAX_SIZE];
int top;
} Stack;
void initStack(Stack *stack) {
stack->top = -1;
}
bool isEmpty(Stack *stack) {
return stack->top == -1;
}
bool isFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}
int push(Stack *stack, int element) {
if (isFull(stack)) {
printf("Stack is full\n");
return EXCEPTION_VALUE;
} else {
stack->data[++(stack->top)] = element;
return 0;
}
}
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
return stack->data[(stack->top)--];
}
}
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return EXCEPTION_VALUE;
} else {
return stack->data[stack->top];
}
}
void printStack(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
} else {
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
}
int main(int *argc, char *argv[]) {
Stack stack1;
initStack(&stack1);
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: 1 2 3
Stack is full
Stack: 1 2 3
Pop element: 3
Stack: 1 2
Top element: 2
Stack: 1 2
|
