中小型企业网站建设,免费看片网站,wordpress要求,08网站建设算法#xff1a;
其实这道题不用像上一道题一样#xff0c;用两个队列实现栈。
由于队列的数据结构特性。用一个队列就可实现栈。
难点还是在出队的时候#xff1a;
比如队列[1,2,3]#xff0c;要模拟一个栈入栈就是直接append#xff08;其实就是C中的push#xff0…
算法
其实这道题不用像上一道题一样用两个队列实现栈。
由于队列的数据结构特性。用一个队列就可实现栈。
难点还是在出队的时候
比如队列[1,2,3]要模拟一个栈入栈就是直接append其实就是C中的push出栈时应该先出3但是队列先出1此时可以先把1取出来再加入队列即[2,3,1]再把2取出来再加入队列即[3,1,2]这个时候再取出队首3也就模拟了出栈操作。
总结
只要将队列首部的元素除了最后一个元素外 重新添加到队列尾部此时再去弹出元素就是栈的顺序了。
为什么用栈实现队列的时候要用两个栈 因为栈底部是密封的只有上面敞口而队列前后都敞口。
所以队列可以实现“先从队首把1取出来再加入队列”的操作而栈要取数只能从最上面敞口的地方取。
Top算法
对于 Python 中的序列类型如列表、元组、字符串等可以使用负数索引来访问元素。负数索引表示从序列的末尾开始计数-1 表示最后一个元素-2 表示倒数第二个元素依此类推。
可以使用负数索引来访问队列的最后一个元素如self.que[-1]。
调试过程 Python普通的Queue或SimpleQueue没有类似于peek的功能 也无法用索引访问在实现top的时候较为困难。 用list可以但是在使用pop(0)的时候时间复杂度为O(n) 因此这里使用双向队列我们保证只执行popleft()和append()因为deque可以用索引访问可以实现和peek相似的功能
class MyStack:def __init__(self):self.que deque()def push(self, x: int) - None:self.que.append(x)def pop(self) - int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) - int:if self.empty():return Noneelse:return self.que[-1]def empty(self) - bool:return self.que# Your MyStack object will be instantiated and called as such:
# obj MyStack()
# obj.push(x)
# param_2 obj.pop()
# param_3 obj.top()
# param_4 obj.empty() 原因
因为我的 empty 方法返回的是一个 deque 对象而预期的返回类型是布尔值。
为了解决这个问题可以将 empty 方法中的返回语句修改为 return not self.que。这样如果队列为空返回 True否则返回 False。
正确代码
class MyStack:def __init__(self):self.que deque()def push(self, x: int) - None:self.que.append(x)def pop(self) - int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) - int:if self.empty():return Noneelse:return self.que[-1]def empty(self) - bool:return not self.que
优化
Top里面的que[-1]实际上用到了栈因为直接获取了que的末尾元素。
其实可以类似pop函数将队列首部的元素除了最后一个元素外 重新添加到队列尾部此时再去弹出的元素就是栈的首了
不过要把这个“栈首”再加回队列里面因为top不改变栈。 比如队列[1,2,3]要模拟一个栈出栈时应该先出3但是队列先出1此时可以先把1取出来再加入队列即[2,3,1]再把2取出来再加入队列即[3,1,2]这个时候再取出队首3也就是top将其弹出再把这个3加入队列即[1,2,3]。其实没有改变栈的内容。
class MyStack:def __init__(self):self.que deque()def push(self, x: int) - None:self.que.append(x)def pop(self) - int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())return self.que.pop()def top(self) - int:if self.empty():return Noneelse:for i in range(len(self.que)-1):self.que.append(self.que.pop())temp self.que.pop()self.que.append(temp)return tempdef empty(self) - bool:return not self.que# Your MyStack object will be instantiated and called as such:
# obj MyStack()
# obj.push(x)
# param_2 obj.pop()
# param_3 obj.top()
# param_4 obj.empty()
