栈和队列（C语言）

server/2025/1/24 21:29:20/

目录

数据结构之栈

定义

 实现方式

基本功能实现

1）定义，初始化栈

2）入栈

3）出栈

4）获得栈顶元素

5)获得栈中有效元素个数

6）检测栈是否为空

7）销毁栈

数据结构之队列 

定义

实现方式

基本功能实现

1）定义，初始化队列

2）入队

3）出队

4）获得队列头部元素

5）获得队尾元素

6）队列元素个数

7）队列是否为空

8）销毁队列

栈和队列练习

1.1 有效括号

用栈的先入后出性质

数据结构之栈

定义

栈：一种特殊的线性表，其特点是只允许在一端进行插入和删除的操作，这一端叫做栈顶，另一端叫做栈底；栈中的数据使用的时候必须遵行先入后出(先进入的后出来)的原则。就好比一群人上电梯，最先进去的站在里面，最后出来，而最后上来的站在门口，最先出来。

压栈：向栈顶插入元素；

出栈：将栈顶元素删去；

原则：入栈和出栈的操作对象都是栈顶。

 实现方式

栈的实现方式有两种，可以用前面的顺序表也可以使用链表。

1）使用链表实现，要记录尾节点(避免遍历链表找尾)方便压栈；同时还要记录倒数第二个节点，方便出栈时，将尾节点释放。所以一共需要定义两个结构体：链表结构体，结构体(记录头节点，尾节点，倒数第二个节点)；

2）使用顺序表实现，顺序表有栈内的总个数，可以直接找到尾，也可以直接出栈，相比于链表更简单。所以我们更推荐使用顺序表来实现栈。

顺序表（含通讯录）-CSDN博客文章浏览阅读743次，点赞16次，收藏11次。C语言实现顺序表及其基本功能的实现，包含通讯录项目。https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098

链表(C语言)-CSDN博客文章浏览阅读730次，点赞18次，收藏7次。用C语言实现数据结构中单链表和双链表的详细介绍https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576

基本功能实现

1）定义，初始化栈

栈的底层逻辑是顺序表，所以可以直接使用顺序表的初始化。

typedef int SDateType;typedef struct Stack
{SDateType* a;int size;int capacity;
}Stack;//栈的初始化
void StackInit(Stack* ps)
{assert(ps);ps->capacity = 4;ps->a = (SDateType*)malloc(sizeof(SDateType)*(ps->capacity));if (ps->a == NULL)perror("malloc failed!");ps->size = 0;
}

2）入栈

向栈顶添加元素，ps->size就是栈顶位置的下标；

//入栈
void StackPush(Stack* ps,  SDateType x)
{assert(ps);//判断空间够不够if (ps->capacity == ps->size){ps->capacity *= 2;SDateType* new = (SDateType*)realloc(ps->a,sizeof(SDateType) * (ps->capacity));if (new == NULL)perror("realloc failed!");ps->a = new;}//入栈ps->a[ps->size] = x;ps->size++;
}

3）出栈

出栈不需要对栈顶元素进行处理，只需要将栈内元素个数-1即可，将栈顶元素看作无效数据；

//出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->size);ps->size--;
}

4）获得栈顶元素

//获得栈顶元素
SDateType StackTop(Stack* ps)
{assert(ps->a);assert(ps->size);return ps->a[ps->size - 1];
}

5)获得栈中有效元素个数

//获得栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->size;
}

6）检测栈是否为空

//检测栈是否为空
bool IsStackEmpty(Stack* ps)
{assert(ps);if (ps->size == 0)return true;return false;
}

7）销毁栈

将malloc的空间释放，将顺序表中的变量制空。

