Какие знаешь виды очередей?

Виды очередей в Go

В Go существуют различные подходы к реализации очередей, каждый из которых имеет свои особенности применения, преимущества и недостатки. Основные виды можно разделить на несколько категорий.

1. Каналы (Channels) - встроенная очередь FIFO

Каналы являются основной встроенной синхронизированной очередью в Go, реализующей паттерн FIFO (First-In-First-Out). Они потокобезопасны по своей природе и идеально подходят для коммуникации между горутинами.

// Пример очереди на основе канала
queue := make(chan string, 100) // Буферизированный канал как очередь

// Запись в очередь
queue <- "task1"
queue <- "task2"

// Чтение из очереди
task := <-queue
fmt.Println(task) // "task1"

Преимущества:

• Встроенная потокобезопасность
• Блокирующие операции ожидания
• Интеграция с оператором select для мультиплексирования
• Автоматическое управление блокировками горутин

Недостатки:

• Ограниченная емкость (при переполнении блокируется запись)
• Однонаправленность (канал имеет тип отправки или получения)

2. Slice-очередь с использованием срезов

Простейшая очередь на основе среза с операциями добавления в конец и извлечения из начала.

type SliceQueue struct {
    items []interface{}
    mu    sync.Mutex
}

func (q *SliceQueue) Enqueue(item interface{}) {
    q.mu.Lock()
    defer q.mu.Unlock()
    q.items = append(q.items, item)
}

func (q *SliceQueue) Dequeue() interface{} {
    q.mu.Lock()
    defer q.mu.Unlock()
    if len(q.items) == 0 {
        return nil
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item
}

Проблема: При частых операциях удаления происходит постоянное перераспределение памяти, так как срез "сдвигается".

3. Кольцевая буферизированная очередь (Ring Buffer)

Оптимизированная очередь с фиксированным размером, использующая кольцевой буфер для избежания перераспределения памяти.

type RingQueue struct {
    items   []interface{}
    head    int // Индекс начала
    tail    int // Индекс конца
    count   int // Количество элементов
    mu      sync.RWMutex
}

func NewRingQueue(capacity int) *RingQueue {
    return &RingQueue{
        items: make([]interface{}, capacity),
    }
}

func (q *RingQueue) Enqueue(item interface{}) bool {
    q.mu.Lock()
    defer q.mu.Unlock()
    
    if q.count == len(q.items) {
        return false // Очередь полна
    }
    
    q.items[q.tail] = item
    q.tail = (q.tail + 1) % len(q.items)
    q.count++
    return true
}

Преимущества:

• Константное время операций O(1)
• Нет перераспределения памяти
• Эффективное использование памяти

Недостатки:

• Фиксированный размер
• Более сложная логика индексов

4. Двусторонняя очередь (Deque)

Очередь с возможностью добавления/удаления с обоих концов. В Go нет встроенной реализации, но можно использовать контейнерный пакет или реализовать самостоятельно.

type Node struct {
    value interface{}
    next  *Node
    prev  *Node
}

type Deque struct {
    head *Node
    tail *Node
    mu   sync.Mutex
}

func (d *Deque) PushFront(value interface{}) {
    d.mu.Lock()
    defer d.mu.Unlock()
    
    newNode := &Node{value: value}
    if d.head == nil {
        d.head = newNode
        d.tail = newNode
    } else {
        newNode.next = d.head
        d.head.prev = newNode
        d.head = newNode
    }
}

5. Приоритетная очередь (Priority Queue)

Очередь, где элементы извлекаются согласно их приоритету, а не порядку добавления.

import "container/heap"

type Item struct {
    value    string
    priority int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority // Max-heap
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1
    *pq = old[0:n-1]
    return item
}

Применение: планировщики задач, алгоритмы Дейкстры, системы обработки событий.

6. Блокирующие и неблокирующие очереди

• Блокирующие очереди (каналы с буфером 0) — операции блокируют горутину до возможности выполнения
• Неблокирующие очереди — операции возвращают результат немедленно (успех/неудача)

7. Распределенные очереди

Для распределенных систем используются внешние брокеры сообщений:

• RabbitMQ (AMQP протокол)
• Apache Kafka (лог-ориентированная очередь)
• Redis через списки или streams
• NATS (легковесный message broker)

Сравнительная таблица

Критерии выбора очереди

1. Производительность vs Безопасность: Каналы безопасны по умолчанию, но ручные реализации могут быть быстрее
2. Размер очереди: Фиксированный (ring buffer) vs динамический (slice)
3. Блокирующее поведение: Нужно ли блокировать горутины при пустой/полной очереди
4. Приоритетность: FIFO vs приоритетный порядок
5. Распределенность: Локальная vs распределенная очередь

В реальных приложениях на Go чаще всего используются каналы для синхронизации горутин и slice-очереди с мьютексами для более сложных сценариев, требующих гибкости. Для высоконагруженных систем предпочтительнее ring buffer, а для систем с распределенной архитектурой — внешние брокеры сообщений.