重生之“我打数据结构，真的假的？”--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>#define MAX_SIZE 100typedef struct Stack {int items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == -1;
}// 判断栈是否已满
bool isFull(Stack* stack) {return stack->top == MAX_SIZE - 1;
}// 压栈操作
void push(Stack* stack, int value) {if (isFull(stack)) {printf("栈已满，无法压入元素。\n");return;}stack->items[++stack->top] = value;printf("压入元素：%d\n", value);
}// 弹栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无法弹出元素。\n");return -1;}return stack->items[stack->top--];
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，没有栈顶元素。\n");return -1;}return stack->items[stack->top];
}// 遍历栈
void traverseStack(Stack* stack) {if (isEmpty(stack)) {printf("栈为空。\n");return;}for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->items[i]);}printf("\n");
}int main() {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);return 0;
}
1.3.2 使用链表实现栈

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

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node* next;
} Node;typedef struct Stack {Node* top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = NULL;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == NULL;
}// 压栈操作
void push(Stack* stack, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = stack->top;stack->top = newNode;printf("压入元素：%d\n", value);
}// 弹栈操作
int pop(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;
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，没有栈顶元素。\n");return -1;}return stack->top->data;
}// 遍历栈
void traverseStack(Stack* stack) {Node* current = stack->top;if (isEmpty(stack)) {printf("栈为空。\n");return;}while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {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);return 0;
}

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>#define MAX_SIZE 100typedef struct Queue {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(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;
}// 入队操作
void enqueue(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);
}// 出队操作
int dequeue(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;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，没有队头元素。\n");return -1;}return queue->items[queue->front];
}// 遍历队列
void traverseQueue(Queue* queue) {if (isEmpty(queue)) {printf("队列为空。\n");return;}for (int i = queue->front; i <= queue->rear; i++) {printf("%d ", queue->items[i]);}printf("\n");
}int main() {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);return 0;
}
2.3.2 使用链表实现队列

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

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node* next;
} Node;typedef struct Queue {Node* front;Node* rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue->front = NULL;queue->rear = NULL;
}// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue->front == NULL;
}// 入队操作
void enqueue(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);
}// 出队操作
int dequeue(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;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf("队列为空，没有队头元素。\n");return -1;}return queue->front->data;
}// 遍历队列
void traverseQueue(Queue* queue) {Node* current = queue->front;if (isEmpty(queue)) {printf("队列为空。\n");return;}while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {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);return 0;
}

2.4 队列的应用

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

3. 栈和队列的对比

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

4. 小结

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/456573.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

基于Multisim的四人智力竞赛抢答器设计与仿真

基于Multisim的四人智力竞赛抢答器设计与仿真

1&#xff09;设计任务 设计一台可供 4 名选手参加比赛的智力竞赛抢答器。 用数字显示抢答倒计时间&#xff0c;由“9”倒计到“0”时&#xff0c;无人抢答&#xff0c;蜂鸣器连续响 1 秒。选手抢答时&#xff0c;数码显示选手组号&#xff0c;同时蜂鸣器响 1 秒&#xff0c;倒…
阅读更多...
基于Python+SQL Server2008实现（GUI）快递管理系统

基于Python+SQL Server2008实现（GUI）快递管理系统

快递业务管理系统的设计与实现 摘要: 着网络新零售的到来&#xff0c;传统物流在网购的洗礼下迅速蜕变&#xff0c;在这场以互联网为基础的时代变革中&#xff0c;哪家企业能率先转变其工作模式就能最先分得一杯羹&#xff0c;物流管理也不例外。传统的物流管理模式效率低下&a…
阅读更多...
金融工程--pine-script 入门

金融工程--pine-script 入门

背景 脚本基本组成 策略实现 实现马丁格尔策略 初始化变量&#xff1a;定义初始资本、初始头寸大小、止损百分比、止盈百分比以及当前资本和当前头寸大小等变量。 更新头寸&#xff1a;创建一个函数来更新头寸大小、止损价格和止盈价格。在马丁格尔策略中&#xff0c;每次亏…
阅读更多...
micro-app【微前端实战】主应用 vue3 + vite 子应用 vue3+vite

