栈（Stack）和队列（Queue）是两种基础且广泛应用的线性数据结构。它们都用于存储数据集合，但其主要区别在于元素的存取方式：栈遵循后进先出（LIFO, Last-In, First-Out）原则，而队列遵循先进先出（FIFO, First-In, First-Out）原则。

本教程将介绍如何使用C语言实现栈和队列，包括基于数组的实现和基于链表的实现，并探讨它们的应用场景。

1. 栈 (Stack)

栈就像一叠盘子，你只能在最上面放盘子，也只能从最上面取盘子。

栈的基本操作

• Push：将元素添加到栈顶。
• Pop：从栈顶移除并返回元素。
• Peek/Top：查看栈顶元素但不移除。
• IsEmpty：检查栈是否为空。
• IsFull (对于基于数组的定长栈)：检查栈是否已满。

a. 基于数组的栈实现

使用一个固定大小的数组来存储栈元素，并用一个整数 top 来追踪栈顶位置。

 #include <stdio.h>
 #include <stdlib.h>
 #include <limits.h> // For INT_MIN
 
 #define MAX_STACK_SIZE 100
 
 // 数组栈结构定义
 typedef struct ArrayStack {
     int items[MAX_STACK_SIZE];
     int top; // 指向栈顶元素的索引，-1表示栈空
 } ArrayStack;
 
 // 初始化栈
 ArrayStack* create_array_stack() {
     ArrayStack *stack = (ArrayStack*)malloc(sizeof(ArrayStack));
     if (!stack) {
         perror("Failed to create array stack");
         return NULL;
     }
     stack->top = -1; // 初始化为空栈
     return stack;
 }
 
 // 检查栈是否已满
 int is_array_stack_full(ArrayStack *stack) {
     return stack->top == MAX_STACK_SIZE - 1;
 }
 
 // 检查栈是否为空
 int is_array_stack_empty(ArrayStack *stack) {
     return stack->top == -1;
 }
 
 // Push操作
 void array_stack_push(ArrayStack *stack, int item) {
     if (is_array_stack_full(stack)) {
         printf("Stack Overflow! Cannot push %d.\n", item);
         return;
     }
     stack->items[++(stack->top)] = item;
     // printf("%d pushed to stack.\n", item);
 }
 
 // Pop操作
 int array_stack_pop(ArrayStack *stack) {
     if (is_array_stack_empty(stack)) {
         printf("Stack Underflow! Cannot pop.\n");
         return INT_MIN; // 返回一个错误指示值
     }
     return stack->items[(stack->top)--];
 }
 
 // Peek/Top操作
 int array_stack_peek(ArrayStack *stack) {
     if (is_array_stack_empty(stack)) {
         printf("Stack is empty! Cannot peek.\n");
         return INT_MIN;
     }
     return stack->items[stack->top];
 }
 
 // 释放栈 (对于数组栈，主要是释放结构体本身)
 void free_array_stack(ArrayStack *stack) {
     if (stack) {
         free(stack);
     }
 }
 
 // 数组栈使用示例
 void demo_array_stack() {
     printf("--- Array Stack Demo ---\n");
     ArrayStack *stack = create_array_stack();
     if (!stack) return;
 
     array_stack_push(stack, 10);
     array_stack_push(stack, 20);
     array_stack_push(stack, 30);
 
     printf("Top element is %d\n", array_stack_peek(stack)); // 30
 
     printf("%d popped from stack\n", array_stack_pop(stack)); // 30
     printf("%d popped from stack\n", array_stack_pop(stack)); // 20
 
     array_stack_push(stack, 40);
     printf("Top element is %d\n", array_stack_peek(stack)); // 40
 
     printf("%d popped from stack\n", array_stack_pop(stack)); // 40
     printf("%d popped from stack\n", array_stack_pop(stack)); // 10
     printf("%d popped from stack\n", array_stack_pop(stack)); // Stack Underflow
 
     free_array_stack(stack);
 }
 

b. 基于链表的栈实现

