🔒Открыть пост
и посмотреть медиа
Задача: 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 {
public:
MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
deque[front] = value;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
deque[rear] = value;
rear = (rear + 1) % capacity;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
int getFront() {
if (isEmpty()) return -1;
return deque[front];
}
int getRear() {
if (isEmpty()) return -1;
return deque[(rear - 1 + capacity) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
private:
vector deque;
int front;
int rear;
int size;
int capacity;
};
Ставь 👍 и забирай 📚 Базу знаний
