链表&&栈&&队列（顺序/链式）

链表#

1
#include <iostream>
2
#include <cstdlib> // 用于 malloc 和 free
3
using namespace std;
4

5
// 定义链表节点
6
typedef struct ListNode {
7
    int val;
8
    ListNode* next;
9
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
10
} Node;
11

12
// 创建新节点
13
Node* createNode(int data) {
14
    Node* newNode = (Node*)malloc(sizeof(Node));
15
    if (!newNode) { // 确保分配成功
16
        cout << "内存分配失败！" << endl;
17
        exit(1);
18
    }
19
    newNode->val = data;
20
    newNode->next = NULL;
21
    return newNode;
22
}
23

24
// 在链表头部插入节点
25
void insertAtHead(Node** head, int data) {
26
    Node* newNode = createNode(data);
27
    newNode->next = *head;
28
    *head = newNode;
29
}
30

31
// 删除指定值的节点
32
void deleteNode(Node** head, int key) {
33
    if (*head == NULL) return; // 避免访问空指针
34

35
    Node* temp = *head, *prev = NULL;
36

37
    if (temp != NULL && temp->val == key) {
38
        *head = temp->next; // 确保头指针更新
39
        free(temp);
40
        return;
41
    }
42

43
    while (temp != NULL && temp->val != key) {
44
        prev = temp;
45
        temp = temp->next;
46
    }
47

48
    if (temp == NULL) return;
49

50
    prev->next = temp->next;
51
    free(temp);
52
}
53

54
// 更新指定值的节点
55
void updateNode(Node* head, int key, int newData) {
56
    Node* temp = head;
57
    while (temp != NULL) {
58
        if (temp->val == key) {
59
            temp->val = newData;
60
            break;
61
        }
62
        temp = temp->next;
63
    }
64
}
65

66
// 查找指定值的节点
67
Node* searchNode(Node* head, int key) {
68
    Node* temp = head;
69
    while (temp != NULL) {
70
        if (temp->val == key) {
71
            return temp;
72
        }
73
        temp = temp->next;
74
    }
75
    return NULL;
76
}
77

78
// 反转链表（迭代）
79
void reverseList(Node** head) {
80
    if (*head == NULL) return; // 避免访问空指针
81

82
    Node* prev = NULL;
83
    Node* current = *head;
84
    Node* next = NULL;
85

86
    while (current != NULL) {
87
        next = current->next;
88
        current->next = prev;
89
        prev = current;
90
        current = next;
91
    }
92

93
    *head = prev;
94
}
95

96
// 反转链表（递归）
97
Node* reverse(Node* head) {
98
    if (head == NULL || head->next == NULL) {
99
        return head;
100
    }
101
    Node* newHead = reverse(head->next);
102
    head->next->next = head;
103
    head->next = NULL;
104
    return newHead;
105
}
106

107
// 打印链表
108
void printList(Node* head) {
109
    Node* temp = head;
110
    while (temp != NULL) {
111
        cout << temp->val << " ";
112
        temp = temp->next;
113
    }
114
    cout << endl;
115
}
116

117
int main() {
118
    Node* head = NULL; // 初始化链表为空
119

120
    // 插入节点
121
    insertAtHead(&head, 3);
122
    insertAtHead(&head, 2);
123
    insertAtHead(&head, 1);
124
    cout << "插入后的链表: ";
125
    printList(head);
126

127
    // 删除节点
128
    deleteNode(&head, 2);
129
    cout << "删除后的链表: ";
130
    printList(head);
131

132
    // 更新节点
133
    updateNode(head, 3, 30);
134
    cout << "更新后的链表: ";
135
    printList(head);
136

137
    // 查找节点
138
    Node* found = searchNode(head, 30);
139
    if (found) {
140
        cout << "找到节点: " << found->val << endl;
141
    } else {
142
        cout << "未找到节点" << endl;
143
    }
144

145
    // 反转链表（迭代）
146
    reverseList(&head);
147
    cout << "反转后的链表: ";
148
    printList(head);
149

150
    return 0;
151
}

栈#

顺序栈#

1
#include <stdio.h>
2
#include <stdbool.h>
3

4
#define MAXSIZE 100 // 定义栈的最大大小
5

6
typedef struct {
7
    int data[MAXSIZE];
8
    int top;
9
} stack;
10

11
void init(stack *s) {
12
    s->top = -1;
13
}
14

