栈与队列（C语言版）

文章目录 栈与队列1. 栈基本操作实现(基于链表)代码运行结果 应用场景 2. 队列基本操作实现代码运行结果 应用场景

栈与队列 1. 栈

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

基本操作 入栈出栈查看栈顶元素判空 实现(基于链表) 代码 // 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)**的特性。

基本操作 入队列出队列查看队头元素判空 实现 代码

用链表实现

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

// Queue.h #define N 10 typedef 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）. . .