使用单向链表来实现栈，链表的头节点即为栈顶。

 // (需要之前单向链表的 SNode 定义)
 // typedef struct SNode { int data; struct SNode *next; } SNode;
 
 // 链式栈结构定义 (实际上只需要一个头指针)
 typedef struct LinkedStack {
     SNode *top; // 指向栈顶节点 (链表头)
     int count;  // 可选：记录元素数量
 } LinkedStack;
 
 // 初始化链式栈
 LinkedStack* create_linked_stack() {
     LinkedStack *stack = (LinkedStack*)malloc(sizeof(LinkedStack));
     if (!stack) {
         perror("Failed to create linked stack");
         return NULL;
     }
     stack->top = NULL;
     stack->count = 0;
     return stack;
 }
 
 // 检查链式栈是否为空
 int is_linked_stack_empty(LinkedStack *stack) {
     return stack->top == NULL; // 或者 stack->count == 0
 }
 
 // Push操作 (相当于在链表头部插入)
 void linked_stack_push(LinkedStack *stack, int item) {
     SNode *new_node = (SNode*)malloc(sizeof(SNode)); // 使用SNode的创建函数更好
     if (!new_node) {
         perror("Failed to allocate node for push");
         return;
     }
     new_node->data = item;
     new_node->next = stack->top;
     stack->top = new_node;
     stack->count++;
     // printf("%d pushed to linked stack.\n", item);
 }
 
 // Pop操作 (相当于删除链表头节点)
 int linked_stack_pop(LinkedStack *stack) {
     if (is_linked_stack_empty(stack)) {
         printf("Linked Stack Underflow! Cannot pop.\n");
         return INT_MIN;
     }
     SNode *temp = stack->top;
     int popped_item = temp->data;
     stack->top = stack->top->next;
     free(temp);
     stack->count--;
     return popped_item;
 }
 
 // Peek/Top操作
 int linked_stack_peek(LinkedStack *stack) {
     if (is_linked_stack_empty(stack)) {
         printf("Linked Stack is empty! Cannot peek.\n");
         return INT_MIN;
     }
     return stack->top->data;
 }
 
 // 释放链式栈 (释放所有节点和栈结构体本身)
 void free_linked_stack(LinkedStack *stack) {
     if (!stack) return;
     SNode *current = stack->top;
     SNode *next_node;
     while (current != NULL) {
         next_node = current->next;
         free(current);
         current = next_node;
     }
     free(stack);
 }
 
 // 链式栈使用示例
 void demo_linked_stack() {
     printf("--- Linked Stack Demo ---\n");
     LinkedStack *stack = create_linked_stack();
     if (!stack) return;
 
     linked_stack_push(stack, 100);
     linked_stack_push(stack, 200);
     linked_stack_push(stack, 300);
 
     printf("Top element is %d\n", linked_stack_peek(stack)); // 300
 
     printf("%d popped from linked stack\n", linked_stack_pop(stack)); // 300
     printf("Top element is %d\n", linked_stack_peek(stack)); // 200
 
     linked_stack_push(stack, 400);
     printf("%d popped from linked stack\n", linked_stack_pop(stack)); // 400
     printf("%d popped from linked stack\n", linked_stack_pop(stack)); // 200
     printf("%d popped from linked stack\n", linked_stack_pop(stack)); // 100
     printf("%d popped from linked stack\n", linked_stack_pop(stack)); // Underflow
 
     free_linked_stack(stack);
 }

栈的应用

• 函数调用栈：操作系统用栈来管理函数调用、局部变量和返回地址。
• 表达式求值：中缀表达式转后缀表达式，以及后缀表达式的求值。
• 括号匹配：检查代码或文本中的括号是否成对匹配。
• 深度优先搜索 (DFS)：在图或树的遍历中，DFS算法通常使用栈（显式或隐式通过递归）。
• 撤销/重做操作：编辑器或软件中的撤销功能常用栈来实现。
• 浏览器历史记录的“后退”按钮。

2. 队列 (Queue)

队列就像排队买票，先来的人先买到票离开。

队列的基本操作

• Enqueue (Enq)：将元素添加到队尾（rear）。
• Dequeue (Deq)：从队头（front）移除并返回元素。
• Peek/Front：查看队头元素但不移除。
• IsEmpty：检查队列是否为空。
• IsFull (对于基于数组的定长队列)：检查队列是否已满。

a. 基于数组的队列实现 (循环队列)

