哪里有做网站排名优化,龙江人社使用教程,wordpress修改宽度,学校网站建设的建议队列是先入先出#xff08;后入后出#xff09;的数据结构#xff0c;常用操作就 push 和 popleft#xff0c;Python中用列表中的 pop(0) 或者 collection.deque的 popleft() 都可以。
普通队列
225. 用队列实现栈
class MyStack:def __init__(self):self.queue1 []sel…队列是先入先出后入后出的数据结构常用操作就 push 和 popleftPython中用列表中的 pop(0) 或者 collection.deque的 popleft() 都可以。
普通队列
225. 用队列实现栈
class MyStack:def __init__(self):self.queue1 []self.queue2 []self.size 0def push(self, x: int) - None:self.size 1self.queue1.append(x)def pop(self) - int:# if self.empty(): 题目中保证了不会 pop 空# return Nonefor _ in range(self.size-1):self.queue2.append(self.queue1.pop(0))self.size - 1self.queue1, self.queue2 self.queue2, self.queue1return self.queue2.pop(0)def top(self) - int:# if self.empty():# return Nonereturn self.queue1[-1]def empty(self) - bool:return self.size 0题目要求用两个队列实现栈很简单push 的操作是一样的只不过在 pop 的时候不能 pop 队列最后一个元素而要一直 pop 队首元素到另一个队列只剩下的那一个元素即为栈顶元素弹出它即可。显然用一个队列也能实现
class MyStack:def __init__(self):self.queue []def push(self, x: int) - None:self.queue.append(x)def pop(self) - int:# if self.empty():# return Nonefor _ in range(len(self.queue)-1):self.queue.append(self.queue.pop(0))return self.queue.pop(0)def top(self) - int:# if self.empty():# return Nonereturn self.queue[-1]def empty(self) - bool:return len(self.queue) 0346. 数据流中的移动平均值
class MovingAverage:def __init__(self, size: int):self.queue []self.size sizeself.sum 0def next(self, val: int) - float:if len(self.queue) self.size:self.queue.append(val)else:self.sum - self.queue[0]self.queue.pop(0)self.queue.append(val)self.sum valreturn self.sum / len(self.queue)这题是利用队列实现滑动窗口窗口满了之后每次新加进来一个数 val计数器 sum 就减去队首元素 queue[0]然后加上 val 即可。
622. 设计循环队列
class MyCircularQueue:def __init__(self, k: int):self.front 0self.rear 0self.size k1self.queue [0 for _ in range(k1)]def enQueue(self, value: int) - bool:if self.isFull():return Falseelse:self.rear (self.rear 1) % self.sizeself.queue[self.rear] valuereturn Truedef deQueue(self) - bool:if self.isEmpty():return Falseelse:self.front (self.front 1) % self.sizereturn Truedef Front(self) - int:return self.queue[(self.front 1) % self.size] if not self.isEmpty() else -1def Rear(self) - int:return self.queue[self.rear] if not self.isEmpty() else -1def isEmpty(self) - bool:return self.front self.reardef isFull(self) - bool:return (self.rear 1) % self.size self.front设计循环队列的核心是对长度取余特别是只对加 1 的情况取余而除了队列为空时首尾指针一样其余情况下尾指针都在首指针的左边。注意不要忘记判断队列空或者满的情况。
优先队列
优先队列常用二叉堆实现相应的题目见这篇博客。
