用循环数组实现队列的方法

92 阅读 0 评论 61 点赞

我是靠谱客的博主粗心溪流，这篇文章主要介绍用循环数组实现队列的方法，现在分享给大家，希望可以做个参考。

用数组实现表的方法可用于实现队列，但这样做的效果并不好。尽管可以用一个游标来指示队尾，使得EnterQueue运算在O（1）时间内完成，但是在执行DeleteQueue时，为了删除队首元素，必须将数组中其他元素都向前移动一个位置。这样队列中有n个元素时，执行DeleteQueue就需要n的时间。

为了提高运算的效率，采用另一种观点来处理数组中各单元的位置关系。设想数组queue[0:maxsize-1]中的单元不是排成一排，而是围成一个环，即queue[0]接在queue[maxsize-1]的后面。这种意义下的数组称为循环数组

复制代码

#include<stdio.h>
#include<stdlib.h>
typedef struct aque*Queue;
typedef struct aque
{
int maxsize;
int front;
int rear;
int *queue;
//循环数组
}Aqueue;
//*******************************
//初始化
Queue QueueInit(int size)
{
Queue Q;
Q=(Queue)malloc(sizeof(Aqueue));
Q->queue=(int*)malloc(sizeof(int)*size);
Q->front=Q->rear=0;
Q->maxsize=size;
return Q;
}
//*******************************
//判断队列是否为空
int QueueEmpty(Queue Q)
{
return Q->front==Q->rear;
}
//*******************************
//判断队列是否为满
int QueueFull(Queue Q)
{
return (Q->rear+1)%Q->maxsize==Q->front;
}
//*******************************
//返回队列队首的值
int QueueFirst(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
return Q->queue[(Q->front+1)%Q->maxsize];
}
//*******************************
//返回队列队尾的值
int QueueLast(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
return Q->queue[Q->rear];
}
//*******************************
//新元素入队列
void EnterQueue(int x,Queue Q)
{
if(QueueFull(Q))
{
printf("queue is full");
exit(0);
}
Q->rear=(Q->rear+1)%Q->maxsize;
Q->queue[Q->rear]=x;
}
//删除队首元素
int DeleteQueue(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
Q->front=(Q->front+1)%Q->maxsize;
return Q->queue[Q->front];
}
int main()
{
Queue Q;
int size=20;
Q=QueueInit(size);
for(int i=1;i<=10;i++)
EnterQueue(i,Q);
for(i=1;i<=10;i++)
printf("%d ",DeleteQueue(Q));
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<stdio.h>
#include<stdlib.h>
typedef struct aque*Queue;
typedef struct aque
{
int maxsize;
int front;
int rear;
int *queue;
//循环数组
}Aqueue;
//*******************************
//初始化
Queue QueueInit(int size)
{
Queue Q;
Q=(Queue)malloc(sizeof(Aqueue));
Q->queue=(int*)malloc(sizeof(int)*size);
Q->front=Q->rear=0;
Q->maxsize=size;
return Q;
}
//*******************************
//判断队列是否为空
int QueueEmpty(Queue Q)
{
return Q->front==Q->rear;
}
//*******************************
//判断队列是否为满
int QueueFull(Queue Q)
{
return (Q->rear+1)%Q->maxsize==Q->front;
}
//*******************************
//返回队列队首的值
int QueueFirst(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
return Q->queue[(Q->front+1)%Q->maxsize];
}
//*******************************
//返回队列队尾的值
int QueueLast(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
return Q->queue[Q->rear];
}
//*******************************
//新元素入队列
void EnterQueue(int x,Queue Q)
{
if(QueueFull(Q))
{
printf("queue is full");
exit(0);
}
Q->rear=(Q->rear+1)%Q->maxsize;
Q->queue[Q->rear]=x;
}
//删除队首元素
int DeleteQueue(Queue Q)
{
if(QueueEmpty(Q))
{
printf("queue is empty");
exit(0);
}
Q->front=(Q->front+1)%Q->maxsize;
return Q->queue[Q->front];
}
int main()
{
Queue Q;
int size=20;
Q=QueueInit(size);
for(int i=1;i<=10;i++)
EnterQueue(i,Q);
for(i=1;i<=10;i++)
printf("%d ",DeleteQueue(Q));
return 0;
}