由两个栈组成的队列
程序员文章站
2023-01-25 17:33:12
题目 使用栈实现队列的下列操作: 示例: 说明: 你只能使用标准的栈操作 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用list或者deque(双端队列)来模拟一个栈,只要是标准的栈 ......
题目
使用栈实现队列的下列操作:
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 操作)。
思路
设计时使用两个栈
一个栈作为压入栈,记为stack_in
一个栈作为弹出栈,记为stack_out
1.当有数据入队列时,压入stack_in
2.当有数据出队列时,从stack_out弹出,如果stack_out为空,则循环遍历stack_in,将stack_in中的元素全部弹出,并按弹出顺序全部压入栈stack_out,循环结束后从stack_out弹出栈顶元素即可
代码
class myqueue: def __init__(self): """ initialize your data structure here. """ self.stack_in = [] self.stack_out = [] def push(self, x: int) -> none: """ push element x to the back of queue. """ self.stack_in.append(x) def pop(self) -> int: """ removes the element from in front of queue and returns that element. """ if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() else: return self.stack_out.pop() def peek(self) -> int: """ get the front element. """ if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1] else: return self.stack_out[-1] def empty(self) -> bool: """ returns whether the queue is empty. """ if self.stack_out or self.stack_in: return false else: return true
复杂度分析
入队
时间复杂度:o(1):向栈压入元素的时间复杂度为o(1)
空间复杂度:o(n):需要额外的内存来存储队列元素
出队
时间复杂度: 摊还复杂度 o(1),最坏情况下的时间复杂度 o(n)
在最坏情况下,stack_out为空,算法需要从 stack_in 中弹出 n 个元素,然后再把这 n个元素压入 stack_out空间复杂度 :o(1)
公众号:《程序员养成记》
主要写算法、计算机基础之类的文章, 有兴趣来关注一起成长!
版权声明 :著作权归作者所有,非商业转载请注明出处,禁止商业转载。
上一篇: 蜂蜜在低温下会凝固么?你真的了解蜂蜜吗
下一篇: STL 应用之set