在计算机程序设计中，栈（Stack）与队列（Queue）是两种最基础且极其重要的线性数据结构。它们以简单却高效的存取机制，在各种算法和系统设计中扮演着核心角色。本文将深入探讨这两种数据结构的概念、特性，并通过C语言实现其基本操作，同时列举常见的应用场景。

一、栈数据结构

栈是一种遵循"后进先出"（Last-In, First-Out, LIFO）原则的数据结构。可以将其想象成一个只能从顶部放入或取出物品的容器。最后放入的物品总是第一个被取出。

1.1 栈的特性

• LIFO原则： 新加入的元素位于栈顶，最先加入的元素位于栈底。
• 限定操作： 主要操作包括入栈（Push，将元素添加到栈顶）和出栈（Pop，从栈顶移除元素），以及查看栈顶元素（Peek）。

1.2 C语言实现栈

我们将使用动态数组来模拟栈的行为。首先定义栈的结构体，并实现其基本操作：

#include <stdlib.h> // For malloc, free
#include <stdio.h>  // For printf, fprintf
#include <limits.h> // For INT_MIN

// 定义一个整数栈结构体
typedef struct {
    int* elements; // 存储数据的数组指针
    int capacity;  // 栈的最大容量
    int count;     // 当前栈中元素数量
} IntStack;

/**
 * @brief 初始化一个新栈
 * @param max_capacity 栈的最大容量
 * @return 成功返回IntStack指针，失败返回NULL
 */
IntStack* initializeStack(int max_capacity) {
    IntStack* s = (IntStack*)malloc(sizeof(IntStack));
    if (!s) {
        fprintf(stderr, "错误：栈结构内存分配失败！\n");
        return NULL;
    }
    s->capacity = max_capacity;
    s->count = 0; // 初始时栈为空
    s->elements = (int*)malloc(max_capacity * sizeof(int));
    if (!s->elements) {
        fprintf(stderr, "错误：栈数组内存分配失败！\n");
        free(s);
        return NULL;
    }
    printf("已创建一个容量为 %d 的栈。\n", max_capacity);
    return s;
}

/**
 * @brief 释放栈占用的内存
 * @param s 要销毁的栈指针
 */
void destroyStack(IntStack* s) {
    if (s) {
        free(s->elements); // 释放元素数组内存
        free(s);           // 释放栈结构体内存
        printf("栈已销毁。\n");
    }
}

/**
 * @brief 检查栈是否为空
 * @param s 栈指针
 * @return 栈为空返回1，否则返回0
 */
int isStackEmpty(IntStack* s) {
    return (s == NULL || s->count == 0);
}

/**
 * @brief 检查栈是否已满
 * @param s 栈指针
 * @return 栈已满返回1，否则返回0
 */
int isStackFull(IntStack* s) {
    return (s != NULL && s->count == s->capacity);
}

/**
 * @brief 将元素压入栈顶
 * @param s 栈指针
 * @param value 要压入的整数值
 */
void pushElement(IntStack* s, int value) {
    if (isStackFull(s)) {
        printf("错误：栈已满，无法压入元素 %d。\n", value);
        return;
    }
    s->elements[s->count++] = value;
    printf("已压入元素：%d\n", value);
}

/**
 * @brief 从栈顶弹出元素
 * @param s 栈指针
 * @return 弹出的元素值，若栈为空则返回INT_MIN
 */
int popElement(IntStack* s) {
    if (isStackEmpty(s)) {
        printf("错误：栈为空，无法弹出元素。\n");
        return INT_MIN; // 返回一个哨兵值表示错误
    }
    int popped_val = s->elements[--s->count];
    printf("已弹出元素：%d\n", popped_val);
    return popped_val;
}

/**
 * @brief 获取栈顶元素（不弹出）
 * @param s 栈指针
 * @return 栈顶元素值，若栈为空则返回INT_MIN
 */
int getTopElement(IntStack* s) {
    if (isStackEmpty(s)) {
        printf("错误：栈为空，无栈顶元素。\n");
        return INT_MIN;
    }
    return s->elements[s->count - 1];
}

1.3 栈的应用示例

• 函数调用管理： 操作系统使用栈来管理函数调用，保存局部变量和返回地址，实现函数的嵌套调用。
• 表达式求值： 例如，将中缀表达式转换为后缀表达式，以及对后缀表达式进行求值运算。
• 文本编辑器的撤销/重做功能： 每一步操作都可以压入栈中，撤销时弹出最近的操作。
• 深度优先搜索（DFS）： 递归实现的DFS底层即是利用了系统栈，非递归实现则需要显式使用栈来辅助遍历图或树。

二、队列数据结构

队列是一种遵循"先进先出"（First-In, First-Out, FIFO）原则的数据结构。它类似于日常生活中排队的情景，最先进入队伍的人最先离开。

