使用C语言来解决循环队列问题的方法

这篇文章主要介绍了使用C语言来解决循环队列问题的方法,来自ACM的练习题实例,需要的朋友可以参考下

题目描述：

大家都知道数据结构里面有一个结构叫做循环队列。顾名思义，这是一个队列，并且是循环的。但是现在，淘气的囧哥给这个循环队列加上了一些规矩，其中有5条指令:

(1) Push K, 让元素K进队列。

(2) Pop，对头元素出队列。

(3) Query K，查找队列中第K个元素，注意K的合法性。

(4) Isempty，判断队列是否为空。

(5) Isfull，判断队列是否已满。

现在有N行指令，并且告诉你队列大小是M。

输入：

第一行包含两个整数N和M。1<=N,M<=100000。

接下来有N行，表示指令，指令格式见题目描述。

其中元素均在int范围。

输出：

对于指令(1)，若队列已满，输出failed，否则不做输出。

对于指令(2)，若队列已空，输出failed，否则不做输出。

对于指令(3)，输出队列中第K个元素，若不存在，输出failed。

对于指令(4)和(5)，则用yes或者no回答。

详情见样例。

样例输入：

12 2Push 1Push 2Push 3Query 2Query 3IsemptyIsfullPopPopPopIsemptyIsfull

样例输出：

failed2failednoyesfailedyesno

AC代码：

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <string.h>  
4.  
5. #define queuesize 100001 //最大队列长度  
6.  
7. struct queue  
8. {  
9. int front;  
10. int rear;  
11. int data[queuesize];  
12. int count; //记录队列中的元素  
13. };  
14.  
15. void InitQueue(struct queue *Q);  
16. void EnQueue(struct queue *Q, int element, int m);  
17. void Dequeue(struct queue *Q, int m);  
18. void QueueSearch(struct queue *Q, int k, int m);  
19.  
20. int main()  
21. {  
22. int n, m, i, element, k, flag;  
23. char command[10];  
24.  
25. while(scanf("%d%d",&n, &m) != EOF)  
26. {  
27. if(n < 1 || m > 100000)  
28. return 0;  
29. struct queue *Q;  
30. Q = malloc(sizeof(struct queue));  
31. InitQueue(Q);  
32. for(i = 0; i < n; i ++)  
33. {  
34. scanf("%s",command);  
35. if (strcmp(command,"Push") == 0)  
36. {  
37. scanf("%d",&element);  
38. EnQueue(Q, element, m);  
39. }else if (strcmp(command,"Pop") == 0)  
40. {  
41. Dequeue(Q, m);  
42. }else if (strcmp(command,"Query") == 0)  
43. {  
44. scanf("%d",&k);  
45. QueueSearch(Q, k, m);  
46. }else if (strcmp(command,"Isempty") == 0)  
47. {  
48. flag = (Q -> count == 0)? 1 : 0;  
49. if(flag)  
50. {  
51. printf("yes/n");  
52. }else 
53. {  
54. printf("no/n");  
55. }  
56. }else if (strcmp(command,"Isfull") == 0)  
57. {  
58. flag = (Q -> count == m)? 1 : 0;  
59. if(flag)  
60. {  
61. printf("yes/n");  
62. }else 
63. {  
64. printf("no/n");  
65. }  
66. }  
67. }  
68. }  
69. return 0;  
70. }  
71.  
72. /**  
73. * Description:队列初始化  
74. */ 
75. void InitQueue(struct queue *Q)  
76. {  
77. Q -> front = Q -> rear = 0;  
78. Q -> count = 0;  
79. }  
80.  
81. /**  
82. * Description:入队操作  
83. */ 
84. void EnQueue(struct queue *Q, int element, int m)  
85. {  
86. int flag;  
87. flag = (Q -> count == m)? 1 : 0;  
88.  
89. if(!flag)  
90. {  
91. Q -> data[Q -> rear] = element;  
92. Q -> count ++;  
93. Q -> rear = (Q -> rear + 1) % m;  
94. }else 
95. {  
96. printf("failed/n");  
97. }  
98. }  
99.  
100. /**  
101. * Description:出队操作  
102. */ 
103. void Dequeue(struct queue *Q, int m)  
104. {  
105. int flag;  
106. int element;  
107.  
108. flag = (Q -> count == 0)? 1 : 0;  
109.  
110. if(!flag)  
111. {  
112. element = Q -> data[Q -> front];  
113. Q -> front = (Q -> front + 1) % m;  
114. Q -> count --;  
115. }else 
116. {  
117. printf("failed/n");  
118. }  
119. }  
120.  
121. /**  
122. * Description:查找队列中的指定元素  
123. */ 
124. void QueueSearch(struct queue *Q, int k, int m)  
125. {  
126. int flag, temp;  
127. flag = (Q -> count == 0)? 1: 0;  
128. temp = Q -> front + k - 1;  
129. if((!flag) && (k <= m && k >= 1))  
130. {  
131. if((Q -> front < Q -> rear) && ( Q-> front <= temp && Q -> rear > temp))  
132. printf("%d/n",Q -> data[temp]);  
133. else if((Q -> front > Q -> rear) && (temp >= Q -> front || temp < Q->rear))  
134. printf("%d/n",Q -> data[temp]);  
135. else if(Q -> front == Q -> rear)  
136. printf("%d/n",Q -> data[temp]);  
137. else 
138. printf("failed/n");  
139. }else 
140. {  
141. printf("failed/n");  
142. }  
143. }