//栈的销毁
void StackDestory(Stack* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

数据结构之队列 

定义

队列：也是一种特殊的线性表，其特点是只允许在一端(队尾)进行插入，另一端(队头)进行删除。队列的数据结构必须遵循先入先出(先进入的先出来原则。就好比车辆进站加油，先进入的车会先出来。

入队：向队尾添加元素；

出队：将队头的元素删去；

实现方式

与栈相同，队列也有两种实现方式；

1）顺序表实现，用顺序表可以直接找到队尾，进行入队，但是在出队的时候将队头元素删除后，要将后面元素整体向前移动，效率低。

2）链表实现，用链表实现的时候，只要记录了尾节点，头节点就可以直接对队列进行入队和出队操作，链表实现的效率更高，此处以链表实行为例。

基本功能实现

1）定义，初始化队列

定义两个结构体，1）链表；2）用于记录头节点，尾节点及链表长度的结构体。

//定义队列
typedef int QDateType;typedef struct QueNode
{QDateType date;struct QueNode* next;
}QueNode;typedef struct Queue
{QueNode* front;QueNode* tail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->front = pq->tail = NULL;pq->size = 0;
}

2）入队

向队尾添加元素；

//入队
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//创建新节点QueNode* newnode = (QueNode*)malloc(sizeof(QueNode));newnode->date = x;newnode->next = NULL;if (pq->front == NULL)pq->front = pq->tail = newnode;else{pq->tail->next = newnode;pq->tail = pq->tail->next;}
}

3）出队

将队头元素删去。

//出队
void QueuePop(Queue* pq)
{assert(pq);//记录队头QueNode* del = pq->front;pq->front = pq->front->next;free(del);del = NULL;
}

4）获得队列头部元素

//获得队列头部元素
QDateType QueTop(Queue* pq)
{assert(pq);assert(pq->size);return pq->front->date;
}

5）获得队尾元素

//获得队尾元素
QDateType QueTail(Queue* pq)
{assert(pq);assert(pq->size);return pq->tail->date;
}

6）队列元素个数

//获得队列元素个数
int QueSize(Queue* pq)
{assert(pq);return pq->size;
}

7）队列是否为空

//判断队列是否为空
bool IsQueueEmpty(Queue* pq)
{assert(pq);if (pq->size == 0)return true;return false;
}

8）销毁队列

//销毁队列
void QueDestory(Queue* pq)
{assert(pq);//要销毁队列的每一个元素while (!IsQueueEmpty){QueuePop(pq);}pq->front = pq->size = NULL;
}

栈和队列练习

1.1 有效括号

20. 有效的括号 - 力扣（LeetCode）

用栈的先入后出性质

遍历字符串，对于左括号入栈，当遇到右括号的时候，出栈，将出栈元素和左括号进行对比，看是否配对。

//有效括号
bool isValid(char* s) {Stack sta;StackInit(&sta);char* cur = s;while(*cur!='\0'){//判断是否是左括号if ((*cur) == '(' || (*cur) == '{' || (*cur) == '['){StackPush(&sta, *cur);cur++;}//将左括号和右括号进行对比else{if (IsStackEmpty(&sta))return false;char left = StackTop(&sta);StackPop(&sta);  //取出栈顶元素if ((left == '(' && (*cur) != ')') ||(left == '{' && (*cur) != '}') ||(left == '[' && (*cur) != ']'))return false;cur++;}}if(!IsStackEmpty(&sta))return false;   //栈中还有元素return true;
}


http://www.ppmy.cn/server/161112.html

相关文章

JupyterLab 安装以及部分相关配置

JupyterLab 安装以及部分相关配置

安装 JupyterLab pip install jupyter启动 JupyterLab jupyter lab [--port <指定的端口号>] [--no-browser] # --port 指定端口 # --no-browser 启动时不打开浏览器安装中文 首先安装中文包 pip install jupyterlab-language-pack-zh-CN安装完成后重启 JupyterLab 选…
阅读更多...
MySQL为什么使用B+树？B+树和B树的区别

MySQL为什么使用B+树？B+树和B树的区别

MySQL为什么使用B树&#xff1f;B树和B树的区别 在数据库系统中&#xff0c;索引是提高数据检索效率的关键技术。MySQL 默认使用 B树 作为索引的数据结构&#xff0c;而不是 B 树或其他数据结构。这是因为 B树在范围查询、磁盘 I/O 效率以及数据存储方式等方面具有显著优势。 …
阅读更多...
08-ArcGIS For JavaScript-通过Mesh绘制几何体（Cylinder，Circle，Box，Pyramid）

08-ArcGIS For JavaScript-通过Mesh绘制几何体（Cylinder，Circle，Box，Pyramid）

目录 概述代码实现1、Mesh.createBox2、createPyramid3、Mesh.createSphere4、Mesh.createCylinder 完整代码 概述 对于三维场景而言&#xff0c;二位的点、线、面&#xff0c;三维的圆、立方体、圆柱等都是比较常见的三维对象&#xff0c;在ArcGIS For JavaScript中我们知道点…
阅读更多...
【技术洞察】2024科技绘卷：浪潮、突破、未来

【技术洞察】2024科技绘卷：浪潮、突破、未来

涌动与突破 2024年&#xff0c;科技的浪潮汹涌澎湃&#xff0c;人工智能、量子计算、脑机接口等前沿技术如同璀璨星辰&#xff0c;方便了大家的日常生活&#xff0c;也照亮了人类未来的道路。这一年&#xff0c;科技的突破与创新不断刷新着人们对未来的想象。那么回顾2024年的科…
阅读更多...
软键盘显示/交互问题

软键盘显示/交互问题

日常开发会经常遇到软键盘覆盖界面布局的问题,比如:我有一个fragment,中心布局了EditText,正常情况是 ,当点击这个EditText的时候,输入法会弹出来,但是输入控件会覆盖掉EditText,看不到输入的内容,这种应该怎么处理呢 这个问题通常是因为当软键盘弹出时&#xff0c;EditText 被…
阅读更多...
【Qt】事件

【Qt】事件

事件 事件的处理鼠标事件键盘事件定时器窗口事件 用户进行的各种操作&#xff0c;就会产生事件。给事件关联上函数或处理逻辑&#xff0c;当事件触发时&#xff0c;就能执行对应的代码。多数场景下&#xff0c;程序和用户的交互可以通过 “信号槽” 完成&#xff0c;但在某些特…
阅读更多...
《罗宾逊-旅途VR》Build2108907官方学习版

《罗宾逊-旅途VR》Build2108907官方学习版

《罗宾逊-旅途VR》官方版 https://pan.xunlei.com/s/VODiY5gn_fNxKREdVRdwVboCA1?pwdsh3f# 从第一人称的角度进行探索&#xff0c;玩家将遇到一系列恐龙和生物&#xff0c;这些恐龙和生物会对它们在泰森三世生态系统中的存在做出反应。强调与周围环境的互动&#xff0c;鼓励玩…
阅读更多...
Selenium-WEB自动化测试环境配置

Selenium-WEB自动化测试环境配置

Selenium-WEB-Python-Mac开发环境 一、安装selenium 打开终端 ->pip安装&#xff08;安装命令&#xff1a;pip3 install selenium&#xff09; 安装成功后&#xff0c;可以通过&#xff08; pip3 show selenium &#xff09;命令查看安装的selenium版本信息 二、安装浏览…
阅读更多...
最新文章

Copyright @ 2022~2023