一.【Leetcode225】队列实现栈
1.链接
2.题目再现
3.解法
这道题给了我们两个队列，要求去实现栈；
首先，我们要知道栈和队列的特征：
栈：后进先出，只能从栈顶入数据和出数据；
队列：先进先出，从队尾入数据，队头出数据；
根据这些特点，我们可以采用两边倒的方法来实现；
具体来说：
1.入栈时就是在不为空的队列插入数据，若两个队列都为空，就随便插入到一个队列中；
2.出栈时将不为空的队列的数据倒入为空的队列中，当不为空的队列就剩一个数据时，就停止向空队列倒数据，然后再删点那最后一个数据；
3.判空时，需要两个队列都为空，才算栈为空；
4.取栈顶元素即取不为空的队列的队尾元素，在取栈顶元素前要判断栈是否为空；
5.销毁栈时，要先销毁其中的两个队列，然后再销毁栈。
因为是用C语言实现的，所以得自己手搓个队列。
1. typedef int Qdatatype; 2. 3. typedef struct QueueNode 4. { 5. struct QueeuNode* next; 6. Qdatatype data; 7. }QueueNode; 8. 9. typedef struct Queue 10. { 11. QueueNode* head; 12. QueueNode* tail; 13. }Queue; 14. void Queueinit(Queue* pq) 15. { 16. assert(pq); 17. pq->head = NULL; 18. pq->tail = NULL; 19. } 20. 21. void Queuedestroy(Queue* pq) 22. { 23. assert(pq); 24. QueueNode* cur = pq->head; 25. 26. while (cur != pq->tail) 27. { 28. QueueNode* next = cur->next; 29. free(cur); 30. cur = next; 31. } 32. 33. pq->head = pq->tail = NULL; 34. } 35. 36. void Queuepush(Queue* pq, Qdatatype x) 37. { 38. assert(pq); 39. QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); 40. 41. if (newnode == NULL) 42. { 43. perror("malloc fail"); 44. exit(-1); 45. } 46. newnode->data = x; 47. newnode->next = NULL; 48. if (pq->head == NULL) 49. { 50. pq->head = pq->tail = newnode; 51. } 52. else 53. { 54. pq->tail->next = newnode; 55. pq->tail = newnode; 56. } 57. } 58. 59. void Queuepop(Queue* pq) 60. { 61. assert(pq); 62. assert(pq->head); 63. 64. QueueNode* next = pq->head->next; 65. if (pq->head->next == NULL) 66. { 67. free(pq->head); 68. pq->head = pq->tail = NULL; 69. } 70. else 71. { 72. free(pq->head); 73. pq->head = next; 74. } 75. } 76. 77. Qdatatype Queuefront(Queue* pq) 78. { 79. assert(pq); 80. assert(pq->head); 81. 82. return pq->head->data; 83. } 84. 85. Qdatatype Queueback(Queue* pq) 86. { 87. assert(pq); 88. assert(Queuesize(pq) > 0); 89. 90. return pq->tail->data; 91. } 92. 93. int Queuesize(Queue* pq) 94. { 95. assert(pq); 96. int size = 0; 97. QueueNode* cur = pq->head; 98. while (cur != pq->tail->next) 99. { 100. size++; 101. cur = cur->next; 102. } 103. 104. return size; 105. } 106. 107. bool Queueempty(Queue* pq) 108. { 109. assert(pq); 110. 111. return pq->head == NULL; 112. } 113. 114. typedef struct 115. { 116. Queue q1; 117. Queue q2; 118. } MyStack; 119. 120. MyStack* myStackCreate() { 121. MyStack*obj=(MyStack*)malloc(sizeof(MyStack)); 122. if(obj==NULL) 123. exit(-1); 124. Queueinit(&obj->q1); 125. Queueinit(&obj->q2); 126. 127. return obj; 128. } 129. 130. void myStackPush(MyStack* obj, int x) 131. { 132. if(!Queueempty(&obj->q1)) 133. { 134. Queuepush(&obj->q1,x); 135. } 136. else 137. { 138. Queuepush(&obj->q2,x); 139. } 140. } 141. 142. int myStackPop(MyStack* obj) { 143. Queue*empty=&obj->q1; 144. Queue*noempty=&obj->q2; 145. if(!Queueempty(&obj->q1)) 146. { 147. empty=&obj->q2; 148. noempty=&obj->q1; 149. } 150. while(Queuesize(noempty)>1) 151. { 152. Queuepush(empty,Queuefront(noempty)); 153. Queuepop(noempty); 154. } 155. int front=Queuefront(noempty); 156. Queuepop(noempty); 157. return front; 158. } 159. 160. int myStackTop(MyStack* obj) { 161. if(!Queueempty(&obj->q1)) 162. { 163. return Queueback(&obj->q1); 164. } 165. else 166. { 167. return Queueback(&obj->q2); 168. } 169. } 170. bool myStackEmpty(MyStack* obj) { 171. 172. return Queueempty(&obj->q1)&&Queueempty(&obj->q2); 173. } 174. 175. void myStackFree(MyStack* obj) { 176. 177. Queuedestroy(&obj->q1); 178. Queuedestroy(&obj->q2); 179. 180. free(obj); 181. }
二.【Leetcode232】栈实现队列
1.链接
2.题目再现
3.解法
这个的解法和上面的类似，只不过这个不用总是来回倒；
根据栈和队列的特征，我们会发现将一个栈中的数据倒入另一个栈时，数据的顺序刚好符合队列的要求，不需要再重复地倒数据，所以我们可以让一个栈专门用来入数据（Pushst），一个栈专门用来出数据（Popst），当我们要出数据而这个栈为空时，我们才将用来入数据的栈中的数据倒入用来出数据的栈 。
如图：
1.判空时，需要两个栈都为空，队列才为空；
2.返回队头数据时，和出数据的操作类似，只是不需要删除队头的数据，还有在之前要判断队列是否为空；
3.销毁队列前，要先销毁两个栈。
同样，因为是C语言，得先手搓个栈。
1. #define MR_CAP 5 2. typedef int STdatatype; 3. 4. typedef struct Stack 5. { 6. STdatatype* arr; 7. int top; 8. int capacity; 9. }ST; 10. 11. void Stackinit(ST* ps) 12. { 13. assert(ps); 14. 15. ps->arr = (STdatatype*)malloc(MR_CAP * sizeof(STdatatype)); 16. if (ps->arr == NULL) 17. { 18. perror("Stackinit malloc"); 19. exit(-1); 20. } 21. 22. ps->top = 0; 23. ps->capacity = MR_CAP; 24. } 25. 26. void Stackdestroy(ST* ps) 27. { 28. assert(ps); 29. 30. free(ps->arr); 31. ps->arr = NULL; 32. ps->top = 0; 33. ps->capacity = 0; 34. } 35. 36. void Stackpush(ST* ps, STdatatype x) 37. { 38. assert(ps); 39. 40. if (ps->top == ps->capacity) 41. { 42. STdatatype* tmp = (STdatatype*)realloc(ps->arr, ps->capacity * 2 * sizeof(STdatatype)); 43. if (tmp == NULL) 44. { 45. perror("Stackpush realloc"); 46. exit(-1); 47. } 48. else 49. { 50. ps->arr = tmp; 51. ps->capacity *= 2; 52. } 53. } 54. 55. ps->arr[ps->top] = x; 56. ps->top++; 57. } 58. 59. void Stackpop(ST* ps) 60. { 61. assert(ps); 62. assert(ps->top > 0); 63. 64. ps->top--; 65. } 66. 67. STdatatype Stacktop(ST* ps) 68. { 69. assert(ps); 70. 71. return ps->arr[ps->top - 1]; 72. } 73. 74. int Stacksize(ST* ps) 75. { 76. assert(ps); 77. 78. return ps->top; 79. 80. } 81. 82. bool Stackempty(ST* ps) 83. { 84. assert(ps); 85. 86. if (ps->top == 0) 87. { 88. return true; 89. } 90. else 91. return false; 92. 93. } 94. 95. typedef struct { 96. ST Pushst; 97. ST Popst; 98. } MyQueue; 99. 100. MyQueue* myQueueCreate() { 101. MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue)); 102. if(obj==NULL) 103. exit(-1); 104. Stackinit(&obj->Pushst); 105. Stackinit(&obj->Popst); 106. 107. return obj; 108. } 109. 110. void myQueuePush(MyQueue* obj, int x) { 111. Stackpush(&obj->Pushst,x); 112. } 113. 114. int myQueuePeek(MyQueue* obj) { 115. if(Stackempty(&obj->Popst)) 116. { 117. while(!Stackempty(&obj->Pushst)) 118. { 119. Stackpush(&obj->Popst,Stacktop(&obj->Pushst)); 120. Stackpop(&obj->Pushst); 121. } 122. } 123. 124. return Stacktop(&obj->Popst); 125. 126. } 127. 128. int myQueuePop(MyQueue* obj) { 129. 130. int front=myQueuePeek(obj); 131. Stackpop(&obj->Popst); 132. return front; 133. } 134. 135. bool myQueueEmpty(MyQueue* obj) { 136. 137. return Stackempty(&obj->Pushst)&&Stackempty(&obj->Popst); 138. } 139. 140. void myQueueFree(MyQueue* obj) { 141. Stackdestroy(&obj->Pushst); 142. Stackdestroy(&obj->Popst); 143. 144. free(obj); 145. }
🐲👻这两道题的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖
🥰🤩希望小伙伴们可以多多支持博主哦。😍😃
😁😄谢谢你的阅读。😼😸
