Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм:

1⃣Инициализация и проверка состояний
Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.

2⃣Операции вставки
Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class MyCircularDeque {
    private $deque;
    private $front;
    private $rear;
    private $size;
    private $capacity;

    function __construct($k) {
        $this->capacity = $k;
        $this->deque = array_fill(0, $k, 0);
        $this->front = 0;
        $this->rear = 0;
        $this->size = 0;
    }

    function insertFront($value) {
        if ($this->isFull()) return false;
        $this->front = ($this->front - 1 + $this->capacity) % $this->capacity;
        $this->deque[$this->front] = $value;
        $this->size++;
        return true;
    }

    function insertLast($value) {
        if ($this->isFull()) return false;
        $this->deque[$this->rear] = $value;
        $this->rear = ($this->rear + 1) % $this->capacity;
        $this->size++;
        return true;
    }

    function deleteFront() {
        if ($this->isEmpty()) return false;
        $this->front = ($this->front + 1) % $this->capacity;
        $this->size--;
        return true;
    }

    function deleteLast() {
        if ($this->isEmpty()) return false;
        $this->rear = ($this->rear - 1 + $this->capacity) % $this->capacity;
        $this->size--;
        return true;
    }

    function getFront() {
        if ($this->isEmpty()) return -1;
        return $this->deque[$this->front];
    }

    function getRear() {
        if ($this->isEmpty()) return -1;
        return $this->deque[($this->rear - 1 + $this->capacity) % $this->capacity];
    }

    function isEmpty() {
        return $this->size == 0;
    }

    function isFull() {
        return $this->size == $this->capacity;
    }
}

Ставь 👍 и забирай 📚 Базу знаний