队列的实现（下）

1. typedef struct {
2.     ST pushST;//定义结构体
3.     ST popST;
4. } MyQueue;
5. 
6. //初始化
7. MyQueue* myQueueCreate() {
8.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
9. assert(obj);
10. StackInit(&obj->pushST);
11. StackInit(&obj->popST);
12. return obj;
13. }
14. 
15. void myQueuePush(MyQueue* obj, int x)
16. {
17. assert(obj);
18. StackPush(&obj->pushST,x);
19. }
20. //
21. int myQueuePop(MyQueue* obj) 
22. {
23. assert(obj);
24. if (StackEmpty(&obj->popST))
25.     {
26. while (!StackEmpty(&obj->pushST))
27.        {
28. StackPush(&obj->popST, StackTop(&obj->pushST));
29. StackPop(&obj->pushST);//把数据倒过去之后，需要删掉pushST里的数据
30.        }
31.     }
32. int front = StackTop(&obj->popST);
33. StackPop(&obj->popST);
34. return front;
35. }
36. 
37. //返回队列开头的元素，如果popST没有元素就导入元素，有数据就直接导入
38. int myQueuePeek(MyQueue* obj) 
39. {
40. assert(obj);
41. if (StackEmpty(&obj->popST))
42.     {
43. while (!StackEmpty(&obj->pushST))
44.        {
45. StackPush(&obj->popST, StackTop(&obj->pushST));
46. StackPop(&obj->pushST);//把数据倒过去之后，需要删掉pushST里的数据
47.        }
48.     }
49. return StackTop(&obj->popST);
50. }
51. 
52. bool myQueueEmpty(MyQueue* obj) 
53. {
54. assert(obj);
55. return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
56. }
57. //两层free,是因为free是把指向的空间free掉，仅仅free掉地址内容存放的空间，并没有free掉地址所指向的内容，但是obj里面的指针又指向了别的空间。
58. void myQueueFree(MyQueue* obj) 
59. {
60. assert(obj);
61. StackDestory(&obj->pushST);
62. StackDestory(&obj->popST);
63. free(obj);
64.     obj = NULL;
65. }
66. 
67. /**
68.  * Your MyQueue struct will be instantiated and called as such:
69.  * MyQueue* obj = myQueueCreate();
70.  * myQueuePush(obj, x);
71.  
72.  * int param_2 = myQueuePop(obj);
73.  
74.  * int param_3 = myQueuePeek(obj);
75.  
76.  * bool param_4 = myQueueEmpty(obj);
77.  
78.  * myQueueFree(obj);
79. */

1. typedef struct {
2. int* a;
3. int head;
4. int tail;
5. int k;
6. } MyCircularQueue;
7. 
8. bool myCircularQueueIsFull(MyCircularQueue* obj);
9. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
10. 
11. MyCircularQueue* myCircularQueueCreate(int k) {
12.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
13. assert(obj);
14.     obj->a = (int*)malloc((k+1)*sizeof(int));
15. assert(obj->a);
16.     obj->head = obj->tail = 0;
17.     obj->k = k;
18. return obj;
19. }
20. 
21. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
22. assert(obj);
23. assert(obj->a);
24. if (myCircularQueueIsFull(obj))
25.     {
26. return false;
27.     }
28. else
29.     {
30. if ((obj->head) == (obj->tail))
31.         {
32.             obj->a[obj->head]=  obj->a[obj->tail] = value;
33.         }
34. else
35.         {
36.             obj->a[obj->tail] = value;
37.         }
38. 
39. if (obj->tail == obj->k)
40.         {
41.             obj->tail = 0;
42.         }
43. else
44.         {
45.             obj->tail++;
46.         }
47. return true;
48.     }
49. 
50. }
51. 
52. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
53. assert(obj);
54. assert(obj->a);
55. if (myCircularQueueIsEmpty(obj))
56.     {
57. return false;
58.     }
59. else
60.     {
61. if (obj->head == obj->k)
62.         {
63.             obj->head = 0;
64.         }
65. else
66.         {
67.             obj->head++;
68.         }
69. return true;
70.     }
71. }
72. 
73. int myCircularQueueFront(MyCircularQueue* obj) 
74. {
75. assert(obj);
76. assert(obj->a);
77. if (myCircularQueueIsEmpty(obj))
78.     {
79. return -1;
80.     }
81. else
82.     {
83. return obj->a[obj->head];
84.     }
85. }
86. 
87. int myCircularQueueRear(MyCircularQueue* obj) {
88. assert(obj);
89. assert(obj->a);
90. if (myCircularQueueIsEmpty(obj))
91.     {
92. return -1;
93.     }
94. else
95.     {
96. if (obj->tail == 0)
97.         {
98. return obj->a[obj->k];
99.         }
100. else
101.         {
102. return obj->a[obj->tail - 1];
103.         }
104. 
105.     }
106. }
107. 
108. bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
109. {
110. assert(obj);
111. assert(obj->a);
112. return obj->head == obj->tail;
113. 
114. }
115. 
116. bool myCircularQueueIsFull(MyCircularQueue* obj) {
117. assert(obj);
118. assert(obj->a);
119. if ((obj->head == 0) && (obj->tail == obj->k))
120.     {
121. return true;
122.     }
123. else
124.     {
125. return (obj->tail) + 1 == obj->head;
126.     }
127. }
128. 
129. void myCircularQueueFree(MyCircularQueue* obj) 
130. {
131. free(obj->a);
132. free(obj);
133. }
134. 
135. /**
136.  * Your MyCircularQueue struct will be instantiated and called as such:
137.  * MyCircularQueue* obj = myCircularQueueCreate(k);
138.  * bool param_1 = myCircularQueueEnQueue(obj, value);
139.  
140.  * bool param_2 = myCircularQueueDeQueue(obj);
141.  
142.  * int param_3 = myCircularQueueFront(obj);
143.  
144.  * int param_4 = myCircularQueueRear(obj);
145.  
146.  * bool param_5 = myCircularQueueIsEmpty(obj);
147.  
148.  * bool param_6 = myCircularQueueIsFull(obj);
149.  
150.  * myCircularQueueFree(obj);
151. */