15
// 判断栈是否为空
16
bool isEmpty(stack *s) {
17
    return s->top == -1;
18
}
19

20
// 判断栈是否满
21
bool isFull(stack *s) {
22
    return s->top == MAXSIZE - 1;
23
}
24

25
// 入栈
26
void push(stack* s, int x) {
27
    if (isFull(s)) {
28
        printf("栈满\n");
29
        return;
30
    }
31
    s->data[++s->top] = x;
32
}
33

34
// 出栈
35
void pop(stack *s, int *x) {
36
    if (isEmpty(s)) {
37
        printf("栈为空\n");
38
    }
39
    *x = s->data[s->top--]; // 先取值，再减少 top
40
}
41

42
// 打印栈
43
void printStack(stack *s) {
44
    if (isEmpty(s)) {
45
        printf("栈为空\n");
46
        return;
47
    }
48
    printf("栈内容: ");
49
    for (int i = 0; i <= s->top; i++) {
50
        printf("%d ", s->data[i]);
51
    }
52
    printf("\n");
53
}
54

55
int main() {
56
    stack s;
57
    init(&s);
58

59
    push(&s, 10);
60
    push(&s, 20);
61
    push(&s, 30);
62
    printStack(&s);
63

64
    int val;
65
    if (pop(&s, &val)) {
66
        printf("出栈: %d\n", val);
67
    }
68
    printStack(&s);
69

70
    return 0;
71
}
72
#### 链栈
73

74

75
```cpp
76
#include <stdio.h>
77
#include <stdlib.h>
78
#include <stdbool.h>
79

80
// 链栈结点
81
typedef struct StackNode {
82
    int data;
83
    struct StackNode *next;
84
} StackNode;
85

86
// 链栈结构
87
typedef struct {
88
    StackNode *top;
89
    int count;
90
} LinkStack;
91

92
// 初始化链栈
93
void InitStack(LinkStack *stack) {
94
    stack->top = NULL;
95
    stack->count = 0;
96
}
97

98
// 入栈操作
99
void push(LinkStack *s, int x) {
100
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
101
    if (p == NULL) { // 确保内存分配成功
102
        printf("内存分配失败！\n");
103
        return;
104
    }
105
    p->data = x;
106
    p->next = s->top;
107
    s->top = p;
108
    s->count++;
109
    printf("入栈: %d\n", x);
110
}
111

112
// 出栈操作
113
bool pop(LinkStack *s, int *x) {
114
    if (s->top == NULL) {
115
        printf("栈为空，无法出栈！\n");
116
        return false; // 失败返回 false
117
    }
118
    StackNode *p = s->top;
119
    if (x != NULL) {
120
        *x = p->data;
121
    }
122
    s->top = s->top->next;
123
    free(p);
124
    s->count--;
125

126
    if (x != NULL) {
127
        printf("出栈: %d\n", *x);
128
    }
129
    return true; // 成功返回 true
130
}
131

132
// 打印栈
133
void printStack(LinkStack *s) {
134
    StackNode *p = s->top;
135
    printf("当前栈内容: ");
136
    while (p) {
137
        printf("%d ", p->data);
138
        p = p->next;
139
    }
140
    printf("\n");
141
}
142

143
// 测试代码
144
int main() {
145
    LinkStack stack;
146
    InitStack(&stack);
147

148
    push(&stack, 10);
149
    push(&stack, 20);
150
    push(&stack, 30);
151
    printStack(&stack);
152

153
    int val;
154
    if (pop(&stack, &val)) {
155
        printf("成功出栈: %d\n", val);
156
    }
157
    printStack(&stack);
158

159
    return 0;
160
}

队列#

顺序队列#

1
#include <stdio.h>
2
#include <stdbool.h>
3

4
#define MAXSIZE 5  // 定义队列最大长度
5

6
typedef struct {
7
    int data[MAXSIZE];
8
    int front;  // 头指针，指向队首元素
9
    int rear;   // 尾指针，指向队尾元素的下一个位置
10
} Queue;
11

12
// 初始化队列
13
void init(Queue *q) {
14
    q->front = q->rear = 0;
15
}
16

17
// 判断队列是否为空
18
bool isEmpty(Queue *q) {
19
    return q->front == q->rear;
20
}
21

22
// 判断队列是否已满
23
bool isFull(Queue *q) {
24
    return (q->rear + 1) % MAXSIZE == q->front;
25
}
26

27
// 入队操作
28
void enqueue(Queue *q, int x) {
29
    if (isFull(q)) {
30
        printf("队列已满\n");
31
        return;
32
    }
33
    q->data[q->rear] = x;
34
    q->rear = (q->rear + 1) % MAXSIZE;
35
    printf("入队: %d\n", x);
36
}
37

38
// 出队操作
39
bool dequeue(Queue *q, int *x) {
40
    if (isEmpty(q)) {
41
        printf("队列为空\n");
42
        return false;
43
    }
44
    if (x != NULL) {
45
        *x = q->data[q->front];
46
    }
47
    q->front = (q->front + 1) % MAXSIZE;
48
    printf("出队: %d\n", *x);
49
    return true;
50
}
51

52
// 打印队列
53
void printQueue(Queue *q) {
54
    if (isEmpty(q)) {
55
        printf("队列为空\n");
56
        return;
57
    }
58
    printf("队列内容: ");
59
    for (int i = q->front; i != q->rear; i = (i + 1) % MAXSIZE) {
60
        printf("%d ", q->data[i]);
61
    }
62
    printf("\n");
63
}
64

65
// 测试代码
66
int main() {
67
    Queue q;
68
    init(&q);
69

70
    enqueue(&q, 10);
71
    enqueue(&q, 20);
72
    enqueue(&q, 30);
73
    enqueue(&q, 40);
74
    printQueue(&q);
75

76
    int val;
77
    if (dequeue(&q, &val)) {
78
        printf("成功出队: %d\n", val);
79
    }
80
    printQueue(&q);
81

82
    enqueue(&q, 50);
83
    enqueue(&q, 60);
84
    printQueue(&q);
85

86
    return 0;
87
}
88
#### 链队列
89

90

91
```cpp
92
#include <stdio.h>
93
#include <stdlib.h>
94
#include <stdbool.h>
95