2.1 队列的特性

• FIFO原则： 新加入的元素位于队尾，最先加入的元素位于队首。
• 限定操作： 主要操作包括入队（Enqueue，将元素添加到队尾）和出队（Dequeue，从队首移除元素），以及查看队首元素（Peek）。

2.2 C语言实现队列

为了更高效地利用空间，我们将采用循环数组（Circular Array）的方式实现队列，避免出队操作后大量元素的移动，提高空间利用率。

#include <stdlib.h> // For malloc, free
#include <stdio.h>  // For printf, fprintf
#include <limits.h> // For INT_MIN

// 定义一个循环整数队列结构体
typedef struct {
    int* storage;   // 存储元素的数组
    int capacity;   // 队列的最大容量
    int head_idx;   // 队首元素索引
    int tail_idx;   // 队尾插入位置索引（指向下一个空闲位置）
    int current_size; // 当前队列中元素数量
} CircularQueue;

/**
 * @brief 初始化一个循环队列
 * @param max_len 队列的最大容量
 * @return 成功返回CircularQueue指针，失败返回NULL
 */
CircularQueue* create_circular_queue(int max_len) {
    CircularQueue* q = (CircularQueue*)malloc(sizeof(CircularQueue));
    if (!q) {
        fprintf(stderr, "错误：队列结构内存分配失败！\n");
        return NULL;
    }
    q->capacity = max_len;
    q->head_idx = 0;
    q->tail_idx = 0; // head_idx == tail_idx 且 current_size == 0 表示空队列
    q->current_size = 0;
    q->storage = (int*)malloc(max_len * sizeof(int));
    if (!q->storage) {
        fprintf(stderr, "错误：队列数据内存分配失败！\n");
        free(q);
        return NULL;
    }
    printf("已创建一个容量为 %d 的队列。\n", max_len);
    return q;
}

/**
 * @brief 释放队列占用的内存
 * @param q 要销毁的队列指针
 */
void destroy_circular_queue(CircularQueue* q) {
    if (q) {
        free(q->storage); // 释放元素数组内存
        free(q);          // 释放队列结构体内存
        printf("队列已销毁。\n");
    }
}

/**
 * @brief 检查队列是否为空
 * @param q 队列指针
 * @return 队列为空返回1，否则返回0
 */
int isQueueEmpty(CircularQueue* q) {
    return (q == NULL || q->current_size == 0);
}

/**
 * @brief 检查队列是否已满
 * @param q 队列指针
 * @return 队列已满返回1，否则返回0
 */
int isQueueFull(CircularQueue* q) {
    return (q != NULL && q->current_size == q->capacity);
}

/**
 * @brief 入队操作：将元素添加到队尾
 * @param q 队列指针
 * @param val 要入队的整数值
 */
void enqueue_item(CircularQueue* q, int val) {
    if (isQueueFull(q)) {
        printf("错误：队列已满，无法入队元素 %d。\n", val);
        return;
    }
    q->storage[q->tail_idx] = val;
    q->tail_idx = (q->tail_idx + 1) % q->capacity; // 循环更新队尾索引
    q->current_size++;
    printf("已将元素 %d 入队。\n", val);
}

/**
 * @brief 出队操作：从队首移除元素
 * @param q 队列指针
 * @return 出队的元素值，若队列为空则返回INT_MIN
 */
int dequeue_item(CircularQueue* q) {
    if (isQueueEmpty(q)) {
        printf("错误：队列为空，无法出队。\n");
        return INT_MIN;
    }
    int item = q->storage[q->head_idx];
    q->head_idx = (q->head_idx + 1) % q->capacity; // 循环更新队首索引
    q->current_size--;
    printf("已将元素 %d 出队。\n", item);
    return item;
}

/**
 * @brief 查看队首元素（不移除）
 * @param q 队列指针
 * @return 队首元素值，若队列为空则返回INT_MIN
 */
int peek_front(CircularQueue* q) {
    if (isQueueEmpty(q)) {
        printf("错误：队列为空，无队首元素。\n");
        return INT_MIN;
    }
    return q->storage[q->head_idx];
}

2.3 队列的应用示例

• 任务调度： 操作系统中的进程调度、打印机任务队列、消息队列等，确保任务按顺序执行。
• 广度优先搜索（BFS）： 用于图或树的遍历，按层级依次访问节点，是实现BFS算法的核心。
• 缓存机制： 例如，在实现最近最少使用（LRU）缓存策略时，队列可以辅助管理缓存项的访问顺序。
• 生产者-消费者问题： 队列作为缓冲区，协调生产者和消费者之间的数据交换，解耦两者关系。

栈和队列作为数据结构的基础，其简洁高效的设计思想贯穿于计算机科学的方方面面。掌握它们不仅能帮助我们更好地理解程序的运行机制，也为解决实际问题提供了强有力的工具。