栈和队列相关代码在前面已经实现过了，接下来就手撕几道有关栈和队列的几道高频经典OJ，让大家更加深刻的理解栈和队列这两种数据结构。
第一题：用栈实现队列
OJ链接：
题目要求用两个栈实现一个队列，要求具备队列基本接口：入列，出列，返回队列头元素，判断队列是否为空。接下来我们按照 ” 一定能写出来四步流程 “，来完成这个题目。
一.思路分析：
我们知道，队列有先进先出（FIFO）的原则，所以要想用两个栈实现队列，就必须用这两个栈使得数据先进先出。因为栈是先进后出的原则，会使得出数据顺序相反，所以用两个栈就刚好可以把顺序摆正。例如 1 2 3 4进入第一个栈---->4 3 2 1进入第二个栈---->1 2 3 4
二.细节分析
我们把两个栈分别取名为pushstack、popstack。即一个栈专门用来入队列，一个栈专门用来出队列。
1.当有元素要入队列：只需要把这个元素入栈到pushstack。
2.当有元素要出队列：如果popstack栈中有元素，直接出栈即可。如果popstack栈中没有元素，需要将pushstack栈中的元素捯入popstack栈。再出popstack栈。
3.返回队首元素：如果popstack栈中有元素，直接返回栈顶元素即可。如果popstack栈中没有元素，需要将pushstack栈中的元素捯入popstack栈。再返回popstack栈顶元素。
4.判断队列是否为空：若两个栈都为空，则队列为空。
三.代码实现
1. //栈的实现 2. typedef int DateType; 3. typedef struct Stack//栈的总架构（这里是动态栈） 4. { 5. DateType* arr; 6. int top;//栈顶下标 7. int capcity;//栈的容量 8. }Stack; 9. //下面对栈的操作都是改变结构体内部的属性，参数列表传结构体一级指针 10. void IntiStack(Stack* stack);//初始化栈 11. void PushStack(Stack* stack, DateType n);//进栈,尾插 12. void PopStack(Stack* stack);//出栈,尾删 13. bool StackEmpty(Stack* stack);//检测栈是否为空 14. int StackSize(Stack* stack);//获取栈中有效数据个数 15. DateType TopStack(Stack* stack);//获取栈顶数据 16. void DestoryStack(Stack* stack);//销毁栈 17. 18. void IntiStack(Stack* stack) 19. { 20. DateType* tmp = (DateType*)malloc(4*sizeof(DateType)); 21. assert(tmp); 22. stack->arr = tmp; 23. stack->top = 0; 24. stack->capcity = 4; 25. } 26. void PushStack(Stack* stack, DateType n) 27. { 28. assert(stack); 29. if (stack->top == stack->capcity) 30. { 31. //扩容 32. DateType* tmp = realloc(stack->arr,2 * stack->capcity * sizeof(DateType)); 33. assert(tmp); 34. stack->arr = tmp; 35. stack->capcity *= 2; 36. } 37. stack->arr[stack->top] = n; 38. stack->top++; 39. } 40. void PopStack(Stack* stack) 41. { 42. assert(stack); 43. assert(!StackEmpty(stack)); 44. stack->top--; 45. } 46. bool StackEmpty(Stack* stack) 47. { 48. assert(stack); 49. return stack->top == 0; 50. } 51. int StackSize(Stack* stack) 52. { 53. assert(stack); 54. return stack->top; 55. } 56. DateType TopStack(Stack* stack) 57. { 58. assert(stack); 59. assert(!StackEmpty(stack)); 60. return stack->arr[stack->top - 1]; 61. } 62. void DestoryStack(Stack* stack) 63. { 64. assert(stack); 65. free(stack->arr); 66. stack->arr = NULL; 67. stack->capcity = 0; 68. stack->top = 0; 69. } 70. 71. //开始解题 72. typedef struct//定义队列 73. { 74. Stack pushstack;//定义两个栈 75. Stack popstack; 76. } MyQueue; 77. MyQueue* myQueueCreate()//初始化队列 78. { 79. MyQueue* queue=(MyQueue*)malloc(sizeof(MyQueue));//为队列分配空间，顺便为两个栈分配空间 80. IntiStack(&queue->pushstack);//初始化两个栈 81. IntiStack(&queue->popstack); 82. return queue; 83. } 84. void myQueuePush(MyQueue* obj, int x)//入列 85. { 86. PushStack(&obj->pushstack,x);//把这个元素入栈到pushstack 87. } 88. 89. int myQueuePop(MyQueue* obj)//出列 90. { 91. int tmp=myQueuePeek(obj);//获取队列头元素（popstack栈顶元素） 92. PopStack(&obj->popstack);//删除popstack栈顶元素 93. return tmp;//返回队列头元素 94. } 95. int myQueuePeek(MyQueue* obj)//获取队首元素 96. { 97. if(StackEmpty(&obj->popstack))//如果popstack栈为空 98. { 99. //导pushstack栈的数据->popstack栈 100. while(!StackEmpty(&obj->pushstack))//循环条件：pushstack栈不为空 101. { 102. //将pushstack栈顶元素入栈到popstack栈 103. PushStack(&obj->popstack,TopStack(&obj->pushstack)); 104. //删除pushstack栈顶元素 105. PopStack(&obj->pushstack); 106. } 107. } 108. return TopStack(&obj->popstack);//返回popstack栈顶元素 109. } 110. bool myQueueEmpty(MyQueue* obj)//判断队列是否为空 111. { 112. //两个栈都为空，队列为空，返回true 113. return StackEmpty(&obj->pushstack)&&StackEmpty(&obj->popstack); 114. } 115. void myQueueFree(MyQueue* obj)//销毁队列 116. { 117. DestoryStack(&obj->pushstack);//先销毁里面两个栈中的顺序表空间 118. DestoryStack(&obj->popstack); 119. free(obj);//再释放队列空间(可以释放两个栈的空间，但是无法是释放栈里面的顺序表空间!) 120. }
四.总结
用栈实现队列本质需要了解栈与队列的区别，知道二者数据处理的差异，并灵活应用。
