[数据结构] 队列 (C语言)

队列

队列基本概念

队列( queue )是一种特殊的线性表结构,只从队尾插入新的元素,并且只从队首弹出元素。一般将队尾称为 rear,队首称为 front

队列基本操作

(1)入队:从队尾 rear 插入新元素;
(2)出队:从队首 front 弹出元素。

队列的特性

队列遵循 先进先出 的原则。比如元素 1、2、3、4、5 依次入队,且中途不存在出队过元素再次入队或其他元素入队,出队顺序为 1、2、3、4、5



循环顺序队列

循环顺序队列基本概念

顺序队列是用数组实现的队列,但是由于定义的数组的空间有限,可以想象一下,当队首 front 和 队尾 rear 经过一系列操作都往后移动时,之前所使用到的空间都不会再被使用了,这造成了空间上的浪费。

所以定义顺序队列往往采用更加高效的 循环顺序队列,其基本上就是在顺序队列的基础上加了一点小小的修改。

循环顺序队列的入队操作

循环顺序队列入队操作图解

初始状态下的循环顺序队列

元素1入队

元素2、3、4、5入队

循环顺序队列入队操作代码

//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
    if((Q->rear + 1) % MAXSIZE == Q->front){
	printf("队列已满\n");
	return;
    }
    Q->data[Q->rear] = e;               //在队尾指向的地址赋值
    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1
}


循环顺序队列的出队操作

循环顺序队列出队操作图解

元素1出队

元素2、3、4、5出队

循环顺序队列出队操作代码

//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
    if(IsEmpty(Q)){
	printf("队列中无元素\n");
	return;
    }
    *e = Q->data[Q->front];             //取出队首指针指向的地址元素
    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}

循环顺序队列中的循环示例

入队

此时队列rear虽然指向数组的最后,但循环操作可以使其重复利用之前使用的空间。

出队

类似的此时队列front指向数组的最后



循环顺序队列完整程序

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000

typedef int Elemtype;
typedef struct SqQueue{
	
    Elemtype data[MAXSIZE];
    int front;           //队列前指针
    int rear;            //队列后指针

}SqQueue;

//初始化
void Create_SqQueue(SqQueue *Q){
    Q->front = Q->rear = 0;
}

//判断队列是否为空
bool IsEmpty(SqQueue *Q){
    return Q->front == Q->rear;
}

//求得队列长度
int SqQueue_Length(SqQueue *Q){
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

//队列元素入队
void Enter_SqQueue(SqQueue *Q, int e){
    if((Q->rear + 1) % MAXSIZE == Q->front){
	printf("队列已满\n");
	return;
    }
    Q->data[Q->rear] = e;               //在队尾指向的地址赋值
    Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针进1
}

//队列元素出队
void Depart_SqQueue(SqQueue *Q, int *e){
    if(IsEmpty(Q)){
	printf("队列中无元素\n");
	return;
    }
    *e = Q->data[Q->front];             //取出队首指针指向的地址元素
    Q->front = (Q->front + 1) % MAXSIZE;//队首指针进1
}

//取队首
int Get_front(SqQueue *Q){
    if(IsEmpty(Q)){
	printf("队列为空\n");
	return -1;
    }
    return Q->data[Q->front];
}


int main(){
    SqQueue myQueue;
    Elemtype a[5] = {35, 30, 11, 23, 9};

    Create_SqQueue(&myQueue);
    for(int i = 0; i < 5; i++)
        Enter_SqQueue(&myQueue, a[i]);

    Elemtype e;
    Depart_SqQueue(&myQueue, &e);
    printf("出队元素: %d\n", e);

    printf("元素22入队并将所有元素出队: \n");
    Enter_SqQueue(&myQueue, 22);

    while(!IsEmpty(&myQueue)){
    	printf("%d ", Get_front(&myQueue));
    	Depart_SqQueue(&myQueue, &e);
    }

    return 0;
}

程序运行结果



链队列

链队列基本概念

链队列是链式的队列结构,其拥有一个 front 指针作为队首,一般队首 front 是不带数据的;还有一个 rear 指针作为队尾,队尾 rear 指向队列的最后一个元素。链队列的操作和链表也有一些相似之处。

链队列的入队操作

链队列入队操作图解

初始状态下的链队列

元素1入队

元素2、3入队

链队列入队操作代码

//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
    Linknode *node = (Linknode*)malloc(sizeof(Linknode));
    node->data = e;
    node->next = NULL;

    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node
    Q->rear = node;           //尾指针重新指向新节点node
}