96
// 链表节点定义
97
typedef struct Node {
98
    int data;
99
    struct Node *next;
100
} Node;
101

102
// 队列定义
103
typedef struct {
104
    Node *front;
105
    Node *rear;
106
} Queue;
107

108
// 初始化队列
109
void initQueue(Queue *q) {
110
    q->front = q->rear = NULL;
111
}
112

113
// 判断队列是否为空
114
bool isEmpty(Queue *q) {
115
    return q->front == NULL;
116
}
117

118
// 入队操作
119
void enqueue(Queue *q, int x) {
120
    Node *newNode = (Node *)malloc(sizeof(Node));
121
    if (newNode == NULL) {
122
        printf("内存分配失败！\n");
123
        return;
124
    }
125
    newNode->data = x;
126
    newNode->next = NULL;
127

128
    if (q->rear == NULL) {
129
        q->front = newNode;
130
        q->rear = newNode;
131
    } else {
132
        q->rear->next = newNode;
133
        q->rear = newNode;
134
    }
135
    printf("入队: %d\n", x);
136
}
137

138
// 出队操作
139
bool dequeue(Queue *q, int *x) {
140
    if (isEmpty(q)) {
141
        printf("队列为空，无法出队！\n");
142
        return false;
143
    }
144

145
    Node *p = q->front;
146
    *x = p->data;
147
    q->front = p->next;
148
    if (q->front == NULL) {
149
        q->rear = NULL;  // 如果队列空了，更新队尾指针
150
    }
151
    free(p);
152
    printf("出队: %d\n", *x);
153
    return true;
154
}
155

156
// 打印队列
157
void printQueue(Queue *q) {
158
    if (isEmpty(q)) {
159
        printf("队列为空\n");
160
        return;
161
    }
162
    Node *p = q->front;
163
    printf("队列内容: ");
164
    while (p != NULL) {
165
        printf("%d ", p->data);
166
        p = p->next;
167
    }
168
    printf("\n");
169
}
170

171
// 测试代码
172
int main() {
173
    Queue q;
174
    initQueue(&q);
175

176
    enqueue(&q, 10);
177
    enqueue(&q, 20);
178
    enqueue(&q, 30);
179
    printQueue(&q);
180

181
    int val;
182
    if (dequeue(&q, &val)) {
183
        printf("成功出队: %d\n", val);
184
    }
185
    printQueue(&q);
186

187
    enqueue(&q, 40);
188
    printQueue(&q);
189

190
    return 0;
191
}

原文发布于 CSDN：链表&&栈&&队列（顺序/链式）