MiddleКодЧастоЕщё не отвечали
Напишите реализацию очереди (кольцевой буфер)
Реализуйте очередь фиксированного размера на кольцевом буфере поверх непрерывного массива с операциями enqueue, dequeue, front, size, empty, full.
Требования:
- Все операции O(1); никаких динамических выделений после конструирования.
- Различайте
emptyиfull(например, оставьте один слот пустым или ведите счётчик размера). dequeue/frontна пустой очереди иenqueueна полной должны сигнализировать об ошибке.
#include <vector>
template<typename T>
class CircularQueue {
public:
explicit CircularQueue(size_t capacity);
void enqueue(const T& val);
T dequeue();
const T& front() const;
bool empty() const;
bool full() const;
size_t size() const;
// ваш код здесь
};Допишите реализацию.
Очередь на кольцевом буфере использует массив фиксированного размера с индексами head и tail, оборачивающимися по модулю вместимости. enqueue записывает в tail и продвигает его; dequeue читает из head и продвигает его. Условие заполненности: (tail + 1) % cap == head. Это даёт O(1) для enqueue/dequeue без динамических выделений.
- ✗Путать условия заполненности и пустоты — (tail + 1) % cap == head для полной, head == tail для пустой
- ✗Тратить один слот для различения полной и пустой очереди — альтернатива: отдельный счётчик размера
- ✗Ошибка на единицу в арифметике по модулю
- →Как сделать эту очередь потокобезопасной для одного производителя и одного потребителя?
- →В чём преимущество кольцевого буфера перед очередью на связном списке?
Оглавление
Задача
Реализуйте очередь фиксированного размера на основе кольцевого буфера с операциями enqueue, dequeue, front, size, empty, full.
Решение
#include <vector>
#include <stdexcept>
#include <cassert>
template<typename T>
class CircularQueue {
public:
explicit CircularQueue(size_t capacity)
: buf_(capacity + 1), cap_(capacity + 1) {}
void enqueue(const T& val) {
if (full()) throw std::overflow_error("queue full");
buf_[tail_] = val;
tail_ = (tail_ + 1) % cap_;
}
T dequeue() {
if (empty()) throw std::underflow_error("queue empty");
T val = buf_[head_];
head_ = (head_ + 1) % cap_;
return val;
}
const T& front() const {
if (empty()) throw std::underflow_error("queue empty");
return buf_[head_];
}
bool empty() const { return head_ == tail_; }
bool full() const { return (tail_ + 1) % cap_ == head_; }
size_t size() const {
return (tail_ >= head_) ? tail_ - head_
: cap_ - head_ + tail_;
}
private:
std::vector<T> buf_;
size_t cap_;
size_t head_ = 0;
size_t tail_ = 0;
};
int main() {
CircularQueue<int> q(3);
assert(q.empty());
q.enqueue(1); q.enqueue(2); q.enqueue(3);
assert(q.full());
assert(q.size() == 3);
assert(q.front() == 1);
assert(q.dequeue() == 1);
assert(q.dequeue() == 2);
q.enqueue(4); // буфер оборачивается
assert(q.dequeue() == 3);
assert(q.dequeue() == 4);
assert(q.empty());
}Ключевые моменты
- Один слот намеренно остаётся незаполненным для различения empty/full состояний.
- Альтернатива: хранить отдельный счётчик
size_— без потери слота. - O(1) для всех операций, нет динамических выделений памяти после инициализации.
- Используется в lock-free очередях producer-consumer (SPSC).
Оглавление
