Очереди и деки

FIFO правило:

Очередь это линейная структура данных где вставки происходят на одном конце (спине) и удаления на другом (передней). Правило это FIFO (первый вошедший, первый вышедший): элемент добавленный первый это тот что удаляется первый.

Представь очередь на кассе в магазине. Покупатели присоединяются сзади и уходят с передней. Первый что присоединился это первый что платит и уходит. Ты никогда не перепрыгиваешь; никто не режет перед. Это FIFO.

Две операции:

1. Enqueue: Добавь элемент на спину очереди. Возвращает ничего; обновляет очередь на месте.
2. Dequeue: Удали и верни передний элемент очереди. Если очередь пуста, или верни null или подними ошибку (зависит от реализации).

Есть также часто передний или peek операция видеть передний элемент без удаления.

const queue = [];  // Пустая очередь

// Enqueue: добавь 10, 20, 30
queue.push(10);    // Очередь: [10]
queue.push(20);    // Очередь: [10, 20]
queue.push(30);    // Очередь: [10, 20, 30]

// Peek: видь передний
console.log(queue[0]);  // 10 (без удаления)

// Dequeue: удали передний
// НЕ используй queue.shift() в реальной очереди! Это O(n).
const front = queue[0];
queue = queue.slice(1);  // Неэффективно! Почему?

Почему .shift() это O(n), и как это исправить:

Когда ты используешь JavaScript .shift() или удаляешь с передней части массива, язык должен переиндексировать все оставшиеся элементы:

До:     [10, 20, 30, 40]  (индексы 0, 1, 2, 3)
Удали индекс 0 (10).
После:  [20, 30, 40]      (индексы 0, 1, 2)
        ↑  Переиндексируй все!

Это переиндексирование это O(n) работа. Если ты зовёшь dequeue n раз, это стоит O(n²) итого — очень дорого.

Решение 1: используй front и rear указатели.

Вместо удаления, держи front указатель. Enqueue идёт на спину; dequeue инкрементирует передний указатель.

class Queue {
  constructor() {
    this.items = [];
    this.front = 0;  // Указатель на передний
  }
  
  enqueue(value) {
    this.items.push(value);
  }
  
  dequeue() {
    if (this.front >= this.items.length) return null;
    const value = this.items[this.front];
    this.front++;
    return value;
  }
  
  peek() {
    if (this.front >= this.items.length) return null;
    return this.items[this.front];
  }
  
  isEmpty() {
    return this.front >= this.items.length;
  }
}

Теперь и enqueue и dequeue это O(1). Но есть проблема: front указатель только движется вперёд. После многих dequeues, передняя часть массива это потраченное пространство. Если ты dequeue 1000 элементов, первые 1000 слотов никогда не переиспользуются.

Решение 2: используй circular buffer.

Circular buffer оборачивается. Когда ты достигаешь конца массива, следующий enqueue идёт назад на индекс 0 (если этот слот пуст). Это переиспользует пространство и держит оба конца O(1):

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }
  
  enqueue(value) {
    if (this.size === this.capacity) {
      // Очередь полна. Вырасти в массиве.
      this._resize();
    }
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = value;
    this.size++;
  }
  
  dequeue() {
    if (this.size === 0) return null;
    const value = this.items[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return value;
  }
  
  peek() {
    if (this.size === 0) return null;
    return this.items[this.front];
  }
  
  _resize() {
    const newCapacity = this.capacity * 2;
    const newItems = new Array(newCapacity);
    for (let i = 0; i < this.size; i++) {
      newItems[i] = this.items[(this.front + i) % this.capacity];
    }
    this.items = newItems;
    this.front = 0;
    this.rear = this.size - 1;
    this.capacity = newCapacity;
  }
}

Модуло % оператор оборачивает указатели: когда rear достигает конца, оно оборачивается на 0.

Решение 3: используй связный список.

Связный список естественно поддерживает O(1) вставку в хвост и O(1) удаление в голове:

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class QueueLinkedList {
  constructor() {
    this.head = null;  // Передний очереди
    this.tail = null;  // Спина очереди
  }
  
  enqueue(value) {
    const newNode = new Node(value);
    if (this.tail === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
  dequeue() {
    if (this.head === null) return null;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null;
    return value;
  }
  
  peek() {
    if (this.head === null) return null;
    return this.head.value;
  }
  
  isEmpty() {
    return this.head === null;
  }
}

Дек: очереди на обоих концах

Дек (двухконечная очередь) позволяет вставку и удаление на обоих концах. Ты можешь push и pop с передней и спины. Дек реализованный с двусвязный список или circular buffer поддерживает все четыре операции за O(1):

class Deque {
  constructor() {
    this.items = [];
    this.front = 0;
    this.rear = -1;
    this.size = 0;
  }
  
  pushBack(value) {
    this.items.push(value);
    this.rear++;
    this.size++;
  }
  
  pushFront(value) {
    this.items.unshift(value);
    this.rear++;
    this.size++;
  }
  
  popBack() {
    if (this.size === 0) return null;
    this.size--;
    this.rear--;
    return this.items.pop();
  }
  
  popFront() {
    if (this.size === 0) return null;
    this.size--;
    this.front++;
    return this.items.shift();  // Это O(n)!
  }
  
  peekFront() {
    if (this.size === 0) return null;
    return this.items[this.front];
  }
  
  peekBack() {
    if (this.size === 0) return null;
    return this.items[this.rear];
  }
}

Заметь: выше наивный дек это неэффективный (popFront используешь .shift()). Правильный дек используешь circular buffer или двусвязный список гарантировать O(1) для всех операций.