Середина

Проблема

Разработайте свою реализацию циклической очереди. Круговая очередь представляет собой линейную структуру данных, в которой операции выполняются по принципу 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].
  • Пожалуйста, не используйте встроенную библиотеку Queue.

Решение

Мы должны быть осторожны до/после enQueue и deQueue при обработке пустого регистра.

Сложность

Все действия занимают O(1) время и занимают O(k) пространство, если k означает длину очереди . Кстати, доступ/поиск элемента в очереди займет O(n) времени.