17 数据结构与算法之栈与队列

在上一章中，我们讨论了数组与链表，它们是最基本的数据存储结构。接下来，我们将深入探讨两个非常重要的数据结构：栈 和 队列。这两个数据结构常用于管理数据的访问顺序，为算法提供支持，尤其是在解决递归、深度优先搜索和广度优先搜索等问题时表现尤为突出。

5.2.1 栈（Stack）

栈是一种后进先出（LIFO, Last In First Out）数据结构。它的基本操作包括：

• push：将一个元素压入栈顶
• pop：从栈顶移除一个元素
• top 或 peek：返回栈顶元素但不移除它
• isEmpty：检查栈是否为空

栈的实现

在C语言中，我们可以使用数组或链表来实现栈。下面是使用数组的简单实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct Stack {
    int top;
    int items[MAX_SIZE];
} Stack;

void init(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int item) {
    if (isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->items[++(s->top)] = item;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1; // 可以使用其他错误码表示栈空
    }
    return s->items[(s->top)--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is Empty!\n");
        return -1;
    }
    return s->items[s->top];
}

栈的应用

1. 括号匹配：用于检查字符串中的括号是否匹配。
2. 深度优先搜索（DFS）：在图或树的遍历中。
3. 函数调用管理：编程语言中函数调用的管理经常依赖于栈。

示例：括号匹配

下面是一个简单的示例，使用栈来检查输入字符串中的括号是否匹配。

#include <stdbool.h>

bool isMatching(char opening, char closing) {
    return (opening == '(' && closing == ')') ||
           (opening == '{' && closing == '}') ||
           (opening == '[' && closing == ']');
}

bool isBalanced(const char *expr) {
    Stack s;
    init(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char current = expr[i];
        if (current == '(' || current == '{' || current == '[') {
            push(&s, current);
        } else if (current == ')' || current == '}' || current == ']') {
            if (isEmpty(&s) || !isMatching(pop(&s), current)) {
                return false; // 不匹配
            }
        }
    }
    return isEmpty(&s); // 栈空则匹配，返回真
}

5.2.2 队列（Queue）

与栈相对，队列是一种先进先出（FIFO, First In First Out）数据结构。基本操作包括：

• enqueue：在队列末尾添加一个元素
• dequeue：从队列头部移除一个元素
• front：返回队列头元素但不移除它
• isEmpty：检查队列是否为空

队列的实现

我们同样可以用数组或链表实现队列。以下是使用链表的简单实现：

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front;
    Node *rear;
} Queue;

void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

int isQueueEmpty(Queue *q) {
    return q->front == NULL;
}

void enqueue(Queue *q, int item) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = item;
    newNode->next = NULL;
    
    if (q->rear) {
        q->rear->next = newNode;
    } else {
        q->front = newNode; // 队列为空时，front指向新节点
    }
    q->rear = newNode; // 更新rear指向新节点
}

int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is Empty!\n");
        return -1; // 可以使用其他错误码表示队列空
    }
    Node *temp = q->front;
    int item = temp->data;
    q->front = q->front->next;
    
    if (q->front == NULL) {
        q->rear = NULL; // 队列为空时重置rear
    }
    
    free(temp);
    return item;
}

队列的应用

1. 任务调度：在操作系统中用于管理正在执行的任务。
2. 广度优先搜索（BFS）：在图或树的遍历中。
3. 缓冲区管理：用于数据流的缓冲区如打印队列。

示例：任务调度模拟

下面是一个简单的队列使用示例，用于模拟简单的任务调度。

#include <stdio.h>

void simulateTaskQueue() {
    Queue taskQueue;
    initQueue(&taskQueue);

    // 添加任务
    enqueue(&taskQueue, 1);
    enqueue(&taskQueue, 2);
    enqueue(&taskQueue, 3);
    
    // 处理任务
    while (!isQueueEmpty(&taskQueue)) {
        int task = dequeue(&taskQueue);
        printf("Processing task %d\n", task);
    }
}

总结

在本节中，我们探讨了 栈 和 队列 的基本概念、实现及其应用。理解这两种数据结构不仅有助于编写高效的代码，还能在处理复杂问题时提供更清晰的思路。接下来，我们将在下一篇中学习更复杂的数据结构：树 和 图，它们在许多实际应用中扮演着关键角色。