micro-app【微前端实战】主应用 vue3 + vite 子应用 vue3+vite

micro-app 官方文档为 https://micro-zoe.github.io/micro-app/docs.html#/zh-cn/framework/vite 子应用 无需任何修改&#xff0c;直接启动子应用即可。 主应用 1. 安装微前端框架 microApp npm i micro-zoe/micro-app --save2. 导入并启用微前端框架 microApp src/main.ts …
阅读更多...
【Ubuntu】Virtualbox下lamp集群分布式搭建Wordpress

【Ubuntu】Virtualbox下lamp集群分布式搭建Wordpress

WordPress是一种使用PHP语言开发的开源内容管理系统&#xff08;CMS&#xff09;&#xff0c;也常被用作博客平台。 开发语言&#xff1a;PHP 数据库&#xff1a;MySQL、mariadb&#xff08;或其他兼容的数据库系统&#xff09; 授权方式&#xff1a;GNU通用公共许可证下发布&a…
阅读更多...
【JavaEE】【多线程】单例模式

【JavaEE】【多线程】单例模式

目录 一、设计模式1.1 单例模式1.1.1 饿汉模式1.1.2 懒汉模式 1.2 线程安全问题1.3 懒汉模式线程安全问题的解决方法1.3.1 原子性问题解决1.3.2 解决效率问题1.3.3 解决内存可见性问题和指令重排序问题 一、设计模式 在讲解案例前&#xff0c;先介绍一个概念设计模式&#xff…
阅读更多...
C++ 模版和继承

C++ 模版和继承

目录 一.模版 1.模版的基本概念 a.函数模版 b.类模板 c.模版的实例化 d.class 和 typename的区别 e.非类型模版参数 2.模版的特化 a.全特化 —— 参数类型全部特殊化处理 b.半特化 —— 部分参数特殊化处理 c.偏特化——对某些类型的进一步限制&#xff08;实例化时传…
阅读更多...
GD32学习知识点累计

GD32学习知识点累计

时钟系统 GD32f427主频最高位240MHZ&#xff08;但是只能到200M&#xff09;&#xff0c;GD32给的函数外接25MHZ晶振配置主频为200MHZ,APB1最高频率为60HZ配置为主频的4分频为50MHZ&#xff0c;APB2最大为120MHZ配置为主频的2分频为100MHZ 定时器 无论什么定时器最大频率为200M…
阅读更多...
安全见闻---清风

安全见闻---清风

注&#xff1a;本文章源于泷羽SEC&#xff0c;如有侵权请联系我&#xff0c;违规必删 学习请认准泷羽SEC学习视频:https://space.bilibili.com/350329294 安全见闻1 泷哥语录&#xff1a;安全领域什么都有&#xff0c;不要被表象所迷惑&#xff0c;无论技术也好还是其他方面…
阅读更多...
AI带货主播框架的搭建!

AI带货主播框架的搭建!

AI带货主播&#xff0c;作为新兴的技术应用&#xff0c;正在逐渐改变电商行业的面貌&#xff0c;通过利用人工智能技术&#xff0c;AI带货主播能够模拟真实主播的行为&#xff0c;与用户进行互动&#xff0c;推荐商品&#xff0c;提升购物体验。 本文将介绍如何搭建一个AI带货…
阅读更多...
处理Hutool的Http工具上传大文件报OOM

处理Hutool的Http工具上传大文件报OOM

程序环境 JDK版本&#xff1a; 1.8Hutool版本&#xff1a; 5.8.25 问题描述 客服端文件上传主要代码&#xff1a; HttpRequest httpRequest HttpUtil.createPost(FILE_UPLOAD_URL); Resource urlResource new UrlResource(url, fileName); httpRequest.form("file&q…
阅读更多...
self-supervised learning(BERT和GPT)

self-supervised learning(BERT和GPT)

