【初探数据结构】线性表——栈与队列（代码实现与详解）

我想吃余

发布于 2025-03-31 16:30:30

4100

代码可运行

文章被收录于专栏：用户11403055的专栏（2）用户11403055的专栏（2）C语言学习

运行总次数：0

代码可运行

引言

栈（Stack）和队列（Queue）是计算机科学中最基础且重要的数据结构。它们分别遵循**后进先出（LIFO）和先进先出（FIFO）**的原则，广泛应用于算法设计、系统底层实现（如函数调用栈）、任务调度等场景。本文将从概念、实现到常见面试题，带你全面掌握这两种数据结构。

一、栈（Stack）

1. 概念与特性

定义：栈是一种只允许在**固定一端（栈顶）**进行插入（压栈）和删除（出栈）操作的线性表。
核心原则：后进先出（LIFO）。类比生活中的叠盘子，最后放上去的盘子会被最先拿走。
操作：
- 压栈（Push）：在栈顶插入元素。
- 出栈（Pop）：删除栈顶元素。
- 获取栈顶元素（Top）：查看但不删除栈顶元素。

2. 实现方式

一、栈结构设计

动态栈通过动态数组实现，包含以下核心结构：

#define INICAPA 4  // 初始容量

typedef struct Stack {
    STDataType* a;      // 动态数组
    int top;            // 栈顶指针（指向下一个待插入位置）
    int capacity;       // 当前容量
} ST;

a：动态数组，存储栈元素。
top：栈顶指针，表示栈中元素个数，也指向下一个插入位置。
capacity：数组当前容量，支持动态扩容。

二、核心函数实现解析

1. 初始化栈

