发布于2020-02-24 23:57 阅读(1008) 评论(0) 点赞(15) 收藏(5)
题目:用两个栈实现队列
具体描述:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解前若无思路可看这里漫画更清晰
题解:
class CQueue:
def __init__(self):
self.stack1=[] #基本栈
self.stack2=[] #辅助栈
def appendTail(self, value: int) -> None:
self.stack1.append(value) #元素放入基本栈
def deleteHead(self) -> int:
# 将基本栈的元素放入辅助栈,基本栈后进元素先放入辅助栈
if len(self.stack2) == 0:
while len(self.stack1) != 0:
self.stack2.append(self.stack1.pop())
# 从辅助栈放出元素
if len(self.stack2) != 0:
return(self.stack2.pop())
return(-1)
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
复杂度分析
(1)插入元素
时间复杂度:O(1)。向基本栈插入一个元素,在队列尾部插入元素,使用常数时间。
空间复杂度:O(1)。向基本栈插入一个元素,使用常数空间。
(2)删除元素
时间复杂度:O(n)。基本栈的元素要删除并插入到辅助栈,是线性时间复杂度。
空间复杂度:O(n)。需要额外空间储存元素。
力扣官方给的题解插入删除元素复杂度正好和上述相反,其将栈元素删除压入至辅助栈放入appendTail插入元素步,个人理解中,对于删除操作少的,插入元素操作多的,将appendTail更简单更好一些
作者:嘴巴嘟嘟
链接:https://www.pythonheidong.com/blog/article/232922/ca7a4dfa5c098f1e009f/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!