开发者社区> ghost丶桃子> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

队列的存储结构和常见操作(c 语言实现)

简介:
+关注继续查看

一、队列(queue)

队列和栈一样,在实际程序的算法设计和计算机一些其他分支里,都有很多重要的应用,比如计算机操作系统对进程 or 作业的优先级调度算法,对离散事件的模拟算法,还有计算机主机和外部设备运行速度不匹配的问题解决等,很多很多。其实队列的本质还是线性表!只不过是一种特殊的或者说是受限的线性表,是这样的:

1)、限定在表的一端插入、另一端删除。 插入的那头就是队尾,删除的那头就是队头。也就是说只能在线性表的表头删除元素,在表尾插入元素。形象的说就是水龙头和水管,流水的水嘴是队头,进水的泵是队尾,管子中间不漏水不进水。这样呲呲的流动起来,想想就是这么个过程。

2)、先进先出 (FIFO结构)。显然我们不能在表(队列)的中间操作元素,只能是在尾部进,在头部出去,还可以类似火车进隧道的过程。(first in first out = FIFO 结构)

注意,当队列没有元素的时候,我们就说队列是空队列。

 

1、双端队列

double-ended queue:限定插入和删除在表的两端进行,也是先进先出 (FIFO)结构,类似铁路的转轨网络。实际程序中应用不多。

这种结构又细分为三类:

1)、输入受限的双端队列:一个端点可插入和删除,另一个端点仅可删除。

2)、输出受限的双端队列:一个端点可插入和删除,另一个端点仅可插入。   

3)、等价于两个栈底相连接的栈:限定双端队列从某个端点插入的元素,只能在此端点删除。

 

2、链队(有链的地方,就有指针)

用链表表示的队列,限制仅在表头删除和表尾插入的单链表。一个链队列由一个头指针和一个尾指针唯一确定。(因为仅有头指针不便于在表尾做插入操作)。为了操作的方便,也给链队列添加一个头结点,因此,空队列的判定条件是:头指针和尾指针都指向头结点。

之前的链式结构,总是使用一个结点的结构来表示链表,其实不太方便,这里使用新的存储结构。定义一个结点结构,和一个队列结构。两个结构嵌套。

复制代码
 1 #ifndef queue_Header_h
 2 #define queue_Header_h
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 #include <stdbool.h>
 6 
 7 //队列的结点结构
 8 typedef struct Node{
 9     int data;
10     struct Node *next;
11 } Node, *Queue;
12 
13 //队列的结构,嵌套
14 typedef struct{
15     Queue front;
16     Queue rear;
17 } LinkQueue;
18 
19 //初始化
20 //开始必然是空队列,队尾指针和队头指针都指向头结点
21 void initQueue(LinkQueue *queue)
22 {
23     //初始化头结点
24     queue->front = queue->rear = (Queue)malloc(sizeof(Node));
25     
26     if (NULL == queue->front) {
27         exit(0);
28     }
29     
30     queue->front->next = NULL;
31 }
32 
33 //判空
34 bool isEmpty(LinkQueue queue)
35 {
36     return queue.rear == queue.front ? true : false;
37 }
38 
39 //入队,只在一端入队,另一端出队,同样入队不需要判满
40 void insertQueue(LinkQueue *queue, int temp)
41 {
42     Queue q = (Queue)malloc(sizeof(Node));
43     
44     if (NULL == q) {
45         exit(0);
46     }
47     //插入数据
48     q->data = temp;
49     q->next = NULL;
50     //rear 总是指向队尾元素
51     queue->rear->next = q;
52     queue->rear = q;
53 }
54 
55 //出队,需要判空
56 void deleteQueue(LinkQueue *queue)
57 {
58     Queue q = NULL;
59     
60     if (!isEmpty(*queue)) {
61         q = queue->front->next;
62         queue->front->next = q->next;
63         //这句很关键,不能丢
64         if (queue->rear == q) {
65             queue->rear = queue->front;
66         }
67         
68         free(q);
69     }
70 }
71 
72 //遍历
73 void traversal(LinkQueue queue)
74 {
75     int i = 1;
76     Queue q = queue.front->next;
77     
78     while (q != NULL) {
79         printf("队列第%d个元素是:%d\n", i, q->data);
80         q = q->next;
81         i++;
82     }
83 }
84 
85 //销毁
86 void destoryQueue(LinkQueue *queue)
87 {
88     while (queue->front != NULL) {
89         queue->rear = queue->front->next;
90         free(queue->front);
91         queue->front = queue->rear;
92     }
93     
94     puts("销毁成功!");
95 }
96 
97 #endif
复制代码

 测试

