数据结构严蔚敏版精简版-栈和队列以及c语言代码实现

2024-06-09 15:44
文章标签 语言 代码 实现 数据结构 队列 精简版 严蔚敏版

本文主要是介绍数据结构严蔚敏版精简版-栈和队列以及c语言代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1栈的定义和特权

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。

注：虽然说栈的实现就是一端插入和删除，但不一定是在“表尾”，这个“表尾”是广义的。

头插法实现链栈

尾插法实现链栈

因此，对栈来说，表尾端有其特殊含义，称为栈顶(top),相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。

2队列的定义和特权

和栈相反，队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表 的一端进行插入，而在另一端删除元素。

如果入队序列为1，2，3，4出队序列也为1，2，3，4

队列在程序设计中也经常出现。一个最典型的 例子就是操作系统中的作业排队。在允许多道程序 运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求 输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出 做输出操作。凡是申请输出的作业都从队尾进入队列。

python实现LRU置换算法和先进先出算法

2.1循环队列

假设当前队列分配的最大空间为6,则当队列处于图d所示的状态时不可再继续 插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实 上，此时队列的实际可用空间并未占满，所以这种现象称 为“假溢出＂。这是由＂队尾入队，队头出队”这种受限制 的操作造成的。

最常用的方式是少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队 空的条件不变， 即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等 千头指针，则认为队满。因此，在循环队列中队空和队满的条件是：

队空的条件： Q.front = Q.rear

队满的条件： (Q rear+ 1)%M心CQSIZE= Q.front

入队尾指针变化：Q.front=(Q.front+1)%m

出队头指针变化：Q.front=(Q.front+1)%m

void EnQueue(Queue *Q,Elemtype x)//入队 
{if((Q->tail+1)%MAX_QUEUE==Q->front){printf("已满\n");return;}Q->base[Q->tail]=x;Q->tail=(Q->tail+1)%MAX_QUEUE;printf("%d已经入队\n",x); 
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);Q->front=(Q->front+1)%MAX_QUEUE;
}

3栈和队列的实现c语言

3.1顺序栈的实现

#define STACK_INC_SIZE 3
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include <iostream>
#define MAX_SIZE 8#define Elemtype char 
typedef struct stack{Elemtype *base;int top;int stacksize;
}Sqstack;void Initstack(Sqstack *S)//初始化 
{S->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_SIZE);S->stacksize=8;S->top=0; } void show(Sqstack *S)//查看栈内元素 {for(int i=S->top-1;i>=0;i--){printf("%d\n",S->base[i]);}}bool IsFull(Sqstack *S)//判断是否满 {return S->top>=S->stacksize; } bool IsEmpty(Sqstack *S)//判断是否为空栈 {return S->top==0;}bool Inc(Sqstack *s)//栈满了则扩容，如果内存不够扩容则失败 {Elemtype *newbase=(Elemtype*)realloc(s->base,sizeof(Elemtype)*(s->stacksize+STACK_INC_SIZE));if(newbase==NULL){printf("满了");return false; }s->base=newbase;s->stacksize+=STACK_INC_SIZE;return true;}void push(Sqstack *S,Elemtype x)//入栈 {if(IsFull(S)&&!Inc(S)){printf("满了,%d不能入栈\n",x);return;}S->base[S->top++]=x;}void pop(Sqstack *S)//出栈 {if(IsEmpty(S)){printf("空的");return;}S->top--;}
Elemtype Gettop(Sqstack *S) //获取栈顶元素 {if(IsEmpty(S)){return false;}return S->base[S->top-1];}int length(Sqstack *S)//长度 {return S->top;}void clear(Sqstack *S)//清空栈 {S->top=0;}void destory(Sqstack *S)//销毁栈 {free(S->base);S->base=NULL;S->stacksize=S->top==0;}void conversion(int value)//进制转换 
{	Sqstack s;Initstack(&s);while(value){push(&s,value%8);value=value/8;}while(!IsEmpty(&s))
{	int v;v=Gettop(&s);pop(&s);printf("%d",v);}	
}bool Cheack(char *str)//括号匹配 
{ char v;Sqstack s;Initstack(&s);while(*str !='0'){if(*str=='['||*str=='('){push(&s,*str);}else if(*str==']'){v=Gettop(&s);if(v!='[')return false;pop(&s);}else if(*str==')'){v=Gettop(&s);if(v!='(')return false;pop(&s);}++str;}return IsEmpty(&s);
}
int main(void)
{char *str="[())]";bool flag=Cheack(str);if(flag){printf("OK\n");}else{printf("False");}} 
/*
int main()
{Elemtype Itim;Sqstack S;Initstack(&S);//conversion(13456);/*for(int i=1;i<=10;i++)push(&S,i);show(&S);Itim=Gettop(&S);printf("%d出栈\n",Itim);pop(&S);show(&S);}*/

3.2队列的实现

由于队列的实现比较简单，文章的开头就给出了2种链栈的实现方式，由于循环队列一直是队列的热门考点，这里只实现循环队列。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>#define Elemtype int
#define MAX_QUEUE 8//最大数量为8个 
typedef struct Queue{Elemtype *base;//基地址 int front;//队头头 int tail;//队尾 
}Queue;void InitQueue(Queue *Q)//初始化队列 
{Q->base=(Elemtype*)malloc(sizeof(Elemtype)*MAX_QUEUE);Q->front=Q->tail=0;
}void EnQueue(Queue *Q,Elemtype x)//入队 
{if((Q->tail+1)%MAX_QUEUE==Q->front){printf("已满\n");return;}Q->base[Q->tail]=x;Q->tail=(Q->tail+1)%MAX_QUEUE;printf("%d已经入队\n",x); 
}void show(Queue *Q)//展示队列 
{for(int i=Q->front;i!=Q->tail;){printf("%d  ",Q->base[i]);i=(i+1)%MAX_QUEUE;}printf("\n");
}
void DeQueue(Queue *Q)//出队 
{	printf("%d出队\n",Q->base[Q->front]);Q->front=(Q->front+1)%MAX_QUEUE;
}
int lenQueue(Queue *Q) 
{return (Q->tail-Q->front);
}
void Gethead(Queue *Q,Elemtype *x)//获取对头元素 
{
if(Q->front==Q->tail)return;*x=Q->base[Q->front];
}
void ClearQueue(Queue *Q)//清空 
{Q->front=Q->tail=0;
}
void DestroyQueue(Queue *Q)//销毁 
{ClearQueue(Q);free(Q->base);Q->base=NULL;
}int main()
{	int x;Queue Q;InitQueue(&Q);EnQueue(&Q,1);EnQueue(&Q,2);EnQueue(&Q,3);EnQueue(&Q,4);DeQueue(&Q);show(&Q);printf("队列长%d\n",lenQueue(&Q));Gethead(&Q,&x);printf("队头元素为%d\n",x);
}

这篇关于数据结构严蔚敏版精简版-栈和队列以及c语言代码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1045601。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2