链队列的出队操作

链队列出队操作图解

元素1出队

链队列出队操作代码

当链队列只有一个元素并且将其出队时,需要特判一下,将链队列置于空队列的状态。

//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
    if(Q->rear == Q->front) return;
    Linknode *p;
    p = Q->front->next;       //要删除的节点暂存给p
    *e = p->data;             //取出删除队头节点的数据
    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
	
    if(Q->rear == p)          //当队列只有一个元素的情况
    	Q->rear = Q->front;   
    free(p);
}


链队列完整程序

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int Elemtype;
//队列节点结构
typedef struct Linknode{

    Elemtype data;             //队列节点数据域
    struct Linknode *next;     //队列next指针域
	
}Linknode;

//链队列整体结构
typedef struct LinkQueue{

    Linknode *front;           //链队列首指针  队首指针不带数据
    Linknode *rear;            //链队列尾指针

}LinkQueue;

//初始化创建链队列
void Create_LinkQueue(LinkQueue *Q){
    Q->front = Q->rear = (Linknode*)malloc(sizeof(Linknode));
    Q->front->next == NULL;
}

//链队列元素入队
void Enter_LinkQueue(LinkQueue *Q, int e){
    Linknode *node = (Linknode*)malloc(sizeof(Linknode));
    node->data = e;
    node->next = NULL;

    Q->rear->next = node;     //原先队列尾指针后继next指向新节点node
    Q->rear = node;           //尾指针重新指向新节点node
}

//链队列元素出队
void Depart_LinkQueue(LinkQueue *Q, int *e){
    if(Q->rear == Q->front) return;
    Linknode *p;
    p = Q->front->next;       //要删除的节点暂存给p
    *e = p->data;             //取出删除队头节点的数据
    Q->front->next = p->next; //队头节点的后继next直接跨过删除的节点指向其下一个节点
	
    if(Q->rear == p)          //当队列只有一个元素的情况
    	Q->rear = Q->front;  
    
    free(p);
}

//判断是否为空
bool IsEmpty(LinkQueue *Q){
    return Q->front == Q->rear;
}

//取队首
int Front_LinkQueue(LinkQueue *Q){
    if(IsEmpty(Q)){
	printf("队列为空\n");
	return -1;
    }
    return Q->front->next->data;
}

int main(){
    LinkQueue myQueue;
    Create_LinkQueue(&myQueue);

    Enter_LinkQueue(&myQueue, 1);
    Enter_LinkQueue(&myQueue, 2);
    Enter_LinkQueue(&myQueue, 3);
    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue));
    
    Elemtype e;
    Depart_LinkQueue(&myQueue, &e);
    printf("出队的元素为 %d \n", e);
    printf("当前队首元素为 %d \n", Front_LinkQueue(&myQueue)); 
   	
    printf("\n所有元素出队:\n");
    while(!IsEmpty(&myQueue)){
    	printf("%d ", Front_LinkQueue(&myQueue));
    	Depart_LinkQueue(&myQueue, &e);
    }

    return 0;
}

程序运行结果

一切都是命运石之门的选择,本文章来源于博客园,作者:Amαdeus,出处:http://www.cnblogs.com/MAKISE004/p/17063234.html,未经允许严禁转载

本文转载于网络 如有侵权请联系删除