1芝麻街与NLP模型 我們接下來要講的主題呢叫做Self-Supervised Learning&#xff0c;在講self-supervised learning之前呢&#xff0c;就不能不介紹一下芝麻街&#xff0c;為什麼呢因為不知道為什麼self-supervised learning的模型都是以芝麻街的人物命名。 因為Bert是一個非常…
阅读更多...
实战-任意文件下载

实战-任意文件下载

实战-任意文件下载 1、开局 开局一个弱口令&#xff0c;正常来讲我们一般是弱口令或者sql&#xff0c;或者未授权 那么这次运气比较好&#xff0c;直接弱口令进去了 直接访问看看有没有功能点&#xff0c;正常做测试我们一定要先找功能点 发现一个文件上传点&#xff0c;不…
阅读更多...
中酱集团：黑松露酱油，天然配方定义健康生活

中酱集团：黑松露酱油，天然配方定义健康生活

在如今的大健康时代&#xff0c;人们对于美食的要求越来越高。不仅美味&#xff0c;更要健康。在健康美食的生态链中&#xff0c;有一个名字正逐渐成为品质与美味的代名词——中酱集团。而当中酱集团与黑松露酱油相遇&#xff0c;一场味觉的革命就此拉开帷幕。 中酱集团&#x…
阅读更多...
【产品应用】旋转式贴标机一站式解决方案

【产品应用】旋转式贴标机一站式解决方案

针对贴标机行业设备&#xff0c;立迈胜公司拥有智能控制器、一体化伺服电机、减速机等系列产品&#xff0c;可以轻松解决传统电机接线不便、占用空间、自重过大、部件繁杂等问题&#xff0c;帮助贴标机制造商实现设备精准控制、运行稳定的同时&#xff0c;保证生产流程高效产出…
阅读更多...
开发运维警示录-20241024

开发运维警示录-20241024

开发警示录 1、作为开发&#xff0c;不要私自修改业务人员给的SQL语句&#xff0c;虽然个人感觉SQL很冗余&#xff0c;效率低等。 2、开发前&#xff0c;要明确需求&#xff0c;必要时通过图和文字形成文档与需求方确认、留痕。 3、开发复杂的业务逻辑代码前&#xff0c;先疏通…
阅读更多...
oracle数据库---PL/SQL、存储函数、存储过程、触发器、定时器job、备份

oracle数据库---PL/SQL、存储函数、存储过程、触发器、定时器job、备份

PL/SQL 什么是 PL/SQL PL/SQL&#xff08;Procedure Language/SQL&#xff09;是 Oracle 对 sql 语言的过程化扩展&#xff0c;指在 SQL 命令语言中增加了过程处理语句&#xff08;如分支、循环等&#xff09;&#xff0c;使 SQL 语言具有过程处理能力。把SQL语言的数据操纵能…
阅读更多...
瑞芯微的 展会总结

瑞芯微的 展会总结

首先是我感兴趣的产品&#xff1a; 摄像头的 墨水瓶的。 android 盒子&#xff0c;使用的是rk3588s 然后是瑞芯微&#xff21;&#xff29;在做什么&#xff1a;　 在对 音频 视屏的输出 进行补充。 比如&#xff0c;视频拍了一张图片很模糊&#xff0c;那么他们用AI算法&am…
阅读更多...
基于Multisim红外接近报警电路设计（含仿真和报告）

基于Multisim红外接近报警电路设计（含仿真和报告）

【全套资料.zip】红外接近报警电路设计Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 标题&#xff1a;红外接近报警电路 红外报警器是当前利用电子技术制作而成的防盗报警器&#xff0c…
阅读更多...
Sei 生态迎首个 MMORPG 游戏伙伴 Final Glory，开启新篇章

Sei 生态迎首个 MMORPG 游戏伙伴 Final Glory，开启新篇章

​“随着 Final Glory 拓展至 SEI Network&#xff0c;SEI 生态也迎来了首款 MMORPG 游戏” 链游赛道新贵 Final Glory Final Glory 是建立在 MateArena 引擎上的 MMORPG 游戏&#xff0c;作为目前行业内首个斥巨资打造的 AAA 级 MMORPG 全链游戏&#xff0c;在面向市场后即引发…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023