Реализовать Queue на слайсе

Решение: Реализовать Queue на слайсе

Основная идея

Queue (очередь) — структура данных FIFO (First In, First Out). Элементы добавляются с конца и удаляются с начала. На слайсе это неэффективно для каждого `Dequeue()`, так как нужно смещать все элементы. Однако для учебных целей можно использовать простой подход или оптимизированный с индексами.

Наивный подход: с копированием

type Queue struct {
    items []int
}

func NewQueue() *Queue {
    return &Queue{
        items: make([]int, 0),
    }
}

func (q *Queue) Enqueue(val int) {
    q.items = append(q.items, val)
}

func (q *Queue) Dequeue() (int, bool) {
    if len(q.items) == 0 {
        return 0, false
    }
    val := q.items[0]
    q.items = q.items[1:]
    return val, true
}

func (q *Queue) Front() (int, bool) {
    if len(q.items) == 0 {
        return 0, false
    }
    return q.items[0], true
}

func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}

func (q *Queue) Size() int {
    return len(q.items)
}

Проблемы: Dequeue() имеет O(n) сложность из-за смещения элементов. Для большой очереди это неэффективно.

Оптимизированный подход: с индексами (рекомендуется)

type Queue struct {
    items []int
    front int // индекс первого элемента
    rear  int // индекс для добавления нового элемента
    size  int // текущий размер
}

func NewQueue() *Queue {
    return &Queue{
        items: make([]int, 10), // начальная ёмкость
        front: 0,
        rear:  0,
        size:  0,
    }
}

func (q *Queue) Enqueue(val int) {
    // Если очередь заполнена, расширяем
    if q.size == len(q.items) {
        q.resize()
    }
    
    q.items[q.rear] = val
    q.rear = (q.rear + 1) % len(q.items) // циклический буфер
    q.size++
}

func (q *Queue) Dequeue() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    
    val := q.items[q.front]
    q.front = (q.front + 1) % len(q.items) // циклический буфер
    q.size--
    
    return val, true
}

func (q *Queue) Front() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    return q.items[q.front], true
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Size() int {
    return q.size
}

func (q *Queue) resize() {
    // Новая ёмкость в 2 раза больше
    newCapacity := len(q.items) * 2
    newItems := make([]int, newCapacity)
    
    // Копируем элементы в новый слайс в правильном порядке
    for i := 0; i < q.size; i++ {
        newItems[i] = q.items[(q.front+i)%len(q.items)]
    }
    
    q.items = newItems
    q.front = 0
    q.rear = q.size
}

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

• Enqueue: O(1) в среднем (при амортизации)
• Dequeue: O(1) всегда
• Память эффективно использует циклический буфер

Пример использования

q := NewQueue()

// Добавляем элементы
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println("Size:", q.Size()) // 3

// Читаем первый элемент
val, _ := q.Front()
fmt.Println("Front:", val) // 2

// Удаляем элемент
val, ok := q.Dequeue()
fmt.Println("Dequeue:", val, ok) // 1, true

fmt.Println("Size:", q.Size()) // 2
fmt.Println("IsEmpty:", q.IsEmpty()) // false

// Удаляем оставшиеся
q.Dequeue() // 2
q.Dequeue() // 3
fmt.Println("IsEmpty:", q.IsEmpty()) // true

// Пустая очередь
val, ok = q.Dequeue()
fmt.Println("Dequeue from empty:", val, ok) // 0, false

Версия с циклическим буфером (более компактно)

type Queue struct {
    data  []int
    front int
    size  int
}

func NewQueue() *Queue {
    return &Queue{
        data: make([]int, 10),
    }
}

func (q *Queue) Enqueue(val int) {
    if q.size == len(q.data) {
        q.resize()
    }
    index := (q.front + q.size) % len(q.data)
    q.data[index] = val
    q.size++
}

func (q *Queue) Dequeue() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    val := q.data[q.front]
    q.front = (q.front + 1) % len(q.data)
    q.size--
    return val, true
}

func (q *Queue) Front() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    return q.data[q.front], true
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Size() int {
    return q.size
}

func (q *Queue) resize() {
    newData := make([]int, len(q.data)*2)
    for i := 0; i < q.size; i++ {
        newData[i] = q.data[(q.front+i)%len(q.data)]
    }
    q.data = newData
    q.front = 0
}

Сложность операций

Ключевые моменты

• Циклический буфер: (index + 1) % capacity позволяет переиспользовать ячейки
• Resize при заполнении: амортизированная O(1) для Enqueue
• Индексы вместо копирования: избегает O(n) операции для каждого Dequeue
• Потокобезопасность: если нужна, используйте мьютекс или sync.Queue
• Дженерики: в Go 1.18+ можно использовать type Queue[T any] для универсальности

Это стандартная реализация очереди, которая используется в production кодобазах.