這篇文章主要介紹了使用C語言來解決循環(huán)隊列問題的方法,來自ACM的練習題實例,需要的朋友可以參考下

題目描述：

大家都知道數(shù)據(jù)結(jié)構(gòu)里面有一個結(jié)構(gòu)叫做循環(huán)隊列。顧名思義，這是一個隊列，并且是循環(huán)的。但是現(xiàn)在，淘氣的囧哥給這個循環(huán)隊列加上了一些規(guī)矩，其中有5條指令:

(1) Push K, 讓元素K進隊列。

(2) Pop，對頭元素出隊列。

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

(4) Isempty，判斷隊列是否為空。

(5) Isfull，判斷隊列是否已滿。

現(xiàn)在有N行指令，并且告訴你隊列大小是M。

輸入：

第一行包含兩個整數(shù)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. }