Если пришел первым в очередь то каким выйдешь

Если пришёл первым в очередь, то каким выйдешь

Краткий ответ

Первым (англ. FIFO — First In, First Out). Это принцип работы очереди (Queue) в программировании. Если вы первым вошли, вы первым и выйдете, как в реальной жизни.

FIFO: First In, First Out

Очередь работает как в реальной жизни: касса супермаркета, очередь к врачу и т.д.

// Представьте очередь как массив
const queue = [];

// Люди приходят (добавляются в конец)
queue.push('Person1'); // [Person1]
queue.push('Person2'); // [Person1, Person2]
queue.push('Person3'); // [Person1, Person2, Person3]

// Люди уходят (извлекаются с начала)
const first = queue.shift();  // Person1 — первый пришёл, первый ушёл
console.log(queue);            // [Person2, Person3]

Структура данных Queue

class Queue {
  constructor() {
    this.items = [];
  }
  
  // Добавить в конец (Enqueue)
  enqueue(element) {
    this.items.push(element);
  }
  
  // Извлечь из начала (Dequeue)
  dequeue() {
    return this.items.shift();
  }
  
  // Посмотреть первый элемент
  front() {
    return this.items[0];
  }
  
  // Проверить, пуста ли очередь
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Размер очереди
  size() {
    return this.items.length;
  }
}

// Использование
const line = new Queue();
line.enqueue('Alice');  // Очередь: [Alice]
line.enqueue('Bob');    // Очередь: [Alice, Bob]
line.enqueue('Charlie'); // Очередь: [Alice, Bob, Charlie]

console.log(line.front()); // Alice
console.log(line.dequeue()); // Alice (первый пришёл)
console.log(line.dequeue()); // Bob (второй пришёл)
console.log(line.dequeue()); // Charlie (третий пришёл)

FIFO vs LIFO (Stack)

Не путайте с LIFO (Last In, First Out) — это стек:

// Queue (FIFO) — как очередь
const queue = [1, 2, 3];
queue.push(4); // Добавляем в конец [1, 2, 3, 4]
queue.shift(); // Берём из начала -> 1
// Порядок: первый пришёл (1), первый ушёл

// Stack (LIFO) — как стопка тарелок
const stack = [1, 2, 3];
stack.push(4); // Добавляем сверху [1, 2, 3, 4]
stack.pop();   // Берём сверху -> 4
// Порядок: последний пришёл (4), первый ушёл

Оптимизированная реализация Queue

Использование .shift() медленно для больших очередей (O(n)). Лучше использовать указатели:

class OptimizedQueue {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(element) {
    this.items[this.rear] = element;
    this.rear++;
  }
  
  dequeue() {
    if (this.front === this.rear) {
      return undefined; // Очередь пуста
    }
    const result = this.items[this.front];
    delete this.items[this.front];
    this.front++;
    return result;
  }
  
  size() {
    return this.rear - this.front;
  }
}

const queue = new OptimizedQueue();
queue.enqueue('Person1');
queue.enqueue('Person2');
queue.enqueue('Person3');

console.log(queue.dequeue()); // Person1 (первый вышел)
console.log(queue.dequeue()); // Person2
console.log(queue.dequeue()); // Person3

Примеры использования Queue в реальном коде

1. JavaScript Task Queue (Event Loop)

Браузер использует очередь для обработки задач:

console.log('1. Синхронный код');

setTimeout(() => {
  console.log('3. Из очереди (макротаска)');
}, 0);

Promise.resolve().then(() => {
  console.log('2. Из микротаск очереди');
});

console.log('1. Синхронный код');

// Вывод:
// 1. Синхронный код
// 1. Синхронный код
// 2. Из микротаск очереди
// 3. Из очереди (макротаска)

2. BFS (Поиск в ширину) в графах

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  
  while (queue.length > 0) {
    const node = queue.shift(); // Берём первый
    console.log(node);
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor); // Добавляем в конец
        visited.add(neighbor);
      }
    }
  }
}

const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': [],
  'F': []
};

bfs(graph, 'A');
// Вывод: A -> B -> C -> D -> E -> F
// Порядок обхода — слой за слоем (BFS)

3. Обработка запросов на сервере

class RequestQueue {
  constructor(concurrency = 2) {
    this.queue = [];
    this.processing = 0;
    this.concurrency = concurrency;
  }
  
  async add(task) {
    this.queue.push(task);
    await this.process();
  }
  
  async process() {
    while (this.queue.length > 0 && this.processing < this.concurrency) {
      const task = this.queue.shift(); // FIFO — первый пришёл, первый выполнится
      this.processing++;
      
      try {
        await task();
      } finally {
        this.processing--;
        if (this.queue.length > 0) {
          await this.process();
        }
      }
    }
  }
}

const queue = new RequestQueue(2); // Максимум 2 одновременно

queue.add(async () => {
  console.log('Request 1 started');
  await new Promise(r => setTimeout(r, 1000));
  console.log('Request 1 done');
});

queue.add(async () => {
  console.log('Request 2 started');
  await new Promise(r => setTimeout(r, 500));
  console.log('Request 2 done');
});

4. Printer Queue (пример очереди печати)

class PrinterQueue {
  constructor() {
    this.queue = [];
    this.printing = false;
  }
  
  addDocument(doc) {
    this.queue.push(doc);
    console.log(`Документ "${doc}" добавлен в очередь`);
    this.printNext();
  }
  
  printNext() {
    if (this.printing || this.queue.length === 0) return;
    
    this.printing = true;
    const doc = this.queue.shift(); // Первый добавленный печатается первым
    
    console.log(`Печать: ${doc}`);
    setTimeout(() => {
      console.log(`Завершена печать: ${doc}`);
      this.printing = false;
      this.printNext();
    }, 1000);
  }
}

const printer = new PrinterQueue();
printer.addDocument('Report.pdf');      // Начнёт печать сразу
printer.addDocument('Invoice.docx');    // Будет ждать
printer.addDocument('Presentation.pptx'); // Будет ждать

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

Операция        Простая Queue   Оптимизированная Queue
─────────────────────────────────────────────────────
enqueue()       O(1)           O(1)
dequeue()       O(n)           O(1)
front()         O(1)           O(1)
size()          O(1)           O(1)

Различные типы очередей

1. Простая Queue (FIFO) — рассмотрели выше
2. Priority Queue — элементы выходят по приоритету, не по порядку
3. Deque (Double-ended Queue) — добавлять и извлекать с обоих концов
4. Circular Queue — конец связан с началом

Вывод

• Если пришёл первым в очередь, выйдешь первым (FIFO)
• Queue — фундаментальная структура данных в программировании
• Используется в алгоритмах (BFS), обработке задач, системах очередей
• Оптимизированная реализация важна для производительности
• JavaScript async/await и микротаски работают с очередями