重生之“我打数据结构，真的假的？”--3.栈和队列（无习题）

Ne0inhk

— 8 min read
重生之“我打数据结构，真的假的？”--3.栈和队列（无习题）

栈和队列

C语言中的栈和队列总结

在C语言中，**栈（Stack）和队列（Queue）**是两种非常重要的数据结构。它们广泛用于各种应用中，比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介绍，并展示如何在C语言中实现它们。

1. 栈（Stack）

栈是一种先进后出（LIFO，Last In First Out）数据结构，类似于一摞盘子，最后放上去的盘子最先被拿下来。

在这里插入图片描述

1.1 栈的特点

  • 先进后出（LIFO）：最后入栈的元素最先出栈。
  • 单端操作：栈的插入和删除操作都发生在栈顶。

1.2 栈的基本操作

  • 压栈（Push）：将元素压入栈顶。
  • 弹栈（Pop）：从栈顶移除元素。
  • 查看栈顶元素（Peek/Top）：获取栈顶元素但不删除它。
  • 判断栈是否为空（isEmpty）。

1.3 栈的实现方式

栈可以通过数组或链表来实现。以下分别讨论栈的数组实现和链表实现。

1.3.1 使用数组实现栈

以下是用C语言实现栈的数组版：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#defineMAX_SIZE100typedefstructStack{int items[MAX_SIZE];int top;} Stack;// 初始化栈voidinitStack(Stack* stack){ stack->top =-1;}// 判断栈是否为空 bool isEmpty(Stack* stack){return stack->top ==-1;}// 判断栈是否已满 bool isFull(Stack* stack){return stack->top == MAX_SIZE -1;}// 压栈操作voidpush(Stack* stack,int value){if(isFull(stack)){printf("栈已满，无法压入元素。\n");return;} stack->items[++stack->top]= value;printf("压入元素：%d\n", value);}// 弹栈操作intpop(Stack* stack){if(isEmpty(stack)){printf("栈为空，无法弹出元素。\n");return-1;}return stack->items[stack->top--];}// 查看栈顶元素intpeek(Stack* stack){if(isEmpty(stack)){printf("栈为空，没有栈顶元素。\n");return-1;}return stack->items[stack->top];}// 遍历栈voidtraverseStack(Stack* stack){if(isEmpty(stack)){printf("栈为空。\n");return;}for(int i =0; i <= stack->top; i++){printf("%d ", stack->items[i]);}printf("\n");}intmain(){ Stack stack;initStack(&stack);push(&stack,10);push(&stack,20);push(&stack,30);printf("栈的内容：");traverseStack(&stack);printf("弹出元素：%d\n",pop(&stack));printf("栈顶元素：%d\n",peek(&stack));printf("栈的内容：");traverseStack(&stack);return0;}
1.3.2 使用链表实现栈

以下是使用链表实现栈的C语言代码：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstructNode{int data;structNode* next;} Node;typedefstructStack{ Node* top;} Stack;// 初始化栈voidinitStack(Stack* stack){ stack->top =NULL;}// 判断栈是否为空 bool isEmpty(Stack* stack){return stack->top ==NULL;}// 压栈操作voidpush(Stack* stack,int value){ Node* newNode =(Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = stack->top; stack->top = newNode;printf("压入元素：%d\n", value);}// 弹栈操作intpop(Stack* stack){if(isEmpty(stack)){printf("栈为空，无法弹出元素。\n");return-1;} Node* temp = stack->top;int poppedValue = temp->data; stack->top = stack->top->next;free(temp);return poppedValue;}// 查看栈顶元素intpeek(Stack* stack){if(isEmpty(stack)){printf("栈为空，没有栈顶元素。\n");return-1;}return stack->top->data;}// 遍历栈voidtraverseStack(Stack* stack){ Node* current = stack->top;if(isEmpty(stack)){printf("栈为空。\n");return;}while(current !=NULL){printf("%d ", current->data); current = current->next;}printf("\n");}intmain(){ Stack stack;initStack(&stack);push(&stack,10);push(&stack,20);push(&stack,30);printf("栈的内容：");traverseStack(&stack);printf("弹出元素：%d\n",pop(&stack));printf("栈顶元素：%d\n",peek(&stack));printf("栈的内容：");traverseStack(&stack);return0;}

1.4 栈的应用

  • 函数调用栈：计算机系统使用栈来保存函数调用的返回地址。
  • 表达式求值和括号匹配：在表达式求值中，栈用于临时保存操作数和操作符。
  • 深度优先搜索（DFS）：在图的遍历中，栈可以用于实现深度优先搜索。

