循环数组实现队列_用循环数组实现队列,定义见queue.h。 注意: 不可使用除数组和链表外的任何标准库

1. 队列：只允许在表尾（队尾）插入和在表首（队首）删除的表（也就是队首标只在插入入时变化，队尾标只在删除时变化）。又叫先进先出（FIFO）表。
2. 用数组循环实现队列，首先想象数组中的单元排列成一个圆，数组的头部和尾部相邻，而表在占用其中任意连续的一部分数组单元空间（而队尾队首标永远大于0且根据增加和删除的次数自加，所以这里存在一个数组越界问题）。接下来用Front指向表中元素的前一个位置，用Last指向表中元素的最后一个所在的数组位置。无论怎么安排Last和Front的初始指向位置，他俩的相对位置关系在表满和表为空的关系总是不变的。那么怎么判断表是满还是空呢。我们可以设置一个量，来记录每次的增加和删除，当这个量等于数组的大小时，表就满了。或者我们约定当表中元素到数组最大存储数量减1时，认定这个表为满。也就是舍弃一个数组单元空间来作为判定表是否满的依据。
3. 代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef int ListItem;
typedef struct snode *Snode;
typedef struct snode{
	int maxsize;
	int front;//指向队首元素的前一个 
	int Last;//指向对尾元素
	int curr;// 
	ListItem *queue; 
}Simul;

Snode ListInit(int size)
{
	Snode L = (Snode)malloc(sizeof( * L));
	L->queue = (int *)malloc(sizeof(int )*size);
	L->maxsize = size;
	L->front = L->Last = 0;//一开始都指向数组的0位 
	return L;
}

int IsEmpty(Snode L)
{
	return L->Last == L->front; //重合则为空队列因为都是从0开始，即一开始就重合了 
 } 
 
int IsFull(Snode L)
{
	return (((L->Last+1)%L->maxsize == L->front)?1:0);
	//因为采用第二种方式，所以最后数组单元为空，而front指向这里，last指向5，所以加Last加1判断是否等于来判断是否队列。 
	//用取余防止数组循坏越界 
}
ListItem ListFirst(Snode L)
{
	if(IsEmpty(L)) return 0;
	return L->queue[(L->front+1)%L->maxsize];//输出队首元素 取余是防止越界。取余是小于被取余的数话返回该数本身，取余的操作是在front和Last发生变化时需要进行。
}

ListItem ListPog(Snode L)
{
	if(IsEmpty(L))return 0;
	return L->queue[L->Last];
}

int  ListInsert(Snode L,ListItem x)
{
	if(IsFull(L))return 0;
	L->Last = (L->Last+1)%L->maxsize; //防止插入和删除时候越界 
	L->queue[L->Last] = x;
}

ListItem ListDellete(Snode L)
{
   if(IsEmpty(L))return 0;
   L->front = (L->curr+1)%L->maxsize;
   return L->queue[L->curr];	
}

int ListTravel(Snode L)
{
	if(IsEmpty(L))return 0;
	L->curr = L->front;
	while((L->curr)%L->maxsize != L->Last ){
		printf("%d",L->queue[L->curr+1]);
		L->curr = (L->curr+1)%L->maxsize;
	}
}

int  ListFind(Snode L,int k)
{
	if(IsEmpty(L))return 0;
	L->curr = L->front;
	for(int i = 1;i<k;i++) L->curr = (L->curr+1)%L->maxsize;
		printf("%d位置上的值为%d\n",k,L->queue[(L->curr+1)%L->maxsize]);

}
int main()
{
	  Snode L = ListInit(6);
      ListInsert(L,1);
	  ListInsert(L,2);
	  ListInsert(L,3);
	  ListInsert(L,4);
	  printf("列首元素为 %d \n",ListFirst(L));
	  printf("列尾元素为 %d \n",ListPog(L));
	  ListDellete(L);
	  ListFind(L,2);
	  ListTravel(L);
	  printf("\n"); 
	  printf("列首元素为 %d \n",ListFirst(L));
	  printf("列尾元素尾 %d \n",ListPog(L));
}
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
91
92

5. 运行结果如下：