Очередь
Следующая структура данных в этой серии статей — это еще одна абстрактная структура данных контейнерного типа, называемая очередью. Очереди работают по существу как реальная очередь в том смысле, что порядок извлечения работает в порядке FIFO (первым пришел — первым обслужен).
Это полезная структура данных, позволяющая сделать время ожидания товаров справедливым. Обратите внимание, что среднее время ожидания остается одинаковым независимо от того, используем ли мы стек (LIFO) или очередь (FIFO).
Три операции, которые должна реализовать любая очередь:
Enqueue(x,q): вставьте элемент x в конец очереди q.Dequeue(q): Вернуть (и удалить) первый элемент из очереди q.is_empty(q): Возвращает True, если очередь пуста, в противном случае — False.
Реализация очереди
ставить в очередь
Давайте посмотрим, как мы можем реализовать очередь в Python, используя список. Во-первых, мы можем реализовать метод enqueue и использовать его для заполнения очереди.
class Queue:
def __init__(self, queue = None, queue_size = 0):
"""
Constructor #1 for Queue class
"""
self.queue = []
self.queue_size = queue_size
def enqueue(self, item):
"""
Add item to the beginning of the queue
"""
self.queue.insert(0, item)
self.queue_size += 1
def __repr__(self) -> str:
"""
String representation of Queue class
"""
return f"Queue({self.queue})"
if __name__ == "__main__":
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue)
print(queue.queue_size)
# Output:
# Queue([3, 2, 1])
# 3
Далее, чтобы упростить построение очереди, мы можем создать метод класса generate_queue, который строит очередь из списка значений:
class Queue:
def __init__(self, queue = None, queue_size = 0):
"""
Constructor #1 for Queue class
"""
self.queue = []
self.queue_size = queue_size
def enqueue(self, item):
"""
Add item to the beginning of the queue
"""
self.queue.insert(0, item)
self.queue_size += 1
def __repr__(self) -> str:
"""
String representation of Queue class
"""
return f"Queue({self.queue})"
@classmethod
def generate_queue(cls, *args):
"""
Constructor #2 for Queue class
"""
queue = cls()
queue.queue.extend(args)
queue.queue_size = len(args)
return queue
if __name__ == "__main__":
queue = Queue.generate_queue(1,2,3)
print(queue)
# Output:
# Queue([1, 2, 3])p
удалить из очереди & is_empty
Далее, чтобы завершить базовую реализацию очереди, мы реализуем методы dequeue и is_empty:
class Queue:
def __init__(self, queue = None, queue_size = 0):
"""
Constructor #1 for Queue class
"""
self.queue = []
self.queue_size = queue_size
@classmethod
def generate_queue(cls, *args):
"""
Constructor #2 for Queue class
"""
queue = cls()
queue.queue.extend(args)
queue.queue_size = len(args)
return queue
def enqueue(self, item):
"""
Add item to the beginning of the queue
"""
self.queue.insert(0, item)
self.queue_size += 1
def dequeue(self, index = None):
"""
Remove item from end of queue
"""
if queue.queue_size == 0:
return -1
self.queue_size -= 1
if index is not None and index < queue.queue_size:
return self.queue.pop(index)
else:
return self.queue.pop()
def is_empty(self):
"""
Check if queue is empty
"""
return True if self.queue_size == 0 else False
def __repr__(self) -> str:
"""
String representation of Queue class
"""
return f"Queue({self.queue})"
if __name__ == "__main__":
queue = Queue.generate_queue(1,2,3)
print(queue)
queue.enqueue(4) # Add 4 to the beginning of the queue
queue.dequeue() # Remove 3 from the end of the queue
print(queue)
# Output:
# Queue([1, 2, 3])
# Queue([4, 1, 2])
просмотр, добавление, мин и макс
Мы можем настроить нашу очередь по своему усмотрению и добавить дополнительные методы. Например, давайте добавим следующие 4 метода:
peek— вернуть элемент из начала очереди.append- Вставить элемент в конец очереди.minиmax— найдите минимальный/максимальный элемент в очереди.
class Queue:
def __init__(self, queue = None, queue_size = 0):
"""
Constructor #1 for Queue class
"""
self.queue = []
self.queue_size = queue_size
@classmethod
def generate_queue(cls, *args):
"""
Constructor #2 for Queue class
"""
queue = cls()
queue.queue.extend(args)
queue.queue_size = len(args)
return queue
def enqueue(self, item):
"""
Add item to the beginning of the queue
"""
self.queue.insert(0, item)
self.queue_size += 1
def append(self, item):
"""
Add item to the beginning of the queue
"""
self.queue.append(item)
self.queue_size += 1
def dequeue(self, index = None):
"""
Remove item from end of queue
"""
if queue.queue_size == 0:
return -1
self.queue_size -= 1
if index is not None and index < queue.queue_size:
return self.queue.pop(index)
else:
return self.queue.pop()
def is_empty(self):
"""
Check if queue is empty
"""
return True if self.queue_size == 0 else False
def peek(self, index = None):
"""
Return item at end of queue
"""
if queue.queue_size == 0:
return -1
if index is not None and index < queue.queue_size:
return self.queue[index]
else:
return self.queue[-1]
def max(self):
"""
Return maximum value in queue
"""
if queue.queue_size == 0:
return -1
return max(self.queue)
def min(self):
"""
Return minimum value in queue
"""
if queue.queue_size == 0:
return -1
return min(self.queue)
def __repr__(self) -> str:
"""
String representation of Queue class
"""
return f"Queue({self.queue})"
Пример — максимальное скользящее окно
Давайте посмотрим, как мы можем использовать нашу очередь для решения задач программирования. Я попытаюсь решить следующий вопрос Leetcode под названием «Максимальное скользящее окно».
Вам дан массив целых чисел nums, имеется скользящее окно размером k, которое перемещается из самого левого края массива в самый правый. В окне вы можете увидеть только k чисел. Каждый раз скользящее окно перемещается вправо на одну позицию.
Возвращает максимальное скользящее окно.
Пример 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 73 1 [3 -1 -3] 5 3 6 73 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 75 1 3 -1 -3 [5 3 6] 76 1 3 -1 -3 5 [3 6 7]7
Решение
Основная идея решения этой проблемы — перебирать массив и добавлять элементы в очередь до тех пор, пока очередь не достигнет размера k.
С этого момента на каждой итерации мы находим максимальный элемент в очереди, вставляем его в список результатов, помещаем в очередь следующий элемент массива и удаляем из очереди последний элемент в очереди.
Это выглядит следующим образом:
A = [1,3,-1,-3,5,3,6,7]
k = 3
def max_sliding_window(A, k):
# Creating an empty queue
queue = Queue()
results = []
for i in range(len(A)):
# While the queue is smaller than k, add elements to the queue
if i < k:
queue.enqueue(A[i])
else:
# Once queue is size of k, at each iteration, add the max to the results
# Then dequeue the first element and enqueue the next element
results.append(queue.max())
queue.dequeue()
queue.enqueue(A[i])
# Add the max of the last window to the results
results.append(queue.max())
return results
print(max_sliding_window(A, k))
# Output:
# [3, 3, 5, 5, 6, 7]
