Я изучаю очередь из задачи Циркулярная очередь проектирования - LeetCode
Дизайн вашей реализации круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются на основе принципа FIFO (First In First Out), и последняя позиция соединяется обратно с первой позицией для образования круга. Его также называют «кольцевой буфер».
Одним из преимуществ кольцевой очереди является то, что мы можем использовать пробелы перед очередью. В обычной очереди, когда очередь заполнится, мы не сможем вставить следующий элемент, даже если перед ней есть место. Но используя круговую очередь, мы можем использовать пространство для хранения новых значений.
Ваша реализация должна поддерживать следующие операции:
MyCircularQueue(k): Конструктор, установите размер очереди равным k. Front: получить передний элемент из очереди. Если очередь пуста, вернуть -1. Rear: получить последний элемент из очереди. Если очередь пуста, вернуть -1. enQueue(value): вставить элемент в круговую очередь. Верните true, если операция прошла успешно. deQueue(): удалить элемент из циклической очереди. Верните true, если операция прошла успешно. isEmpty(): проверяет, пустая круговая очередь или нет. isFull(): проверяет, заполнена ли циклическая очередь или нет.
Пример:
MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1); // return true
circularQueue.enQueue(2); // return true
circularQueue.enQueue(3); // return true
circularQueue.enQueue(4); // return false, the queue is full
circularQueue.Rear(); // return 3
circularQueue.isFull(); // return true
circularQueue.deQueue(); // return true
circularQueue.enQueue(4); // return true
circularQueue.Rear(); // return 4
Примечание:
- Все значения будут в диапазоне [0, 1000].
- Количество операций будет в диапазоне [1, 1000].
- Пожалуйста, не используйте встроенную библиотеку очередей.
Я имитирую учебник Гудрича Структуры данных и алгоритмы на Python и написал удобное для чтения решение
1, только три данных (_queue, _len и _front)
2, инициализировать self._front как 0
class MyCircularQueue:
#Runtime: 76 ms, faster than 53.17%
#Memory Usage: 13.6 MB, less than 7.24%
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the queue to be k.
"""
self._queue = [None] * k #the basic
self._capacity = k
self._len = 0
#The first three categorize as a group, the 4th as the second group
self._front = 0
#self._rear is not necessary, because rear = front + length -1
def enQueue(self, value: int) -> bool:
"""
Insert an element into the circular queue. Return true if the operation is successful.
"""
if self.isFull(): return False
avail = (self._front + self._len) % (self._capacity)
self._queue[avail] = value
self._len += 1
return True
def deQueue(self) -> bool:
"""
Delete an element from the circular queue. Return true if the operation is successful.
"""
if self.isEmpty():
return False
self._queue[self._front] = None #overrode the current node
self._front = (self._front+1) % self._capacity
self._len -= 1
return True
def Front(self) -> int:
"""
Get the front item from the queue.
"""
if not self.isEmpty():
return self._queue[self._front]
else:
return -1
def Rear(self) -> int:
"""
Get the last item from the queue.
"""
if not self.isEmpty():
_rear = (self._front + self._len - 1) % self._capacity
return self._queue[_rear]
else:
return -1
def isEmpty(self) -> bool:
"""
Checks whether the circular queue is empty or not.
"""
return self._len == 0
def isFull(self) -> bool:
"""
Checks whether the circular queue is full or not.
"""
return self._len == self._capacity
Дизайн Гудрича очень хорошо читается с меньшими усилиями.
Однако, после прочтения других представлений, обычная практика состоит в том, чтобы инициализировать self._fornt и self._rear как -1, хотя считалось, что для чтения или записи необходимо приложить усилия.
За исключением случая, производительность которого выше 98%
def deQueue(self):
"""
Delete an element from the circular queue. Return true if the operation is successful.
:rtype: bool
"""
if self.isEmpty():
return False
self.head = (self.head+1) % self.maxlen
self.currlen -= 1
if self.isEmpty(): #have to take care of self.head and self.tail
self.head = -1
self.tail = -1
#another submission which initialize front and rear =-1
def enQueue(self, value: 'int') -> 'bool':
"""
Insert an element into the circular queue. Return true if the operation is successful.
"""
if (self.len == self.capacity): return False
# To check if full
#if (self.rear == self.front - 1 or (self.rear == self.capacity - 1 and self.front == 0) )
if (self.front == -1):
self.front, self.rear = 0, 0
elif (self.rear == self.capacity - 1 and self.front != 0):
# make rear start (case when element was removed from start)
self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.data[self.rear] = value
self.len += 1
return True
Поскольку Python затеняет большинство деталей реализации,
Какое преимущество принимать front или rear как -1?