用栈实现队列-爱代码爱编程
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-queue-using-stacks
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目提示
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty(这个提示元素最多为100个
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)
代码
typedef struct
{
int puttop,outtop;
int put[100],out[100];//一个用来存放进入队列的元素 一个存放出队列
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue *list=(MyQueue*)malloc(sizeof (MyQueue));//申请队列空间
list->puttop=0;
list->outtop=0;
return list;//返回创建好的队列
}
void myQueuePush(MyQueue* obj, int x)
{
obj->put[obj->puttop]=x;//将元素存入队列
obj->puttop++;//下标向后移一位
}
int myQueuePop(MyQueue* obj)
{
int putindex,outindex,tmp;
putindex=obj->puttop;
//下面if(outindex==0)中 使用--putindex是因为
//输入元素后 puttop会向后移动一位 下标puttop此时无对应元素
outindex=obj->outtop;
if(outindex==0)//out[]为空 队列开头元素在put[]中 将队列开头元素放入out[]
{
while(putindex>0)
{
obj->out[outindex++]=obj->put[--putindex];//将put[]中元素转移
}
}
tmp=obj->out[--outindex];//储存队列开头元素
while(outindex>0)//除队列开头元素外 其他元素都放回put[]
{
obj->put[putindex++]=obj->out[--outindex];
}
//更新下标
obj->puttop=putindex;
obj->outtop=0;
return tmp;
}
int myQueuePeek(MyQueue* obj)
{
return obj->put[0];//返回队列中的第一个元素
}
bool myQueueEmpty(MyQueue* obj)
{
if(obj->puttop==0&&obj->outtop==0)
return true;
else
return false;
}
void myQueueFree(MyQueue* obj)
{
free(obj);
}
/**
* 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);
*/
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-queue-using-stacks