相关文章

  • 运筹帷幄决胜千里,Python3.10原生协程asyncio工业级真实协程异步消费任务调度实践

      我们一直都相信这样一种说法:协程是比多线程更高效的一种并发工作方式,它完全由程序本身所控制,也就是在用户态执行,协程避免了像线程切换那样产生的上下文切换,在性能方面得到了很大的提升。毫无疑问,这是颠扑不破的业界共识,是放之四海而皆准的真理。  但事实上,协程远比大多数人想象中的复杂,正因为协程的“用户态”特性,任务调度权掌握在撰写协程任务的人手里,而仅仅依赖async和await关键字远远达不到“调度”的级别,有时候反而会拖累任务效率,使其在任务执行效率上还不及“系统态”的多线程和多进程,本次我们来探讨一下Python3原生协程任务的调度管理。  Python3.10协程库async.io的基本操作  事件循环(Eventloop)是原生协程库asyncio的核心,可以理解为总指挥。Eventloop实例提供了注册、取消和执行任务和回调的方法。  Eventloop可以将一些异步方法绑定到事件循环上,事件循环会循环执行这些方法,但是和多线程一样,同时只能执行一个方法,因为协程也是单线程执行。当执行到某个方法时,如果它遇到了阻塞,事件循环会暂停它的执行去执行其他的方法,与此同时为这个

  • SparkSql LogicalPlan的resolved变量

    在阅读SparkSql源码过程中,可能会遇到的小迷惑resolved主要用来标记当前LogicalPlan是否为经过了解析。//当前logicalplan中的所有的expressions都被解析了,并且该logicalplan的子节点也被解析,刚当前的logicalplan的resolved会返回true lazyvalresolved:Boolean=expressions.forall(_.resolved)&&childrenResolved 复制logicalplan分unresolvedlogicalplan和resolvedlogicalplan,resolved可以被子类重写。看两个案例UnresolvedRelationUnresolvedRelation是由ASTTree直接生成的unresolvedlogicalplan的节点,还未被解析,所以resolved被赋值为falseAggregateAggregate有"两重身份",不像UnresolvedRelation一定是未解析的。Aggregate即可以unresolved也

  • 三分钟迁移 antd@4

    文章作者:陈帅等13w人 文章来源:https://zhuanlan.zhihu.com/p/109067115antd@4rc发布已经有一段时间了(大概已经两周了),官网[1]也已同步放出。最为一个酷爱尝鲜的人,当然要第一时间安装升级。在咨询了豆酱老师得到了api不会修改的承诺之后,我已经在自己的项目中迁移完成。第一时间享受到了的antd@4各种优势。?升级点首先对我而言最大的改进在于性能,select,table和tree已经全面支持了虚拟滚动,作为了早早的使用了rc-tree来解决性能问题的人,antd@4中提供自然是更好不过了,毕竟自己写样式和动态是非常复杂的。重写的table和from解决很多遗留的疑难杂症,具体可以查看豆酱老师的antd@4系列文章[2],里面详细写了心路历程,在form中我们不需要使用getFieldDecorator和Form.create这两个方法。已Pro全区块为例,这两个方法分别出现了87和22次,在我自己的一个维护项目中找到了142个getFieldDecorator,更不用说为了封装组件getFieldDecorator被当成props传来传去

  • Java内存分配之堆、栈和常量池

    java内存分配主要包括以下几个区域:寄存器:我们在程序中无法控制栈:存放基本的类型数据和对象的引用,但对象本身不存放在栈中,而是存放在堆中堆:存放用new产生的数据静态域:存放在对象中用static定义的静态成员常量池:存放常量非RAM(随机存取存储器)存储java内存分配中的栈在函数中定义的一些基本类型的变量数据和对象的引用变量都在函数的栈内存中分配。当在一段代码定义一个变量时,java就在栈中为这个变量分配内存空间,当该变量退出该作用域后,java会自动释放掉为该变量所分配的内存空间,该内存空间可以立即被另做他用。 java内存分配中的堆堆内存用来存放由new创建的对象和数组。在堆中分配的内存,由java虚拟机的自动垃圾回收期来管理。 在堆中产生了一个数组或对象后,还可以在栈中定义一个特殊的变量,让栈中这个变量的取值等于数组或对象在堆内存中的首地址,栈中的这个变量就成了数组或对象的引用变量。引用变量就相当于是为数组或对象起一个名称,以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。应用变量就相当于是为了数组或对象起的一个名称。 引用变量是普通的变量,定义时在栈中分配,引

  • 多台Linux服务器执行同样的命令

    在Spark安装和运行时,比如zkServer.shstart这样的命令是需要所有服务器执行的,一个个复制粘贴回车肯定不够优雅,找个shell解决这个问题:#!/bin/bash if["$#"-ne1];then echo"USAGE:$0-fcmd" exit1 fi file_name='server.list' cmd_str=$1 cwd=$(pwd) cd$cwd serverlist_file="$cwd/$file_name" if[!-e$serverlist_file];then echo'server.listnotexist'; exit0; fi whilereadline do if[-n"$line"];then echo"DOING--->"$line"<---" sshroot@$line$cmd_str</dev/null>/dev/null if[$?-eq0

  • CSS画各种图形(五角星、吃豆人、太极图等)

    扇形CSS画各种图形(五角星、吃豆人、太极图等)扇形width:0; height:0; border-left:70pxsolidtransparent; border-right:70pxsolidtransparent; border-top:100pxsolidred; border-radius:50%;复制梯形CSS画各种图形(五角星、吃豆人、太极图等)梯形border-bottom:100pxsolidred; border-left:50pxsolidtransparent; border-right:50pxsolidtransparent; height:0; width:100px;复制平行四边形CSS画各种图形(五角星、吃豆人、太极图等)平行四边形width:150px; height:100px; transform:skew(20deg); background:red;复制五边形CSS画各种图形(五角星、吃豆人、太极图等)五边形#pentagon{ position:relative; width:54px; box-sizing:content-box;

  • ansible简单使用

    安装ansible的安装算简单的了,不要配置数据库,不用在远程操作的节点安装任何东西。只需要本机安装ansible即可。但是还是依赖一些基本python库。ansible |–jinja2 |–PyYAML |–paramiko |–pycrypto>=2.6 |–setuptools |–MarkupSafe |–cryptography>=1.1 |–pyasn1>=0.1.7 |–idna>=2.1 |–asn1crypto>=0.21.0 |–packaging |–six>=1.4.1 |–enum34 |–ipaddress |–cffi>=1.4.1 |–pyparsing |–pycparserhelloworld#echo"127.0.0.1">~/ansible_hosts #exportANSIBLE_HOSTS=~/ansible_hosts #ansibleall-mping--ask-pass [root@promote~]#cat~/ansible_hosts 127.0.0.1 [roo

  • RxJava2操作符之“Buffer”

    作用字面意思:缓冲 其实就是将要发射的数据封装成多个缓冲区,每次发射一个缓冲区示例用法Observable.just("one","two","three","four","five")//创建了一个有5个数字的被观察者 //3means,ittakesmaxofthreefromitsstartindexandcreatelist //1means,itjumpsonestepeverytime .buffer(3,1) .subscribe(getObserver());复制这里贴一下观察者,为了能更清晰的看到发射出来的内容,我们将每一个item都打印出来privateObserver<List<String>>getObserver(){ returnnewObserver<List<String>>(){ @Override publicvoidonSubscribe(Disposabled){ Log.d(TAG,"o

  • Java案例-数组求余问题

    案例分析要求定义一个int型数组a,包含100个元素,保存100个随机的4位数。再定义一个int型数组b,包含10个元素。统计a数组中的元素对10求余等于0的个数,保存到b[0]中;对10求余等于1的个数,保存到b[1]中,……依此类推。具体实现代码packageteacher01; /** *要求定义一个int型数组a,包含100个元素,保存100个随机的4位数。再定义一个int型数组b, *包含10个元素。统计a数组中的元素对10求余等于0的个数, *保存到b[0]中;对10求余等于1的个数,保存到b[1]中,……依此类推。 */ publicclassRemain{ publicstaticvoidmain(String[]args){ int[]a=newint[100]; //保存100个随机4位数到a中 for(inti=0;i<a.length;i++){ a[i]=(int)(1000*Math.random()); } //统计a数组中的元素对10求余的各个的数目 int[]b=newint[10]; intk,sum; for(intj=0;j<b.le

  • 重磅|微信发布2015微信生活白皮书

    今天在腾讯全球合作伙伴大会微信分论坛上,微信团队对外做了“微信·生活”的分享。现在,就让我们一起,从微信视角来看看中国人的喜怒哀乐、衣食住行。以下是报告的全文,你的感觉是这样么?绿点越亮,使用微信通话的数量也就越多。西湖是最微信签到最多的地方;中国香港是微信用户境外签到最多的地方。

  • MFS学习总结

    大家好,又见面了,我是你们的朋友全栈君。公司使用moosefs做图片存储,最近学习了一下,在此小小总结一下,主要分以下几部分:MFS概述、特性和新版改进MFS工作原理和设计架构MFS的安装、部署、配置MFS的高级特性MFS的性能测试MFS集群的维护MFS的常见问题和建议对策一、MFS概述、特性和新版改进MooseFS是一个分布式存储的框架,其具有如下特性:Free(GPL)通用文件系统,不需要修改上层应用就可以使用(那些需要专门api的dfs很麻烦!)。可以在线扩容,体系架构可伸缩性极强。(官方的case可以扩到70台了!)部署简单。(sa们特别高兴,领导们特别happy!)高可用,可设置任意的文件冗余程度(提供比raid1+0更高的冗余级别,而绝对不会影响读或者写的性能,只会加速!)可回收在指定时间内删除的文件(“回收站”提供的是系统级别的服务,不怕误操作了,提供类似oralce的闪回等高级dbms的即时回滚特性!)提供netapp,emc,ibm等商业存储的snapshot特性。(可以对整个文件甚至在正在写入的文件创建文件的快照)googlefilesystem的一个c实现。提供w

  • ui自动化测试脑图

     

  • 重写demo

    #!/usr/bin/envpython #-*-coding:utf-8-*- #@Author:zhangjun #@Date :2018/7/269:20 #@Desc :Description   import logging import logging.handlers import os import time   class logs(object):     def __init__(self):         self.logger = logging.getLogger("")         #设置输出的等级         LEVELS =&nb

  • 抓包工具fiddler抓取jmeter接口

    针对fiddler 抓取不到 jmeter请求的接口问题,解决办法如下: 需要设置jmeter里面的http默认请求【高级】代理ip----127.0.0.1   8888 不使用后,清空代理ip----127.0.0.1   8888     . . . -----------Miss.men---】百分百妖】---------

  • 多线程编程(六)——条件变量(Condition Variable)

    作者:StormZhu链接:https://www.jianshu.com/p/c1dfa1d40f53来源:简书著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 互斥锁std::mutex是一种最常见的线程间同步的手段,但是在有些情况下不太高效。 假设想实现一个简单的消费者生产者模型,一个线程往队列中放入数据,一个线程往队列中取数据,取数据前需要判断一下队列中确实有数据,由于这个队列是线程间共享的,所以,需要使用互斥锁进行保护,一个线程在往队列添加数据的时候,另一个线程不能取,反之亦然。用互斥锁实现如下: #include<iostream> #include<deque> #include<thread> #include<mutex> std::deque<int>q; std::mutexmu; voidfunction_1(){ intcount=10; while(count>0){ std::unique_lock<std::mutex>locker(mu); q.pu

  • 吼,数据结构上机课1

    唔,好歹是学到了新东西,不慌。 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #defineM20 typedefintElemType; typedefstructS{ ElemTypeelem[M]; intl; }S; intinits(S&L)//初始化 {L.l=0;return1;} intfinds(S&L,intx)//查找 { inti=0; while(i<L.l&&L.elem[i]!=x)i++; if(i>=L.l){printf("顺序表中不存在该元素!\n");return0;} elsereturni+1; } intinserts(S&L,inti,intx)//插入 { intj; if(L.l>=M){printf("顺序表已满,无法进行插入操作!\n");return0;} if(i<=0||i>L.l+1){printf("插入位置不正确!\n");return0

  • 第五周psp

    本周psp   本周进度条   代码累积折线图   博文字数累积折线图   饼状图  

  • Elasticsearch 索引模板 Index Template, 并通过模板创建索引

    ESversion:7.11 1.索引模板 1.1新建模板 CreateorupdateindextemplateAPI curl-u"username:pwd"-XPUT'127.0.0.1:9200/_index_template/friend_add_log?pretty'-H'Content-Type:application/json'-d' { "index_patterns":["friend_add_log*"], "priority":0, "template":{ "settings":{ "index":{ "analysis":{ "normalizer":{ "my_lowercase":{ "type":"custom", "filter":["lowercase"] } } } }, "number_of_shards":3, "number_of_replicas":0 }, "mappings":{ "properties":{ "self_im_id":{ "type":"keyword" }, "target_im_id":{ "type":"ke

  • 团队-象棋游戏-代码设计规范

    逆流而上 象棋游戏 代码规范 一、前言: 本编程规范适用于编写HTML/CSS代码,本规范并不是一个一成不变的必须严格遵守的条文,特殊情况下应灵活应对,做到变通。   二、HTML编码: HTML是一种标记语言,HTML没有任何真正的编程语言中的循环或是流程控制语句。然而,HTML代码的格式和风格是非常重要的,因为要经常对HTML代码进行维护和修改,因此HTML代码必须有很清晰的逻辑结构和布局,增强可读性,而使其易懂和易于维护。HTML代码本身是不区分大小写的,但是为了更好的统一代码布局,本项目中HTML文件标记都以小写为主。   三、软件: 编码同一使用HBuilder软件;浏览器统一使用最新版Google浏览器。   四、标记规范: 1.标记应对应编码,不可出现交叉编码,例:<p><font>内容</p></font>; 2.开始和关闭标记放在同一行内; 3.因不涉及联网,HTML文件头基本标记为:<!DOCTYPEhtml>; 4.对于标记内的属性,务必使用双引号包围; 5.对于i

  • Future的使用和理解

    最近遇到了一个场景,系统需要调另外一个接口来获取配置文件的内容,但是接口没有返回值,这种情况下,这样的接口就不能直接使用了。首先想到的是在接口实现中回调自身系统的接口,把配置文件传过来,我把过程简化成了一个流程图。    1.自身系统生成一个唯一单号,在数据库中保存一行,单号所在行的配置文件此时还是空 2.自身系统调用Jenkins,Jenkins执行脚本, 3.Jenkins去生产服务器上拉取配置文件,之后通过自身系统中的一个回调接口将配置文件内容传回到自身系统,保存在对应单号所在行;此时还有另外一件事在做,自身系统需要在超时时间为20s的情况下轮询单号对应的配置文件内容,如果内容已经被填充,那么立即返回结果。 这里,Jenkins执行获取配置文件的内容是一个耗时任务,只有配置文件通过回调接口调用成功后,任务才算是完成。所以自身系统不得不做轮询。 一开始,我们代码可以这样写在一个线程中。   publicCommonResponsegetNewestConfigFile(ApplyOrderRequestrequest){   BuildWithDe

  • 乱七八糟的流

    由于工作用到了各种流,所以就查阅资料总结一下,查询资料需谨慎啊,有的有错误,多看看。 首先了解两个概念:字节流和字符流。 字节流--传输过程中,传输数据的最基本单位是字节的流; 字符流--传输过程中,传输数据的最基本单位是字符的流。 字符流顾名思义读出来的都是字符,所以只用来知读文本文件,其他非文件的二进制文件当然要用字节流来读道了,最常见的就是一些流媒体文件,都是直接读取的字节。 写了一堆然后删掉了,直接贴上一篇链接,详细的雅痞,直接看就行了。 原文:https://www.cnblogs.com/progor/p/9357676.html   另外附加几句话为了理解(复制来的): (1)InputStream inputstream =new FileInputStream("fileName");//然后对InputStream进行读操作,为啥是读呢?可以把内存当作主体, 这是某个网友说的,你从硬盘往内存里Input东西就是读取数据咯。另外这里因为FileInputStream继承InputStream类//所以可以这样用。 (2)字符流

相关推荐

推荐阅读