普通数组实现队列时，出队操作会导致所有后续元素前移（O(n)），效率低下。循环队列通过将数组视为环形来解决这个问题，使用 front 和 rear 两个指针（索引）以及一个 count 或特定逻辑来区分队空和队满。

 #define MAX_QUEUE_SIZE 5 // 小一点方便演示循环
 
 // 循环队列结构定义
 typedef struct ArrayQueue {
     int items[MAX_QUEUE_SIZE];
     int front; // 指向队头元素的前一个位置或队头元素本身 (不同实现方式)
     int rear;  // 指向队尾元素的实际位置
     int count; // 当前队列中的元素数量
 } ArrayQueue;
 
 // 初始化循环队列
 ArrayQueue* create_array_queue() {
     ArrayQueue *queue = (ArrayQueue*)malloc(sizeof(ArrayQueue));
     if (!queue) {
         perror("Failed to create array queue");
         return NULL;
     }
     queue->front = 0; // 或 -1, 根据具体实现调整
     queue->rear = -1; // 初始时 rear 在 front 之前表示空
     queue->count = 0;
     return queue;
 }
 
 // 检查队列是否已满
 int is_array_queue_full(ArrayQueue *queue) {
     return queue->count == MAX_QUEUE_SIZE;
 }
 
 // 检查队列是否为空
 int is_array_queue_empty(ArrayQueue *queue) {
     return queue->count == 0;
 }
 
 // Enqueue操作
 void array_queue_enqueue(ArrayQueue *queue, int item) {
     if (is_array_queue_full(queue)) {
         printf("Queue Overflow! Cannot enqueue %d.\n", item);
         return;
     }
     queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; // 循环移动rear指针
     queue->items[queue->rear] = item;
     queue->count++;
     // printf("%d enqueued to queue.\n", item);
 }
 
 // Dequeue操作
 int array_queue_dequeue(ArrayQueue *queue) {
     if (is_array_queue_empty(queue)) {
         printf("Queue Underflow! Cannot dequeue.\n");
         return INT_MIN;
     }
     int item = queue->items[queue->front];
     queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; // 循环移动front指针
     queue->count--;
     return item;
 }
 
 // Peek/Front操作
 int array_queue_front(ArrayQueue *queue) {
     if (is_array_queue_empty(queue)) {
         printf("Queue is empty! Cannot peek front.\n");
         return INT_MIN;
     }
     return queue->items[queue->front];
 }
 
 // 释放队列
 void free_array_queue(ArrayQueue *queue) {
     if (queue) {
         free(queue);
     }
 }
 
 // 循环队列使用示例
 void demo_array_queue() {
     printf("--- Array Queue (Circular) Demo ---\n");
     ArrayQueue *queue = create_array_queue();
     if (!queue) return;
 
     array_queue_enqueue(queue, 10);
     array_queue_enqueue(queue, 20);
     array_queue_enqueue(queue, 30);
     printf("Front element is %d\n", array_queue_front(queue)); // 10
 
     printf("%d dequeued from queue\n", array_queue_dequeue(queue)); // 10
     array_queue_enqueue(queue, 40);
     array_queue_enqueue(queue, 50);
     // Queue: 20, 30, 40, 50 (front at 20, rear at 50)
     printf("Front element is %d\n", array_queue_front(queue)); // 20
 
     array_queue_enqueue(queue, 60); // Queue is now full
     // Queue: 20, 30, 40, 50, 60
     printf("Front element is %d\n", array_queue_front(queue)); // 20
 
     array_queue_enqueue(queue, 70); // Overflow
 
     printf("%d dequeued from queue\n", array_queue_dequeue(queue)); // 20
     array_queue_enqueue(queue, 70); // Now can enqueue 70
     // Queue: 30, 40, 50, 60, 70
 
     printf("Dequeuing all: ");
     while (!is_array_queue_empty(queue)) {
         printf("%d ", array_queue_dequeue(queue));
     }
     printf("\n");
     array_queue_dequeue(queue); // Underflow
 
     free_array_queue(queue);
 }
 

b. 基于链表的队列实现

