接下来我们继续深入学习数据结构中的栈和队列。这些是非常常用的数据结构，它们在许多应用场景中都有重要的作用，如表达式求值、递归、任务调度等。
第2节：栈（Stack）
2.1 栈的基本概念
栈（Stack）是一种**后进先出（LIFO）**的数据结构。栈的操作主要有两个：
push：将元素压入栈顶。pop：将栈顶元素弹出。
栈的应用包括：
递归调用的处理
表达式求值和语法解析
深度优先搜索（DFS）
2.2 栈的数组实现
栈的基本结构
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// 定义栈结构
struct Stack {
int items[MAX]; // 用数组存储栈元素
int top; // 栈顶指针
};
// 初始化栈
void initStack(struct Stack* s) {
s->top = -1; // 初始时栈为空
}
// 检查栈是否满
int isFull(struct Stack* s) {
return s->top == MAX - 1;
}
// 检查栈是否为空
int isEmpty(struct Stack* s) {
return s->top == -1;
}
// 压栈操作
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("Stack is full! Cannot push %d\n", value);
return;
}
s->items[++(s->top)] = value;
}
// 弹栈操作
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty! Cannot pop\n");
return -1;
}
return s->items[(s->top)--];
}
// 获取栈顶元素
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->items[s->top];
}
完整示例：使用数组实现栈
int main() {
struct Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("Top element: %d\n", peek(&s));
printf("Pop element: %d\n", pop(&s));
printf("Pop element: %d\n", pop(&s));
if (isEmpty(&s)) {
printf("Stack is empty\n");
}
return 0;
}
2.3 栈的链表实现
栈也可以使用链表来实现，这样可以避免固定大小的限制，使栈的大小动态可变。
链表节点的定义
struct Node {
int data;
struct Node* next;
};
栈操作
// 初始化链表栈
void initStack(struct Node** top) {
*top = NULL;
}
// 压栈操作
void push(struct Node** top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = *top;
*top = newNode;
}
// 弹栈操作
int pop(struct Node** top) {
if (*top == NULL) {
printf("Stack is empty! Cannot pop\n");
return -1;
}
struct Node* temp = *top;
int poppedValue = temp->data;
*top = temp->next;
free(temp);
return poppedValue;
}
// 获取栈顶元素
int peek(struct Node* top) {
if (top == NULL) {
printf("Stack is empty!\n");
return -1;
}
return top->data;
}
完整示例：使用链表实现栈
int main() {
struct Node* stack = NULL;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("Top element: %d\n", peek(stack));
printf("Pop element: %d\n", pop(&stack));
printf("Pop element: %d\n", pop(&stack));
if (stack == NULL) {
printf("Stack is empty\n");
}
return 0;
}
第3节：队列（Queue）
3.1 队列的基本概念
队列（Queue）是一种**先进先出（FIFO）**的数据结构，广泛应用于任务调度、操作系统的进程管理、广度优先搜索等场景。
队列的操作主要包括：
enqueue：将元素加入队列的末尾。dequeue：将元素从队列的开头移出。
3.2 队列的数组实现
队列的基本结构
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// 定义队列结构
struct Queue {
int items[MAX]; // 用数组存储队列元素
int front, rear; // 队列的头指针和尾指针
};
// 初始化队列
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}
// 检查队列是否为空
int isEmpty(struct Queue* q) {
return q->front == -1;
}
// 检查队列是否已满
int isFull(struct Queue* q) {
return q->rear == MAX - 1;
}
// 入队操作
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("Queue is full! Cannot enqueue %d\n", value);
return;
}
if (isEmpty(q)) {
q->front = 0; // 第一个元素插入时，更新 front
}
q->items[++(q->rear)] = value;
}
// 出队操作
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty! Cannot dequeue\n");
return -1;
}
int value = q->items[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1; // 队列为空时，重置指针
} else {
q->front++;
}
return value;
}
完整示例：使用数组实现队列
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Dequeue element: %d\n", dequeue(&q));
printf("Dequeue element: %d\n", dequeue(&q));
if (isEmpty(&q)) {
printf("Queue is empty\n");
}
return 0;
}
3.3 队列的链表实现
类似于栈，队列也可以用链表来实现。链表实现的队列在需要动态增长的场景中非常适合。
队列节点的定义
struct Node {
int data;
struct Node* next;
};
队列操作
struct Queue {
struct Node front, rear;
};
// 初始化队列
void initQueue(struct Queue* q) {
q->front = q->rear = NULL;
}
// 入队操作
void enqueue(struct Queue* q, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
// 出队操作
int dequeue(struct Queue* q) {
if (q->front == NULL) {
printf("Queue is empty! Cannot dequeue\n");
return -1;
}
struct Node* temp = q->front;
int dequeuedValue = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return dequeuedValue;
}
完整示例：使用链表实现队列
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Dequeue element: %d\n", dequeue(&q));
printf("Dequeue element: %d\n", dequeue(&q));
if (q.front == NULL) {
printf("Queue is empty\n");
}
return 0;
}
练习题
最小栈：设计一个支持 push、
pop和 getMin 操作的栈，getMin应返回栈中的最小值，时间复杂度应为 O(1)。中缀表达式求值：使用栈实现中缀表达式的求值。
环形队列：实现一个环形队列，支持循环利用空间。
双端队列（Deque）：实现一个双端队列，可以从两端插入和删除元素。
队列的栈实现：使用两个栈实现一个队列，支持 enqueue 和 dequeue 操作。
完成这些练习后，你将对栈和队列的数据结构有深入理解。接下来，我们可以继续学习其他数据结构，如树和图。