void STInit(ST* stack) {
    assert(stack);
    stack->a = (STDataType*)malloc(sizeof(STDataType) * INICAPA);
    if (stack->a == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    stack->capacity = INICAPA;
    stack->top = 0;  // 初始时栈空
}

功能：分配初始容量（4）的数组，初始化栈顶指针。
注意：
- 使用 assert 确保传入指针非空。
- 内存分配失败时直接终止程序。

2. 压栈操作（动态扩容）

void STPush(ST* stack, STDataType x) {
    assert(stack);
    // 栈满时扩容至2倍
    if (stack->top == stack->capacity) {
        STDataType* tmp = (STDataType*)realloc(
            stack->a, 
            sizeof(STDataType) * stack->capacity * 2
        );
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        stack->a = tmp;
        stack->capacity *= 2;
    }
    // 插入数据并更新栈顶
    stack->a[stack->top] = x;
    stack->top++;
}

步骤：
1. 检查栈是否已满（top == capacity）。
2. 若满，通过 realloc 扩容至原容量的2倍。
3. 插入新元素到 top 位置，并递增栈顶指针。
关键点：
- 扩容策略为翻倍，均摊时间复杂度为 (O(1))。
- 扩容失败时直接终止程序。

3. 出栈操作

void STPop(ST* stack) {
    assert(stack);
    assert(!STEmpty(stack));  // 栈不能为空
    stack->top--;
}

逻辑：仅需将 top 减1，无需实际删除数据。
注意：必须确保栈非空，否则触发断言。

4. 获取栈顶元素

STDataType STTop(ST* stack) {
    assert(stack && !STEmpty(stack));
    return stack->a[stack->top - 1];
}

关键：通过 top-1 访问当前栈顶元素。

5. 销毁栈

void STDestroy(ST* stack) {
    assert(stack);
    free(stack->a);     // 释放动态数组
    stack->a = NULL;    // 避免野指针
    stack->top = 0;
    stack->capacity = 0;
}

作用：释放内存并重置状态。
易错点：忘记将 a 置为 NULL 可能导致后续误用。

6. 辅助函数

// 判空
bool STEmpty(ST* stack) {
    assert(stack);
    return stack->top == 0;
}

// 获取栈大小
int STSize(ST* stack) {
    assert(stack);
    return stack->top;
}

三、关键问题与优化

1. 为什么选择动态数组而非链表？

优势：
- 内存连续，缓存友好。
- 压栈/出栈操作的时间复杂度为 (O(1))（均摊后）。
劣势：扩容时需要复制数据，但通过翻倍扩容策略可优化均摊成本。

2. `top` 指针的设计

指向下一个空闲位置：例如，top=3 表示栈中有3个元素（索引0~2），新元素插入索引3。
简化逻辑：top 直接表示元素个数，无需额外维护大小字段。

3. 动态扩容的细节

翻倍策略：容量从4→8→16→32…，均摊每次插入操作的时间复杂度为 (O(1))。
内存释放：销毁时必须调用 STDestroy，否则导致内存泄漏。

二、队列（Queue）

1. 概念与特性

定义：队列是一种允许在队尾插入、队头删除的线性表。
核心原则：先进先出（FIFO）。类比排队购票，先到的人先买到票。
操作：
- 入队（Enqueue）：在队尾插入元素。
- 出队（Dequeue）：删除队头元素。
- 获取队头元素（Front）：查看但不删除队头元素。

2. 实现方式

一、队列结构设计

队列通过链表实现，包含以下核心结构：

// 队列节点
typedef struct QListNode {
    struct QListNode* next;  // 指向下一节点
    QDataType data;          // 节点数据
} QNode;

// 队列管理结构
typedef struct Queue {
    QNode* head;    // 队头指针
    QNode* tail;    // 队尾指针
    int size;       // 队列元素个数
} Queue;

head：指向链表的第一个节点（队头），用于出队操作。
tail：指向链表的最后一个节点（队尾），用于入队操作。
size：记录队列长度，避免遍历链表统计元素。

二、核心函数实现解析

1. 初始化队列

void QueueInit(Queue* q) {
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

功能：将队列的头尾指针置空，size 设为0。
注意：需使用 assert 确保传入的队列指针非空。

2. 入队操作

void QueuePush(Queue* q, QDataType data) {
    assert(q);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    newnode->next = NULL;
    newnode->data = data;

    if (q->tail == NULL) {  // 队列为空
        q->tail = q->head = newnode;
    } else {                // 队列非空
        q->tail->next = newnode;
        q->tail = newnode;
    }
    q->size++;
}

步骤：
1. 创建新节点并初始化数据。
2. 若队列为空，头尾指针均指向新节点。
3. 若队列非空，将新节点链接到链表尾部，并更新尾指针。
关键点：
- 处理队列为空的边界条件。
- 内存分配失败时需报错退出。

3. 出队操作

void QueuePop(Queue* q) {
    assert(q);
    assert(!QueueEmpty(q));

    if (q->head->next == NULL) {  // 队列仅剩一个节点
        free(q->head);
        q->head = q->tail = NULL;
    } else {                     // 队列有多个节点
        QNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
    q->size--;
}

步骤：
1. 检查队列是否为空（通过 QueueEmpty）。
2. 若队列只剩一个节点，释放后需将头尾指针均置空。
3. 若有多个节点，删除头节点并更新头指针。
关键点：
- 必须处理队列只剩一个节点的特殊情况，避免悬空指针。
- 出队后需同步更新 size。

4. 获取队头和队尾元素

QDataType QueueFront(Queue* q) {
    assert(q && !QueueEmpty(q));
    return q->head->data;
}

QDataType QueueBack(Queue* q) {
    assert(q && !QueueEmpty(q));
    return q->tail->data;
}

注意：需确保队列非空，否则断言触发。

5. 队列销毁

void QueueDestroy(Queue* q) {
    assert(q);
    QNode* cur = q->head;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->tail = q->head = NULL;
    q->size = 0;
}

步骤：遍历链表释放所有节点内存，重置头尾指针和 size。
易错点：未释放全部节点导致内存泄漏。

三、关键问题与优化

1. 为什么用链表实现队列？

优势：出队时无需移动数据，时间复杂度为 (O(1))。
若用数组实现，出队需整体前移元素，效率低。

2. `size` 字段的作用

直接通过 q->size 获取队列长度，避免遍历链表（(O(1)) 时间复杂度）。
在判空时直接检查 size == 0，提升效率。

3. 边界条件处理

入队：队列为空时需同时更新头尾指针。
出队：队列只剩一个节点时需重置头尾指针。

结语

栈和队列是算法设计的基石，理解其原理和实现是程序员的基本功。建议通过实际编码练习（如实现动态栈、循环队列）加深理解，并多刷相关面试题提升应用能力。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-31，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

【初探数据结构】线性表——栈与队列（代码实现与详解）

【初探数据结构】线性表——栈与队列（代码实现与详解）

引言

一、栈（Stack）

1. 概念与特性

2. 实现方式

一、栈结构设计

二、核心函数实现解析

1. 初始化栈

2. 压栈操作（动态扩容）

3. 出栈操作

4. 获取栈顶元素

5. 销毁栈

6. 辅助函数

三、关键问题与优化

1. 为什么选择动态数组而非链表？

2. top 指针的设计

3. 动态扩容的细节

二、队列（Queue）

1. 概念与特性

2. 实现方式

一、队列结构设计

二、核心函数实现解析

1. 初始化队列

2. 入队操作

3. 出队操作

4. 获取队头和队尾元素

5. 队列销毁

三、关键问题与优化

1. 为什么用链表实现队列？

2. size 字段的作用

3. 边界条件处理

结语

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

2. `top` 指针的设计

2. `size` 字段的作用