数据结构：栈与队列的底层实现 | 极客日志

C算法

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

详细阐述了栈与队列两种核心数据结构的底层实现原理。栈基于动态数组，利用 LIFO 特性，通过翻倍扩容策略平衡时间与空间复杂度；队列基于链表，利用 FIFO 特性优化队头删除效率，并探讨了循环队列解决假溢出的方案。此外，文章总结了工程实践中的关键规范，包括头文件分离、内存安全管理及命名一致性，为数据结构学习提供扎实的代码参考。

RedisGeek发布于 2026/3/30更新于 2026/4/131 浏览

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

栈（Stack）：后进先出的动态数组实现

1.1 核心概念

栈是一种**后进先出（LIFO, Last In First Out）**的线性表。

栈顶（Top）：唯一允许插入和删除的一端。
栈底（Bottom）：固定的一端。
操作：入栈（Push）、出栈（Pop）。

1.2 选型思考：为什么用数组？

虽然栈可以用链表实现，但我在实现时选择了动态数组，原因如下：

操作集中：栈的操作只在尾部进行，数组尾插/尾删复杂度为 O(1)，无需移动元素。
缓存友好：数组内存连续，CPU 缓存命中率更高。
空间效率：不需要像链表那样为每个元素存储额外的指针域。

1.3 代码实现与规范

在编写代码时，我将接口定义（.h）与具体实现（.c）分离，这是 C 语言工程化的基本规范。

头文件 stack.h

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

typedef int STDataType;
typedef struct Stack {
    STDataType* arr; // 指向动态数组的指针
    int top;         // 栈顶指针（指向下一个可用位置，兼作大小）
    int capacity;    // 当前容量
} ST;

// 接口声明
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
 ;
STDataType ;
 ;
 ;

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#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;
}

#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);

#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;
}