复制代码
 1 #include "queue.h"
 2 
 3 int main(int argc, const char * argv[])
 4 {
 5     LinkQueue queue;
 6     puts("初始化队列 queue");
 7     initQueue(&queue);
 8     traversal(queue);
 9     
10     puts("队尾依次插入0 1 2 3");
11     insertQueue(&queue, 0);
12     insertQueue(&queue, 1);
13     insertQueue(&queue, 2);
14     insertQueue(&queue, 3);
15     traversal(queue);
16     
17     puts("先进先出,删除队列从头开始, 0 ");
18     deleteQueue(&queue);
19     traversal(queue);
20     
21     puts("先进先出,删除队列从头开始, 1 ");
22     deleteQueue(&queue);
23     traversal(queue);
24     
25     puts("先进先出,删除队列从头开始, 2 ");
26     deleteQueue(&queue);
27     traversal(queue);
28     
29     puts("先进先出,删除队列从头开始, 3");
30     deleteQueue(&queue);
31     traversal(queue);
32     
33     destoryQueue(&queue);
34     return 0;
35 }
复制代码

结果:

初始化队列 queue

队尾依次插入0 1 2 3

队列第1个元素是:0

队列第2个元素是:1

队列第3个元素是:2

队列第4个元素是:3

先进先出,删除队列从头开始, 0 

队列第1个元素是:1

队列第2个元素是:2

队列第3个元素是:3

先进先出,删除队列从头开始, 1 

队列第1个元素是:2

队列第2个元素是:3

先进先出,删除队列从头开始, 2 

队列第1个元素是:3

先进先出,删除队列从头开始, 3

销毁成功!

Program ended with exit code: 0

 

3、顺序队列

限制仅在表头删除和表尾插入的顺序表,利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的,所以也要设头、尾指针。  

初始化时的头尾指针,初始值均应置为 0。 入队尾指针增 1 ,出队头指针增 1 。头尾指针相等时队列为空,在非空队列里,头指针始终指向队头元素,尾指针始终指向队尾元素的下一位置。

初始为空队列,那么头尾指针相等。

入队,那么尾指针加1,头指针不变。先进先出,J1先进队,则 rear+1,尾指针始终指向队尾元素的下一位!如,J2进队,rear 继续+1,J3进队,尾指针继续加1,如图

 

出队,则尾指针不变,头指针加1,注意这里都是加1,先进先出原则,J1先删除,front+1,指向了 J2,J2删除,front+1指向了 J3,如图

 

最后,J3删除,则头指针再次和尾指针相等,说明队列空了。如图

在顺序队列中,当尾指针已经指向了队列的最后一个位置的下一位置时,若再有元素入队,就会发生“溢出”。如图位置,再次入队,就会溢出。

 

4、循环队列的诞生

顺序队列的 “假溢出” 问题:队列的存储空间未满,却发生了溢出。很好理解,比如 rear 现在虽然指向了最后一个位置的下一位置,但是之前队头也删除了一些元素,那么队头指针经历若干次的 +1 之后,遗留下了很多空位置,但是顺序队列还在傻乎乎的以为再有元素入队,就溢出呢!肯定不合理。故循环队列诞生!

解决“假溢出”的问题有两种可行的方法:

(1)、平移元素:把元素平移到队列的首部。效率低。否决了。

(2)、将新元素插入到第一个位置上,构成循环队列,入队和出队仍按“先进先出”的原则进行。操作效率高、空间利用率高。

      

虽然使用循环队列,解决了假溢出问题,但是又有新问题发生——判空的问题,因为仅凭 front = rear 不能判定循环队列是空还是满。比如如图:

这是空循环队列的样子

这是满循环队列的样子

解决办法:

(1)、另设一个布尔变量以区别队列的空和满;

(2)、少用一个元素的空间,约定入队前测试尾指针在循环下加 1 后是否等于头指针,若相等则认为队满;(最常用)

(3)、使用一个计数器记录队列中元素的总数。

对于第2个方案,必须牺牲一个元素的空间,那么入队的时候需要测试,循环意义下的加 1 操作可以描述为:

复制代码
1     if (rear + 1 = MAXQSIZE)
2 
3            rear = 0;
4 
5      else
6 
7           rear ++; 
复制代码

利用模运算可简化为:

1 rear = (rear + 1)% MAXQSIZE  

基本操作

复制代码
 1 #ifndef ___queue_Header_h
 2 #define ___queue_Header_h
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 #define MAX_SIZE 5
 6 
 7 typedef struct{
 8     int *base;
 9     int rear;//如果队列不空,指向队尾元素的下一个位置
10     int front;//初始的时候指向表头
11 } CirularQueue;
12 
13 //初始化
14 void initQueue(CirularQueue *queue)
15 {
16     queue->base = (int *)malloc(MAX_SIZE*sizeof(int));
17     
18     if (NULL == queue->base) {
19         exit(0);
20     }
21     
22     queue->front = queue->rear = 0;
23 }
复制代码

求长度

复制代码
//求长度
int getLength(CirularQueue queue)
{
    //这样把所以的情况都考虑到了
    return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE;
}
复制代码

第一种情况,长度的求法

第二种情况,长度的求法,利用模运算,两个情况合二为一!

