博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构——队列
阅读量:5990 次
发布时间:2019-06-20

本文共 2885 字,大约阅读时间需要 9 分钟。

hot3.png

一、队列概念

队列时一种特殊的线性表,只允许在表的前端进行删除操作,而在表的后端进行插入操作,队列具有先进先出的特点。

队列的操作很简单,主要有以下几种常见的操作:

(1)初始化队列:创建一个队列

(2)进队列:将一个元素添加到队尾

(3)出队列:将队头元素取出,同时删除该元素,使下一个元素成为对头

(4)获取队列第一元素:将队头元素取出,不删除该元素

(5)获取队列长度:根据队头和队尾计算出队列中元素的数量

 

二、顺序队列实现

    将队列用顺序存储方式保存时,在内存中申请一片区域用来保存元素,当第一个元素A进入队列时,因是空列队,因此元素A将排在队头,接着B、C、D顺次进入队列,就得到如图所示的队列。其中head指向队头,以指示队头元素出队操作,tail指向队尾,以指示新增元素进入队列。如下图所示:

    执行一次出队操作,元素A将出队,这时第2个元素B将成为队头,head指针将指向该元素如果要将元素E入队,则是将其放入tail指针指向元素的后一个位置(如下图为5的单元),并使tail指针指向序号为5的单元。

(1)定义顺序队列的结构

#define QUEUEMAX 15typedef struct{	DATA data[QUEUEMAX];	int head;	int tail;} SeqQueue;

(2)初始化队列

SeqQueue *SeqQueueInit(){	SeqQueue *q;	if (q=(SeqQueue *)malloc(sizeof(SeqQueue))) {		q->head = 0;		q->tail = 0;		return q;	}	return NULL;}

(3)释放队列

void SeqQueueFree(SeqQueue *q){	if (q)		free(q);}

(4)获取队列状态

/**判断队列是否为空*/int SeqQueueIsEmpty(SeqQueue *q){	return (q->head == q->tail);}/**判断队列是否已满*/int SeqQueueIsFull(SeqQueue *q){	return (q->tail == QUEUEMAX);}/**获取队列的长度*/int SeqQueueLen(SeqQueue *q){	return (q->tail - q->head);}

(5)入队操作

int SeqQueueIn(SeqQueue *q, DATA data){	if (SeqQueueIsFull(q)) {		printf("队列已满!\n");		return 0;	}	q->data[q->tail++] = data;	return 1;}

(6)出队操作

DATA *SeqQueueOut(SeqQueue *q){	if (SeqQueueIsEmpty(q)) {		printf("队列已空!\n");		return NULL;	}	return &(q->data[q->head++]);}

(7)获取队头元素

DATA *SeqQueuePeek(SeqQueue *q){	if (SeqQueueIsEmpty(q)) {		printf("队列已空!\n");		return NULL;	}	return &(q->data[q->head]);}

三、循环队列

    由于每次出队后,队头的指针都向后移动,这时候就会出现一个问题,就是假溢出。如下图所示:

tail已指向队尾,这时进行入队操作时,虽然前面还有空位置,但仍然显示队列已满。为了解决这个问题,就提出了循环队列。

循环队列就是将队列的首尾相连构成一个环形区域,当在第n个位置进行元素的入队操作后,下一个地址就翻转为1

循环队列结构图:

在循环队列中,主要需要计算队尾tail和队头head的序号

以入队操作为例:

1、将队尾序号加1,即tail=tail+1

2、若tail=n+1,则tail=1

其实前2步,可以使用表达式tail=(tail+1)%n

3、若head=tail,即队尾和队头重合了,表示队列已满提示队列溢出

4、若未溢出,将元素入队即可

(1)定义循环队列的结构 

#define QUEUEMAX 15typedef struct{	DATA data[QUEUEMAX];	int head;	int tail;} CycQueue;

(2)初始化队列

CycQueue *CycQueueInit(){	CycQueue *q;	if (q=(CycQueue *)malloc(sizeof(CycQueue))) {		q->head = 0;		q->tail = 0;		return q;	}	return NULL;}

(3)释放队列

void CycQueueFree(CycQueue *q){	if (q)		free(q);}

(4)获取队列状态

/**判断队列是否为空*/int CycQueueIsEmpty(CycQueue *q){	return (q->head == q->tail);}/**判断队列是否已满*/int CycQueueIsFull(CycQueue *q){	return ((q->tail+1)%QUEUEMAX == q->head);}/**获取队列的长度*/int CycQueueLen(CycQueue *q){	int n;	n = q->tail - q->head;	if (n < 0) {		n = QUEUEMAX + n;	}	return n;}

(5)入队操作

int CycQueueIn(CycQueue *q, DATA data){	if (CycQueueIsFull(q)) {		printf("队列已满!\n");		return 0;	}	q->tail = (q->tail+1)%QUEUEMAX;	q->data[q->tail] = data;	return 1;}

(6)出队操作

DATA *CycQueueOut(CycQueue *q){	int head;	if (CycQueueIsEmpty(q)) {		printf("队列已空!\n");		return NULL;	}	head = q->head;	q->head = (q->head +1)%QUEUEMAX;	return &(q->data[head]);}

(7)获取队头元素

DATA *CycQueuePeek(CycQueue *q){	if (CycQueueIsEmpty(q)) {		printf("队列已空!\n");		return NULL;	}	return &(q->data[q->head]);}

转载于:https://my.oschina.net/wangande2014/blog/687230

你可能感兴趣的文章
mysql a-b复制常见错误
查看>>
手把手教人安装ISA2006设定
查看>>
Storm笔记整理(五):可靠性分析、定时任务与Storm UI参数详解
查看>>
centos7.2 redis安装及java测试
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
亲情爱情难两全
查看>>
全面拥抱“后ERP”时代
查看>>
在Word2010文档中显示图片框
查看>>
为什么采用达龙平台实施桌面虚拟化更合适?
查看>>
javascript显示中文时间的小例子
查看>>
OpenGL进阶(十三) - GLSL光照(Lighting)
查看>>
stm32 获取有效字符串
查看>>
svn服务器搭建
查看>>
我通过高项啦
查看>>
收藏:JavaMail使用SSL遇到安全证书问题
查看>>
我的友情链接
查看>>
小程序员应该提防的公司小陷阱
查看>>
我的友情链接
查看>>
zabbix 邮件报警配置
查看>>