要上进的柯同学1. 栈与队列的本质区别
在计算机科学中，栈和队列是最基础的两种线性数据结构，它们的核心区别在于数据元素的存取顺序。栈遵循LIFO（Last In First Out，后进先出）原则，而队列遵循FIFO（First In First Out，先进先出）原则。
栈就像我们日常生活中叠放的盘子：你只能从最上面取放盘子，最后放上去的盘子总是最先被取走。这种特性使得栈特别适合需要"回退"操作的场景，比如：
- 函数调用时的调用栈
- 浏览器的后退功能
- 文本编辑器的撤销操作
队列则更像是排队买票的队伍：新来的人排在队尾，最早来的人站在队首，服务也是从队首开始。这种特性使得队列天然适合处理需要按顺序执行的任务，比如：
- 打印机的任务队列
- 消息队列系统
- 多线程编程中的任务调度
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 栈的数组实现详解
2.1 数据结构设计
我们用动态数组来实现栈，这种实现方式在大多数情况下性能更好，因为数组的内存是连续的，CPU缓存命中率高。栈的结构体设计如下：
c复制typedef int StackDataType;
typedef struct Stack {
StackDataType* array; // 动态数组
size_t top; // 栈顶指针（指向下一个空闲位置）
size_t capacity; // 数组容量
} Stack;
这里有几个关键设计点：
- 使用动态数组而非固定大小数组，可以避免栈溢出问题
- top指针指向的是下一个可插入位置，而非当前栈顶元素
- capacity记录当前分配的数组大小，当空间不足时进行扩容
2.2 核心操作实现
初始化与销毁
c复制void StackInit(Stack* ps) {
assert(ps);
ps->array = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestroy(Stack* ps) {
assert(ps);
free(ps->array);
ps->array = NULL;
ps->top = ps->capacity = 0;
}
入栈操作
c复制void StackPush(Stack* ps, StackDataType x) {
assert(ps);
// 检查并扩容
if (ps->top == ps->capacity) {
size_t newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
StackDataType* tmp = realloc(ps->array, newCapacity * sizeof(StackDataType));
if (!tmp) {
perror("realloc failed");
exit(EXIT_FAILURE);
}
ps->array = tmp;
ps->capacity = newCapacity;
}
// 插入元素
ps->array[ps->top++] = x;
}
这里采用了常见的倍增扩容策略，初始容量为4，每次空间不足时将容量翻倍。这种策略可以保证多次插入的均摊时间复杂度为O(1)。
出栈操作
c复制void StackPop(Stack* ps) {
assert(ps);
assert(!StackEmpty(ps)); // 栈不为空
ps->top--;
}
其他辅助操作
c复制StackDataType StackTop(const Stack* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->array[ps->top - 1];
}
bool StackEmpty(const Stack* ps) {
assert(ps);
return ps->top == 0;
}
size_t StackSize(const Stack* ps) {
assert(ps);
return ps->top;
}
2.3 实际应用：非递归快速排序
栈的一个经典应用是将递归算法改为非递归实现。以快速排序为例：
c复制void QuickSortNonR(int* arr, int left, int right) {
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st)) {
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = PartSort(arr, begin, end);
// 右子序列入栈
if (keyi + 1 < end) {
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
// 左子序列入栈
if (keyi - 1 > begin) {
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
这个实现中，我们手动用栈来保存待处理的子数组范围，模拟了系统调用栈的行为。相比递归版本，非递归实现可以避免栈溢出风险，特别适合处理大规模数据。
3. 队列的链表实现详解
3.1 数据结构设计
队列的链表实现比数组实现更灵活，因为出队操作不需要移动元素。我们采用带头尾指针的结构：
c复制typedef int QueueDataType;
typedef struct QueueNode {
QueueDataType data;
struct QueueNode* next;
} QueueNode;
typedef struct Queue {
QueueNode* head;
QueueNode* tail;
size_t size;
} Queue;
这种设计的关键点：
- 单独维护头尾指针，避免每次入队都要遍历整个链表
- 记录队列大小，可以快速获取元素数量
- 每个节点动态分配内存，没有容量限制
3.2 核心操作实现
初始化与销毁
c复制void QueueInit(Queue* pq) {
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq) {
assert(pq);
QueueNode* cur = pq->head;
while (cur) {
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
入队操作
c复制void QueuePush(Queue* pq, QueueDataType x) {
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (!newNode) {
perror("malloc failed");
exit(EXIT_FAILURE);
}
newNode->data = x;
newNode->next = NULL;
if (pq->tail == NULL) {
// 空队列
pq->head = pq->tail = newNode;
} else {
// 非空队列
pq->tail->next = newNode;
pq->tail = newNode;
}
pq->size++;
}
出队操作
c复制void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL) {
// 队列已空
pq->tail = NULL;
}
pq->size--;
}
其他辅助操作
c复制QueueDataType QueueFront(const Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QueueDataType QueueBack(const Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(const Queue* pq) {
assert(pq);
return pq->size == 0;
}
size_t QueueSize(const Queue* pq) {
assert(pq);
return pq->size;
}
3.3 实际应用：生产者-消费者模型
队列在多线程编程中的一个重要应用是实现生产者-消费者模型：
c复制typedef struct {
Queue queue;
pthread_mutex_t mutex;
pthread_cond_t cond;
} PCQueue;
void* Producer(void* arg) {
PCQueue* pcq = (PCQueue*)arg;
for (int i = 0; i < 100; ++i) {
pthread_mutex_lock(&pcq->mutex);
QueuePush(&pcq->queue, i);
printf("Produced: %d\n", i);
pthread_cond_signal(&pcq->cond);
pthread_mutex_unlock(&pcq->mutex);
usleep(rand() % 100000);
}
return NULL;
}
void* Consumer(void* arg) {
PCQueue* pcq = (PCQueue*)arg;
for (int i = 0; i < 100; ++i) {
pthread_mutex_lock(&pcq->mutex);
while (QueueEmpty(&pcq->queue)) {
pthread_cond_wait(&pcq->cond, &pcq->mutex);
}
int item = QueueFront(&pcq->queue);
QueuePop(&pcq->queue);
printf("Consumed: %d\n", item);
pthread_mutex_unlock(&pcq->mutex);
usleep(rand() % 100000);
}
return NULL;
}
这个例子中，生产者线程向队列中添加数据，消费者线程从队列中取出数据。当队列为空时，消费者会等待条件变量；当有新数据加入时，生产者会通知等待的消费者。
4. 性能优化与常见问题
4.1 栈的实现选择
数组实现 vs 链表实现：
- 数组实现：
- 优点：内存局部性好，缓存命中率高；实现简单
- 缺点：需要处理扩容问题；最大容量受限
- 链表实现：
- 优点：没有容量限制；不需要扩容
- 缺点：每个操作都需要分配/释放内存；缓存不友好
在实际应用中，除非特别需要，一般优先选择数组实现。在C++的STL中，std::stack默认就是用deque（一种数组结构）实现的。
4.2 队列的实现选择
数组实现（循环队列） vs 链表实现：
- 循环队列：
- 优点：内存连续，缓存友好；不需要频繁内存分配
- 缺点：有最大容量限制；实现稍复杂
- 链表实现：
- 优点：没有容量限制；实现简单
- 缺点：内存不连续；需要频繁内存分配
对于性能要求高的场景，循环队列通常是更好的选择。Linux内核中的kfifo就是一个高性能的循环队列实现。
4.3 常见错误与陷阱
-
栈的数组实现中，top指针的语义要明确。我们实现的top指向的是下一个空闲位置，因此：
- 栈空条件：top == 0
- 栈顶元素位置：top - 1
如果设计为top指向当前栈顶元素，这些条件会有所不同。
-
队列的链表实现中，出队时要特别注意队列变为空的情况，此时需要将tail指针也置为NULL，否则tail会成为一个悬垂指针。
-
在多线程环境下使用队列时，必须做好同步控制。简单的做法是用互斥锁保护整个队列，但这样会影响性能。更高效的实现可以考虑无锁队列。
-
内存管理问题：
- 栈/队列销毁时要释放所有分配的内存
- 扩容时要检查realloc是否成功
- 链表节点出队/出栈后要及时free
4.4 测试用例设计
良好的测试应该覆盖以下场景：
- 空栈/队列的操作
- 单个元素的操作
- 满容量时的操作（对于数组实现）
- 交替的入栈/出栈、入队/出队操作
- 连续大量操作后的状态验证
例如，栈的测试用例可以这样设计：
c复制void TestStack() {
Stack st;
StackInit(&st);
// 测试空栈操作
assert(StackEmpty(&st));
assert(StackSize(&st) == 0);
// 测试单元素操作
StackPush(&st, 1);
assert(!StackEmpty(&st));
assert(StackSize(&st) == 1);
assert(StackTop(&st) == 1);
// 测试多元素操作
for (int i = 2; i <= 100; ++i) {
StackPush(&st, i);
}
assert(StackSize(&st) == 100);
// 测试出栈顺序
for (int i = 100; i >= 1; --i) {
assert(StackTop(&st) == i);
StackPop(&st);
}
assert(StackEmpty(&st));
StackDestroy(&st);
}