2. 队列（Queue）

队列是一种先进先出（FIFO，First In First Out）数据结构，类似于排队买票，第一个到达的人先买票。

2.1 队列的特点

  • 先进先出（FIFO）：第一个入队的元素第一个出队。
  • 双端操作：插入操作发生在队尾，而删除操作发生在队头。

2.2 队列的基本操作

  • 入队（Enqueue）：在队尾添加一个元素。
  • 出队（Dequeue）：从队头移除一个元素。
  • 查看队头元素（Front）。
  • 判断队列是否为空（isEmpty）。

2.3 队列的实现方式

队列可以通过数组或链表来实现。以下分别介绍这两种实现方式。

2.3.1 使用数组实现队列

以下是使用数组实现队列的C语言代码：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#defineMAX_SIZE100typedefstructQueue{int items[MAX_SIZE];int front;int rear;} Queue;// 初始化队列voidinitQueue(Queue* queue){ queue->front =-1; queue->rear =-1;}// 判断队列是否为空 bool isEmpty(Queue* queue){return queue->front ==-1;}// 判断队列是否已满 bool isFull(Queue* queue){return queue->rear == MAX_SIZE -1;}// 入队操作voidenqueue(Queue* queue,int value){if(isFull(queue)){printf("队列已满，无法入队元素。\n");return;}if(isEmpty(queue)){ queue->front =0;} queue->items[++queue->rear]= value;printf("入队元素：%d\n", value);}// 出队操作intdequeue(Queue* queue){if(isEmpty(queue)){printf("队列为空，无法出队元素。\n");return-1;}int value = queue->items[queue->front];if(queue->front >= queue->rear){// 队列为空 queue->front = queue->rear =-1;}else{ queue->front++;}return value;}// 查看队头元素intfront(Queue* queue){if(isEmpty(queue)){printf("队列为空，没有队头元素。\n");return-1;}return queue->items[queue->front];}// 遍历队列voidtraverseQueue(Queue* queue){if(isEmpty(queue)){printf("队列为空。\n");return;}for(int i = queue->front; i <= queue->rear; i++){printf("%d ", queue->items[i]);}printf("\n");}intmain(){ Queue queue;initQueue(&queue);enqueue(&queue,10);enqueue(&queue,20);enqueue(&queue,30);printf("队列的内容：");traverseQueue(&queue);printf("出队元素：%d\n",dequeue(&queue));printf("队头元素：%d\n",front(&queue));printf("队列的内容：");traverseQueue(&queue);return0;}
2.3.2 使用链表实现队列

以下是使用链表实现队列的C语言代码：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstructNode{int data;structNode* next;} Node;typedefstructQueue{ Node* front; Node* rear;} Queue;// 初始化队列voidinitQueue(Queue* queue){ queue->front =NULL; queue->rear =NULL;}// 判断队列是否为空 bool isEmpty(Queue* queue){return queue->front ==NULL;}// 入队操作voidenqueue(Queue* queue,int value){ Node* newNode =(Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next =NULL;if(isEmpty(queue)){ queue->front = queue->rear = newNode;}else{ queue->rear->next = newNode; queue->rear = newNode;}printf("入队元素：%d\n", value);}// 出队操作intdequeue(Queue* queue){if(isEmpty(queue)){printf("队列为空，无法出队元素。\n");return-1;} Node* temp = queue->front;int value = temp->data; queue->front = queue->front->next;if(queue->front ==NULL){ queue->rear =NULL;}free(temp);return value;}// 查看队头元素intfront(Queue* queue){if(isEmpty(queue)){printf("队列为空，没有队头元素。\n");return-1;}return queue->front->data;}// 遍历队列voidtraverseQueue(Queue* queue){ Node* current = queue->front;if(isEmpty(queue)){printf("队列为空。\n");return;}while(current !=NULL){printf("%d ", current->data); current = current->next;}printf("\n");}intmain(){ Queue queue;initQueue(&queue);enqueue(&queue,10);enqueue(&queue,20);enqueue(&queue,30);printf("队列的内容：");traverseQueue(&queue);printf("出队元素：%d\n",dequeue(&queue));printf("队头元素：%d\n",front(&queue));printf("队列的内容：");traverseQueue(&queue);return0;}

2.4 队列的应用

  • 操作系统中的任务调度：队列用于实现任务调度和处理。
  • 广度优先搜索（BFS）：在图的遍历中，队列用于实现广度优先搜索。
  • 缓存（Buffer）：队列可用于实现环形缓冲区或缓冲机制。

3. 栈和队列的对比

