你好，欢迎来到我的博客！作为一名程序员，我经常刷LeetCode题目来提升自己的编程能力。在我的博客里，我会分享一些我自己做过的题目和解题思路，希望能够帮助到大家。今天，我想和大家分享一道挑战性较高的题目，让我们一起来挑战一下吧！作者也是在学习的过程中刷到有意思的题目就会选择与大家分享，并且提供较优解，关于力扣的文章全部放在博客，如果大家喜欢记得支持作者。🤓
题目难度：简单
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
- 说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例一：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
解题思路💡
总结：栈是先进后出，队列是先进先出，用两个栈实现队列，我们可以定义一个专门入数据的栈，再定义一个专门出数据的栈，入数据就在入数据的栈中入，出数据时，如果出数据的栈为空，将入数据的栈顶内容依次入到出数据的栈中，这样出数据的栈中的数据就是反过来的，再将此栈中的栈顶数据出栈。直到出数据的栈为空，再将入数据的栈中的数据再入栈到出数据的栈中，就达到了先入先出的效果。
- 本题需要先写一个功能完全的栈，然后对栈进行调用。
示例
第一步）
- 写出一个
栈，有基本的初始化、入栈、出栈、销毁等功能。
（第二步）由上图中可以了解到
- 调用栈函数模拟实现队列功能。
代码实现⭐
typedef int STDataType; typedef struct STNode { STDataType* str; int top; int capacity; }STNode; void STInit(STNode* pst) { assert(pst); pst->str = NULL; pst->top = 0; pst->capacity = 0; } bool STEmpty(STNode* pst) { assert(pst); return pst->top == 0; } void STPush(STNode* pst, STDataType data) { assert(pst); if (pst->top == pst->capacity) { int Newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* temp =(STDataType*)realloc(pst->str,sizeof(STDataType) * Newcapacity); if (temp == NULL) { perror("malloc error"); return; } pst->str = temp; pst->capacity = Newcapacity; } pst->str[pst->top++] = data; } void STPop(STNode* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } void STDestroy(STNode* pst) { assert(pst); free(pst->str); pst->top = 0; pst->capacity = 0; } STDataType STTop(STNode* pst) { assert(pst); assert(!STEmpty(pst)); return pst->str[pst->top - 1]; } typedef struct { STNode* STPushStack; STNode* STPopStack; } MyQueue; MyQueue* myQueueCreate() { MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue)); mq->STPushStack = (STNode*)malloc(sizeof(STNode)); STInit(mq->STPushStack); mq->STPopStack = (STNode*)malloc(sizeof(STNode)); STInit(mq->STPopStack); return mq; } void myQueuePush(MyQueue* obj, int x) { assert(obj); STPush(obj->STPushStack,x); } bool myQueueEmpty(MyQueue* obj) { assert(obj); return obj->STPushStack->top==0&&obj->STPopStack->top==0; } int myQueuePop(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); if(obj->STPopStack->top==0) { while(obj->STPushStack->top!=0) { STDataType temp = STTop(obj->STPushStack); STPop(obj->STPushStack); STPush(obj->STPopStack,temp); } } STDataType ret = STTop(obj->STPopStack); STPop(obj->STPopStack); return ret; } int myQueuePeek(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); if(obj->STPopStack->top==0) { while(obj->STPushStack->top!=0) { STDataType temp = STTop(obj->STPushStack); STPop(obj->STPushStack); STPush(obj->STPopStack,temp); } } return STTop(obj->STPopStack); } void myQueueFree(MyQueue* obj) { assert(obj); STDestroy(obj->STPushStack); STDestroy(obj->STPopStack); obj->STPushStack = NULL; obj->STPopStack = NULL; } /** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */
完结
当你喜欢一篇文章时，点赞、收藏和关注是最好的支持方式。如果你喜欢我的文章，请不要吝啬你的支持，点赞👍、收藏⭐和关注都是对我最好的鼓励。感谢你们的支持！
