【数据结构---21】用栈实现队列的操作

题目描述:

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部 pop() -- 从队列首部移除元素 peek() -- 返回队列首部的元素 empty() -- 返回队列是否为空

示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的 你所使用的语言也许不支持栈 你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

先把需要用到的栈构建好:C语言实现一个动态栈

思路分析:

1.使用两个栈来完成对队列的模拟 2.一个栈用来辅助中转元素,一个栈主要用来存放数据 3.入队操作全部对于s1进行,出队操作首先将s1中的元素压入s2,然后s2的栈顶就是队头,将值保存后删除,然后再把s2的元素全部转入s1,恢复原本的结构 4.获取队头元素和出队操作一致,只是不删除s2的栈顶元素即可

代码实现:

typedef struct { Stack s1; Stack s2; } MyQueue; /** Initialize your data structure here. */ MyQueue* myQueueCreate() { MyQueue* SQ=(MyQueue*)malloc(sizeof(MyQueue)); if(SQ==NULL) { assert(0); } StackInit(&SQ->s1); StackInit(&SQ->s2); return SQ; } /** Push element x to the back of queue. */ void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->s1,x); } /** Removes the element from in front of queue and returns that element. */ int myQueuePop(MyQueue* obj) { //队列的Pop是头删,删除栈底元素 while(obj->s1.top>0) { StackPush(&obj->s2,StackTop(&obj->s1)); StackPop(&obj->s1); } int a=StackTop(&obj->s2); StackPop(&obj->s2); //然后恢复本来的结构 while(obj->s2.top>0) { StackPush(&obj->s1,StackTop(&obj->s2)); StackPop(&obj->s2); } return a; } /** Get the front element. */ int myQueuePeek(MyQueue* obj) { while(obj->s1.top>0) { StackPush(&obj->s2,StackTop(&obj->s1)); StackPop(&obj->s1); } int a=StackTop(&obj->s2); //然后恢复本来的结构 while(obj->s2.top>0) { StackPush(&obj->s1,StackTop(&obj->s2)); StackPop(&obj->s2); } return a; } /** Returns whether the queue is empty. */ bool myQueueEmpty(MyQueue* obj) { if(StackEmpty(&obj->s2) == -1 && StackEmpty(&obj->s1) == -1) { return true; } return false; } void myQueueFree(MyQueue* obj) { free(obj); obj=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); */