特性栈（Stack）队列（Queue）
数据结构类型线性线性
操作模式LIFO（后进先出）FIFO（先进先出）
插入/删除位置只在一端操作（栈顶）两端操作（队头和队尾）
应用场景函数调用、递归、括号匹配任务调度、广度优先搜索

4. 小结

栈和队列都是重要的线性数据结构，栈采用LIFO原则，而队列采用FIFO原则。栈和队列的操作非常简单，但它们在实际应用中起到了至关重要的作用。在C语言中，栈和队列可以通过数组或链表来实现，每种实现方式都有其优缺点。

在理解了这些数据结构的基本操作后，可以更好地应用它们来解决实际问题，如表达式求值、任务调度、图遍历等。掌握这些基础数据结构也为进一步学习更加复杂的数据结构（如树、图等）打下了坚实的基础。

Read more

Java 泛型擦除深度解析：原理与限制全揭秘

Java 泛型擦除深度解析：原理与限制全揭秘

Java 泛型的设计有个独特之处：类型信息只存在于编译期，运行时会被彻底擦除。这种 “擦除” 机制让很多开发者困惑：为什么List<String>和List<Integer>在运行时是同一个类型？为什么不能用基本类型作为泛型参数？为什么创建泛型数组会报错？今天我们就从泛型擦除的底层原理讲起，彻底搞懂这些问题，看清泛型的 “真面目”。 一、泛型擦除：Java 泛型的 “编译期幻术”         泛型是 Java 5 引入的特性，但为了兼容之前的版本（Java 5 之前没有泛型），Java 采用了类型擦除（Type Erasure） 的实现方式：编译时检查泛型类型合法性，运行时擦除所有泛型信息。也就是说，泛型只在编译期起作用，运行时 JVM 根本不知道泛型参数的存在。 1. 擦除的核心过程：从泛型到原始类型

By Ne0inhk
JavaSE重点总结后篇

JavaSE重点总结后篇

🔥个人主页：寻星探路 🎬作者简介：Java研发方向学习者 📖个人专栏：JAVA（SE）----如此简单 从青铜到王者，就差这讲数据结构！！数据库那些事！！JavaEE 初阶启程记：跟我走不踩坑测试开发漫谈 ⭐️人生格言：没有人生来就会编程，但我生来倔强！！！ 目录 一、面向对象 1、深拷贝和其那拷贝的区别 2、Java创建对象有哪几种方式？ 二、String 1、String 和StringBuilder、StringBuffer 的区别? 2、String 是不可变类吗? 三、异常处理 1、Java中的异常体系？ 2、异常的处理方式 四、I/O 1、Java中IO流分为几种？ 2、有了字节流为什么还要有字符流？ 3、BIO、NIO、

By Ne0inhk
用飞算JavaAI做项目：在线图书借阅平台设计与实现

用飞算JavaAI做项目：在线图书借阅平台设计与实现

目录 * 一、引言 * 二、环境准备 * 1. 下载并安装IntelliJ IDEA * 2. 安装飞算JavaAI插件 * 3. 登录飞算JavaAI * 三、模块设计与编码 * 1. 飞算JavaAI生成基础模块 * 2. 核心代码展示 * （1）entity包：核心实体类 * （2）dto包：数据传输对象（带参数校验） * （3）vo包：视图对象（向前端隐藏敏感字段） * （4）service包：业务逻辑实现（含核心校验） * 四、网页展示 * 1. 图书查询页 * 2. 借阅记录页 * 3. 图书管理页 * 五、优化与调试 * 1. 核心优化点 * 2. 调试中遇到的问题及解决 * 六、自我感想 * 七、

By Ne0inhk

2026年 Java 面试八股文总结（完整版）

1、Java中有几种类型的流    难度系数：⭐ 2、请写出你最常见的5个RuntimeException    难度系数：⭐ 1. java.lang.NullPointerException 空指针异常；出现原因：调用了未经初始化的对象或者是不存在的对象。 1. java.lang.ClassNotFoundException 指定的类找不到；出现原因：类的名称和路径加载错误；通常都是程序试图通过字符串来加载某个类时可能引发异常。 1. java.lang.NumberFormatException 字符串转换为数字异常；出现原因：字符型数据中包含非数字型字符。 1. java.lang.IndexOutOfBoundsException 数组角标越界异常，常见于操作数组对象时发生。 1. java.lang.IllegalArgumentException 方法传递参数错误。 1. java.lang.ClassCastException 数据类型转换异常。 3、谈谈你对反射的理解    难度系数：⭐ 1. 反射

By Ne0inhk