复制代码
//入队,先判满
void insertQueue(CirularQueue *queue, int e)
{
    if ((queue->rear + 1) % MAX_SIZE == queue->front) {
        puts("循环队列是满的!");
    }
    else
    {
        queue->base[queue->rear] = e;
        queue->rear = (queue->rear + 1) % MAX_SIZE;
    }
}
复制代码

如下时为满,损失一个空间,不存储元素。方便判满

复制代码
 1 //出队
 2 void deleteQueue(CirularQueue *queue)
 3 {
 4     if (queue->front == queue->rear) {
 5         puts("队列是空的!");
 6     }
 7     else
 8     {
 9         queue->front = (queue->front + 1) % MAX_SIZE;
10     }
11 }
12 
13 //遍历
14 void traversal(CirularQueue queue)
15 {
16     int q = queue.front;
17     
18     for (int i = 0; i < getLength(queue); i++) {
19         printf("循环队列的第%d个元素为%d\n", i + 1, queue.base[q]);
20         q++;
21     }
22 }
23 
24 #endif
复制代码

测试

复制代码
 1 #include "Header.h"
 2 
 3 int main(int argc, const char * argv[]) {
 4     CirularQueue queue;
 5     puts("循环队列初始化:");
 6     initQueue(&queue);
 7     
 8     puts("循环队列初始化后长度:");
 9     printf("%d\n", getLength(queue));
10     
11     puts("循环队列5个元素入队,总长度为5,但是损失一个位置空间,实际存储4个元素。先进先出原则:");
12     puts("循环队列元素0入队");
13     insertQueue(&queue, 0);
14     puts("循环队列元素1入队");
15     insertQueue(&queue, 1);
16     puts("循环队列元素2入队");
17     insertQueue(&queue, 2);
18     puts("循环队列元素3入队");
19     insertQueue(&queue, 3);
20     
21     puts("循环队列元素遍历:");
22     traversal(queue);
23     
24     puts("循环队列元素继续入队,无法完成:");
25     insertQueue(&queue, 4);
26     
27     puts("循环队列元素0出队之后,先进先出原则:");
28     deleteQueue(&queue);
29     traversal(queue);
30     
31     puts("循环队列元素1出队之后,先进先出原则:");
32     deleteQueue(&queue);
33     traversal(queue);
34     
35     puts("循环队列元素2出队之后,先进先出原则:");
36     deleteQueue(&queue);
37     traversal(queue);
38     
39     puts("循环队列元素3出队之后,先进先出原则:");
40     deleteQueue(&queue);
41     traversal(queue);
42     
43     puts("4个元素全部删除,循环队列已经空了:");
44     deleteQueue(&queue);
45     
46     traversal(queue);
47     
48     return 0;
49 }
复制代码

结果;

循环队列初始化:

循环队列初始化后长度:

0

循环队列5个元素入队,总长度为5,但是损失一个位置空间,实际存储4个元素。先进先出原则:

循环队列元素0入队

循环队列元素1入队

循环队列元素2入队

循环队列元素3入队

循环队列元素遍历:

循环队列的第1个元素为0

循环队列的第2个元素为1

循环队列的第3个元素为2

循环队列的第4个元素为3

循环队列元素继续入队,无法完成:

循环队列是满的!

循环队列元素0出队之后,先进先出原则:

循环队列的第1个元素为1

循环队列的第2个元素为2

循环队列的第3个元素为3

循环队列元素1出队之后,先进先出原则:

循环队列的第1个元素为2

循环队列的第2个元素为3

循环队列元素2出队之后,先进先出原则:

循环队列的第1个元素为3

循环队列元素3出队之后,先进先出原则:

4个元素全部删除,循环队列已经空了:

队列是空的!

Program ended with exit code: 0

 

小结:

若用户需要循环队列,那么要设置队列的最大长度,否则无法完成判断空,如果用户不知道最大长度是多少,那么应该使用链队。队列在程序设计中和栈一样,应用很多,未完待续。

 

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4104802.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构——队列
队列 (Queue) 是一种先进先出FIFO (First in First Out) 的线性存储结构
0 0
数据结构 队列
数据结构 队列
0 0
数据结构-队列结构
如何理解“队列”? 队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列”。 我们知道,栈只支持两个基本操作:入栈 push()和出栈 pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。
0 0
【数据结构】《大话数据结构》队列代码汇总
【数据结构】《大话数据结构》队列代码汇总
0 0
数据结构基础——队列
数据结构基础——队列
0 0
数据结构(3):队列的原理和实现
完整代码拉到最底下 一、介绍 队列顾名思义就像我们生活中排队一样,先进先出。 如上图所示,25、16、5、9依次在队列中,按照顺序拿出的数据也分别是25、26、5、9。 二、实现过程及思路 底层使用数组来实现,实现的功能有插入数据到队尾、移除队首数据、查看队首数据、判断队列是否为空、判断队列是否存满。
658 0
[数据结构]队列的基本操作
栈是先进后出,队列则是先进先出.下面贴一下队列的基本操作. 1.队列的顺序表示. 1.1队列的结构体定义 #include #include typedef int DataType; #define MA...
282 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载