文章/答案/技术大牛

发布

社区首页 >专栏 >【初探数据结构】线性表——栈与队列（代码实现与详解）

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

我想吃余

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

17500

代码可运行

文章被收录于专栏：数据结构初阶数据结构初阶 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;
}