栈与队列（C语言版）

栈与队列

1. 栈

栈是一种操作受限的线性结构。操作受限体现在，栈只能在一端添加和删除元素，符合后进先出 ( LIFO ) 的特性，如下图所示：

基本操作

1. 入栈
2. 出栈
3. 查看栈顶元素
4. 判空

实现(基于链表)

代码

// Stack.h
// 定义结点类型
typedef struct node {int val;struct node* next;} Node;// API
void push_stack(Node** pstack, int val);
int  pop_stack(Node** pstack);
int  peek_stack(Node* stack);
bool is_empty(Node* stack);

// Stack.c
#include "stack.h"
#include <stdlib.h>
#include <stdio.h>void push_stack(Node** pstack, int val) {// 头插法Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = val;newNode->next = NULL;newNode->next = *pstack;*pstack = newNode;
}int pop_stack(Node** pstack) {if (*pstack == NULL) {printf("栈为空，无法弹出元素");return -1;}int pop_val = (*pstack)->val;*pstack = (*pstack)->next;printf("弹出元素：%d\n", pop_val);return pop_val;
}int  peek_stack(Node* stack) {if (stack == NULL) {printf("栈为空, 无法查看栈顶元素\n");return -1;}printf("栈顶元素：%d\n", stack->val);return stack->val;
}bool is_empty(Node* stack) {if (stack) {printf("栈不为空\n");return false;}printf("栈为空\n");return true;
}

// main.c
#include<stdio.h>
#include"stack.h"int main(void) {Node* stack = NULL;push_stack(&stack, 1);push_stack(&stack, 2);peek_stack(stack);pop_stack(&stack);peek_stack(stack);is_empty(stack);pop_stack(&stack);peek_stack(stack);is_empty(stack);return 0;}

运行结果

应用场景

栈的应用场景是多种多样的：

• 函数调用栈
• 符号匹配问题
• 表达式求值
• 深度优先搜索（DFS）
• . . .

2. 队列

队列是另一种操作受限的线性结构。操作受限体现在，队列只能在一端添加元素，在另一端删除元素，符合**先进先出(FIFO)**的特性。

基本操作

1. 入队列
2. 出队列
3. 查看队头元素
4. 判空

实现

代码

1. 用链表实现

2. 用数组实现（没使用循环数组的方法， 没有自动扩容功能）

   // Queue.h
   #define N 10typedef struct {int elements[N];int front;int rear;int size;
   } Queue;// API
   Queue* create_queue();
   void destroy_queue(Queue* q);void push_queue(Queue* q, int val);
   int pop_queue(Queue* q);
   int peek_queue(Queue* q);bool is_empty(Queue* q);
   bool is_full(Queue* q);
   

   // Queue.c
   #include "queue.h"
   #include <stdio.h>
   #include <malloc.h>Queue* create_queue() {Queue* que = (Queue*)malloc(sizeof(Queue));que->front = 0; // 队头que->rear = -1; // 队尾que->size = 0;return que;
   }void destroy_queue(Queue* q) {free(q);printf("队列已释放\n");
   }void push_queue(Queue* q, int val) {if (is_full(q)) {printf("队列已满，无法插入元素\n");return;}if (q->rear == N - 1) { // 队尾指针已经到数组尾部边界，需要将元素移动到数组头部for (int i = q->front, j = 0; i <= q->rear; i++, j++) {q->elements[j] = q->elements[i];}q->front = 0;q->rear = q->size - 1;}q->elements[q->rear + 1] = val;q->rear++;q->size++;printf("成功在队尾插入元素：%d\n", val);
   }int pop_queue(Queue* q) {if (is_empty(q)) {printf("队列为空，无法弹出元素\n");return -1;}int pop_val = q->elements[q->front];q->front++;q->size--;printf("成功在队头弹出元素：%d\n", pop_val);return pop_val;
   }int peek_queue(Queue* q) {if (is_empty(q)) {printf("队列为空，无法查看元素\n");return -1;}return q->elements[q->front];
   }bool is_full(Queue* q) {if (q->rear - q->front == N - 1) {// printf("队列已满\n");return true;}return false;
   }bool is_empty(Queue* q) {if (q->rear < q->front) {// printf("队列为空\n");return true;}return false;
   }
   

   // main.c
   #include <stdio.h>
   #include "queue.h"int main(void) {Queue* que = create_queue();pop_queue(que);push_queue(que, 1);push_queue(que, 2);push_queue(que, 3);printf("查看队头元素：%d\n", peek_queue(que));pop_queue(que);printf("查看队头元素：%d\n", peek_queue(que));push_queue(que, 4);push_queue(que, 5);push_queue(que, 6);push_queue(que, 7);push_queue(que, 8);push_queue(que, 9);push_queue(que, 10);printf("队头索引：%d  队尾索引：%d\n", que->front, que->rear);printf ("队列元素个数：%d\n", que->size);push_queue(que, 11);printf("队头索引：%d  队尾索引：%d\n", que->front, que->rear);printf ("队列元素个数：%d\n", que->size);push_queue(que, 12);destroy_queue(que);return 0;
   }
   

运行结果

应用场景

• 缓冲
• 广度优先搜索（BFS）
• . . .