使用单向链表，并维护指向队头（front）和队尾（rear）的两个指针。 Enqueue 操作在链表尾部进行，Dequeue 操作在链表头部进行。

 // (需要之前单向链表的 SNode 定义)
 
 // 链式队列结构定义
 typedef struct LinkedQueue {
     SNode *front; // 指向队头节点
     SNode *rear;  // 指向队尾节点
     int count;    // 可选：元素数量
 } LinkedQueue;
 
 // 初始化链式队列
 LinkedQueue* create_linked_queue() {
     LinkedQueue *queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
     if (!queue) {
         perror("Failed to create linked queue");
         return NULL;
     }
     queue->front = NULL;
     queue->rear = NULL;
     queue->count = 0;
     return queue;
 }
 
 // 检查链式队列是否为空
 int is_linked_queue_empty(LinkedQueue *queue) {
     return queue->front == NULL; // 或者 queue->count == 0
 }
 
 // Enqueue操作 (在链表尾部添加)
 void linked_queue_enqueue(LinkedQueue *queue, int item) {
     SNode *new_node = (SNode*)malloc(sizeof(SNode)); // 使用SNode的创建函数更好
     if (!new_node) {
         perror("Failed to allocate node for enqueue");
         return;
     }
     new_node->data = item;
     new_node->next = NULL;
 
     if (is_linked_queue_empty(queue)) { // 如果队列为空
         queue->front = new_node;
         queue->rear = new_node;
     } else {
         queue->rear->next = new_node; // 原队尾指向新节点
         queue->rear = new_node;       // 更新队尾指针
     }
     queue->count++;
     // printf("%d enqueued to linked queue.\n", item);
 }
 
 // Dequeue操作 (从链表头部移除)
 int linked_queue_dequeue(LinkedQueue *queue) {
     if (is_linked_queue_empty(queue)) {
         printf("Linked Queue Underflow! Cannot dequeue.\n");
         return INT_MIN;
     }
     SNode *temp = queue->front;
     int dequeued_item = temp->data;
     queue->front = queue->front->next;
 
     if (queue->front == NULL) { // 如果出队后队列为空
         queue->rear = NULL;
     }
     free(temp);
     queue->count--;
     return dequeued_item;
 }
 
 // Peek/Front操作
 int linked_queue_front_val(LinkedQueue *queue) { // Renamed to avoid conflict
     if (is_linked_queue_empty(queue)) {
         printf("Linked Queue is empty! Cannot peek front.\n");
         return INT_MIN;
     }
     return queue->front->data;
 }
 
 // 释放链式队列
 void free_linked_queue(LinkedQueue *queue) {
     if (!queue) return;
     SNode *current = queue->front;
     SNode *next_node;
     while (current != NULL) {
         next_node = current->next;
         free(current);
         current = next_node;
     }
     free(queue);
 }
 
 // 链式队列使用示例
 void demo_linked_queue() {
     printf("--- Linked Queue Demo ---\n");
     LinkedQueue *queue = create_linked_queue();
     if (!queue) return;
 
     linked_queue_enqueue(queue, 1000);
     linked_queue_enqueue(queue, 2000);
     linked_queue_enqueue(queue, 3000);
 
     printf("Front element is %d\n", linked_queue_front_val(queue)); // 1000
 
     printf("%d dequeued from linked queue\n", linked_queue_dequeue(queue)); // 1000
     printf("Front element is %d\n", linked_queue_front_val(queue)); // 2000
 
     linked_queue_enqueue(queue, 4000);
     // Queue: 2000, 3000, 4000
 
     printf("%d dequeued from linked queue\n", linked_queue_dequeue(queue)); // 2000
     printf("%d dequeued from linked queue\n", linked_queue_dequeue(queue)); // 3000
     printf("%d dequeued from linked queue\n", linked_queue_dequeue(queue)); // 4000
     printf("%d dequeued from linked queue\n", linked_queue_dequeue(queue)); // Underflow
 
     free_linked_queue(queue);
 }
 

队列的应用

• 任务调度：操作系统中的进程调度、打印机任务队列。
• 广度优先搜索 (BFS)：在图或树的遍历中，BFS算法使用队列来存储待访问的节点。
• 缓冲区：在数据生产者和消费者之间用作缓冲区，例如I/O操作、网络数据包处理。
• 消息队列：在分布式系统中用于组件间的异步通信。
• 模拟排队系统：如银行排队、呼叫中心等待。

3. 比较与选择

选择依据：

• 如果元素数量上限已知且不大，或者对内存连续性有要求，数组实现可能更优（尤其是栈）。
• 如果元素数量不确定，或者需要频繁动态增删，链表实现更灵活，避免了固定大小的限制和数据搬移。
• 对于队列，链表实现通常比简单的（非循环）数组实现更高效，而循环数组队列则提供了与链表队列相当的性能，但有大小限制。

总结

栈和队列是构建更复杂算法和系统的基石。理解它们的LIFO和FIFO特性，以及如何通过数组或链表来实现它们，对于C程序员来说非常重要。

• 栈：后进先出，常用于递归模拟、表达式求值、撤销操作等。
• 队列：先进先出，常用于任务调度、BFS、缓冲区等。

选择合适的实现方式取决于具体的应用需求，如数据量、性能要求和内存管理的复杂度。

 // Main function to run demos (uncomment SNode definition if needed)
 /*
 typedef struct SNode { // Make sure SNode is defined if running linked versions
     int data;
     struct SNode *next;
 } SNode;
 
 int main() {
     demo_array_stack();
     printf("\n");
     demo_linked_stack();
     printf("\n");
     demo_array_queue();
     printf("\n");
     demo_linked_queue();
     return 0;
 }
 */