数据结构：栈与队列的底层实现

实现文件 stack.c

#include "stack.h"

// 初始化栈
void STInit(ST* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

// 销毁栈
void STDestroy(ST* ps) {
    assert(ps);
    if (ps->arr) {
        free(ps->arr);
        ps->arr = NULL;
    }
    ps->capacity = 0;
    ps->top = 0;
}

// 入栈 (核心逻辑：动态扩容)
void STPush(ST* ps, STDataType x) {
    assert(ps);
    // 容量检查：满则扩容
    if (ps->top == ps->capacity) {
        // 策略：初始为 4，之后每次翻倍
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc fail.");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

// 出栈
void STPop(ST* ps) {
    assert(ps);
    assert(!STEmpty(ps));
    // 防御性编程：确保栈不为空
    ps->top--;
}

// 取栈顶元素
STDataType STTop(ST* ps) {
    assert(ps);
    assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];
}

// 获取栈中有效元素个数
int STSize(ST* ps) {
    assert(ps);
    return ps->top;
}

// 判断栈是否为空
bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}

1.4 复杂度分析

• 时间复杂度：
  • Push/Pop：均摊 O(1)。虽然扩容涉及 O(N) 拷贝，但触发频率低。
  • Top/Size/Empty：O(1)。
• 空间复杂度：O(N)，取决于存储元素的个数。

队列（Queue）：先进先出的链表实现

2.1 核心概念

队列是**先进先出（FIFO, First In First Out）**的线性表。

• 队头（Head）：删除数据的一端。
• 队尾（Tail）：插入数据的一端。

2.2 选型思考：为什么用链表？

与栈不同，队列的实现我选择了链表，原因如下：

1. 队头删除效率：若用数组，队头删除需移动所有元素（O(N)）；链表头删只需修改指针（O(1)）。
2. 避免假溢出：链表动态分配节点，无需预先估计大小。

2.3 代码实现与优化点

头文件 Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int QDataType;
typedef struct QueueNode {
    QDataType data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* phead; // 队头
    QueueNode* ptail; // 队尾
    // 优化建议：建议添加 int size; 成员变量，避免每次遍历计算大小
} Queue;

// 接口声明
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

实现文件 Queue.c

#include "Queue.h"

// 初始化
void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptail = NULL;
}

// 入队 (队尾插入)
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->phead == NULL) {
        // 队列为空，头尾都指向新节点
        pq->phead = pq->ptail = newnode;
    } else {
        // 队列非空，链接到尾部并更新尾指针
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
}

// 出队 (队头删除)
void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    // 关键逻辑：若只有一个节点，删除后需将尾指针也置空
    if (pq->phead == pq->ptail) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else {
        QueueNode* nextnode = pq->phead->next;
        free(pq->phead);
        pq->phead = nextnode;
    }
}

// 获取队列大小 (当前实现为 O(N))
int QueueSize(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    int size = 0;
    while (pcur) {
        ++size;
        pcur = pcur->next;
    }
    return size;
}

// 销毁队列 (遍历释放)
void QueueDestroy(Queue* pq) {
    assert(pq);
    QueueNode* pcur = pq->phead;
    while (pcur) {
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
}

// 其他辅助函数 (Front, Back, Empty) 略，逻辑类似栈
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL;
}

QDataType QueueFront(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}

QDataType QueueBack(Queue* pq) {
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}

2.4 代码复盘与优化

在编写 QueueSize 函数时，我采用了遍历链表的方式，时间复杂度为 O(N)。

• 问题：如果频繁调用 QueueSize，效率较低。
• 优化方案：参考讲义中的结构定义，可以在 Queue 结构体中增加一个 int size; 成员变量。
  • Push 时 size++
  • Pop 时 size--
  • QueueSize 直接返回 size，复杂度降为 O(1)。
• 空间换时间：虽然多占 4 个字节，但换取了查询效率的提升，这在工程实践中通常是值得的。

进阶：循环队列 (Circular Queue)

为了克服数组队列的'假溢出'问题，我们引入循环队列。

• 结构：逻辑上首尾相连，物理上仍用数组。
• 判空：front == rear
• 判满：(rear + 1) % capacity == front
• 思考：为什么队满时 rear 不存数据？
  • 答：为了区分'队空'和'队满'。如果不浪费一个空间，当 front == rear 时无法判断是空还是满。牺牲一个单元是经典的工程设计权衡。

Debug 记录与工程规范反思

在编写测试代码的过程中，我遇到了一些典型问题，记录在此以免再犯：

1. 头文件包含规范：
   • ❌ 错误：#include "stack.c"
   • ✅ 正确：#include "stack.h"
   • 反思：在 .c 文件中包含另一个 .c 文件会导致符号重复定义（Linker Error）。应该只包含头文件，编译时将所有 .c 文件一起编译。
2. 大小写敏感：
   • ❌ 错误：调用 STpop(&st)
   • ✅ 正确：调用 STPop(&st)
   • 反思：C 语言区分大小写，命名风格应统一（推荐大驼峰或小驼峰）。
3. 内存安全：
   • 在 QueuePop 中，如果队列只有一个节点，删除头节点后，必须同时将 ptail 置为 NULL，否则尾指针会成为野指针，导致后续 Push 出错。

总结

本章通过手写实现，我深刻体会到了：

1. 结构选型的重要性：栈选数组（尾操多），队列选链表（头删多）。
2. 边界条件处理：空栈/空队列的判断、单节点队列的删除、动态扩容的逻辑。
3. 工程规范：头文件分离、内存管理、命名规范。