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

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

引言

栈（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. 边界条件处理

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

结语

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