天津市住房公积金网,柚木家具的优缺点,健康养生常识
使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
示例:
myqueue queue = new myqueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false
说明:
设计时使用两个栈
一个栈作为压入栈,记为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)
公众号:《程序员养成记》
主要写算法、计算机基础之类的文章, 有兴趣来关注一起成长!
版权声明 :著作权归作者所有,非商业转载请注明出处,禁止商业转载。
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
python求numpy中array按列非零元素的平均值案例
网友评论