第四节、堆栈

1.数组形式堆栈的实现

（1）堆栈的定义以及结构体

堆栈可以理解为先入后出，一端进一端出。它的结构体为：

1
2
3
4
5
6
7
#define MAX_SIZE 100 // 栈的最大容量

// 定义栈结构
typedef struct {
    int data[MAX_SIZE]; // 存储栈元素的数组
    int top; // 栈顶指针，指向栈顶元素
} Stack;

（2）队列的基本操作的实现

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
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // 栈的最大容量

// 定义栈结构
typedef struct {
    int data[MAX_SIZE]; // 存储栈元素的数组
    int top; // 栈顶指针，指向栈顶元素
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = -1; // 空栈时栈顶指针为 -1
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈操作
int push(Stack* stack, int value) {
    if (isFull(stack)) {
        return 0; // 栈已满，插入失败
    }
    stack->data[++stack->top] = value; // 栈顶指针先加 1，再将值插入栈顶
    return 1; // 插入成功
}

// 出栈操作
int pop(Stack* stack, int* value) {
    if (isEmpty(stack)) {
        return 0; // 栈为空，弹出失败
    }
    *value = stack->data[stack->top--]; // 先将栈顶元素弹出，再将栈顶指针减 1
    return 1; // 弹出成功
}

// 获取栈顶元素
int getTop(Stack* stack, int* value) {
    if (isEmpty(stack)) {
        return 0; // 栈为空，获取失败
    }
    *value = stack->data[stack->top]; // 获取栈顶元素
    return 1; // 获取成功
}

// 测试
int main() {
    Stack stack;
    int value;
    initStack(&stack); // 初始化栈
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    getTop(&stack, &value);
    printf("栈顶元素为：%d\n", value); // 输出 3
    pop(&stack, &value);
    printf("弹出的元素为：%d\n", value); // 输出 3
    getTop(&stack, &value);
    printf("栈顶元素为：%d\n", value); // 输出 2
    return 0;
}

2.链表形式堆栈的实现

（1）堆栈的定义以及结构体

1
2
3
4
5
// 定义链表节点
typedef struct node {
    int data;
    struct node* next;
} Node;

（2）队列的基本操作的实现

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
#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
typedef struct node {
    int data;
    struct node* next;
} Node;

// 定义堆栈
typedef struct stack {
    Node* top;
} Stack;

// 初始化堆栈
void init(Stack* s) {
    s->top = NULL;
}

// 压入元素
void push(Stack* s, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node)); // 创建新节点
    new_node->data = data;
    new_node->next = s->top; // 新节点指向栈顶
    s->top = new_node; // 栈顶指向新节点
}

// 弹出元素
int pop(Stack* s) {
    if (s->top == NULL) { // 栈为空，无法弹出
        printf("Stack is empty.\n");
        return -1;
    }
    int data = s->top->data;
    Node* temp = s->top;
    s->top = s->top->next; // 栈顶指向下一个节点
    free(temp); // 释放被弹出节点的内存
    return data;
}

// 获取栈顶元素
int top(Stack* s) {
    if (s->top == NULL) { // 栈为空，无法获取栈顶元素
        printf("Stack is empty.\n");
        return -1;
    }
    return s->top->data;
}

// 判断栈是否为空
int is_empty(Stack* s) {
    return s->top == NULL;
}

// 打印栈中所有元素
void print_stack(Stack* s) {
    Node* current = s->top;
    printf("Stack: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 主函数
int main() {
    Stack s;
    init(&s);

    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    
    int value = top(s); // 栈顶元素
    printf("%d \n",value);
    
    
    
}