В чем разница между очередью от стеком?

В чем разница между очередью и стеком?

Это две фундаментальные структуры данных в информатике, важные для понимания JavaScript. Хотя вопрос базовый, разработчик должен глубоко их понимать.

Стек (Stack) - LIFO

Стек работает по принципу LIFO (Last-In-First-Out) — последний добавленный элемент удаляется первым. Как стопка тарелок.

class Stack {
  constructor() { this.items = []; }
  push(e) { this.items.push(e); }
  pop() { return this.items.pop(); }
  peek() { return this.items[this.items.length - 1]; }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3 - последний добавленный

Очередь (Queue) - FIFO

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

class Queue {
  constructor() { this.items = []; }
  enqueue(e) { this.items.push(e); }
  dequeue() { return this.items.shift(); }
  peek() { return this.items[0]; }
}

const queue = new Queue();
queue.enqueue('Alice');
queue.enqueue('Bob');
console.log(queue.dequeue()); // 'Alice' - первый

Основные различия

Call Stack - стек вызовов

В JavaScript стек вызовов определяет порядок выполнения функций.

function a() { b(); }
function b() { c(); }
function c() { console.log('c'); }
a();

// Call Stack: [] → [a] → [a,b] → [a,b,c] → [a,b] → [a] → []
// Вывод: c

Undo/Redo - практический пример стека

class TextEditor {
  constructor() {
    this.text = '';
    this.undoStack = [];
  }
  add(char) {
    this.undoStack.push(this.text);
    this.text += char;
  }
  undo() {
    if (this.undoStack.length > 0) {
      this.text = this.undoStack.pop();
    }
  }
}

Event Loop - очередь макротасков

В браузере Event Loop использует очередь для обработки макротасков.

console.log('1');
setTimeout(() => console.log('2'), 0);
setTimeout(() => console.log('3'), 0);
console.log('4');

// Вывод: 1, 4, 2, 3
// setTimeout callback'и обрабатываются в очередь FIFO

Проверка скобок - использование стека

function isBalanced(str) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  
  for (let char of str) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (pairs[char]) {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[}])')); // false

BFS - поиск в ширину с очередью

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  const result = [];
  
  while (queue.length > 0) {
    const node = queue.shift(); // FIFO
    result.push(node);
    
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

Асинхронная очередь задач

class TaskQueue {
  constructor() {
    this.queue = [];
    this.processing = false;
  }
  
  addTask(task) {
    this.queue.push(task);
    this.process();
  }
  
  async process() {
    if (this.processing || this.queue.length === 0) return;
    
    this.processing = true;
    while (this.queue.length > 0) {
      const task = this.queue.shift(); // FIFO
      await task();
    }
    this.processing = false;
  }
}

const tq = new TaskQueue();
tq.addTask(async () => console.log('Task 1'));
tq.addTask(async () => console.log('Task 2'));
// Вывод: Task 1, затем Task 2

DFS - поиск в глубину со стеком

function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];
  
  while (stack.length > 0) {
    const node = stack.pop(); // LIFO
    if (visited.has(node)) continue;
    
    visited.add(node);
    result.push(node);
    
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return result;
}

Event Loop - полная картина

console.log('1'); // Call Stack
setTimeout(() => console.log('2'), 0); // Макротаски
Promise.resolve().then(() => console.log('3')); // Микротаски
console.log('4'); // Call Stack

// Вывод: 1, 4, 3, 2
// Порядок:
// 1. Стек вызовов (синхронный код)
// 2. Микротаски (Promise) - высокий приоритет
// 3. Макротаски (setTimeout) - низкий приоритет

Когда использовать

Стек:

• Откат операций (Undo/Redo)
• Рекурсия и вложенные вызовы
• Поиск в глубину (DFS)
• Парсинг выражений

Очередь:

• Планирование задач (Task Queue)
• Асинхронные операции
• Поиск в ширину (BFS)
• Event Loop (макротаски)

Производительность

Стек: O(1) для push/pop

Очередь с shift(): O(n) для dequeue (медленно)

Оптимальная очередь с индексами: O(1) для всех операций

// Быстрая очередь
class FastQueue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(e) {
    this.items[this.tail++] = e;
  }
  dequeue() {
    const result = this.items[this.head];
    delete this.items[this.head++];
    return result;
  }
}

Заключение

Стек (LIFO): последний добавленный элемент удаляется первым. Используется для Call Stack, Undo/Redo, DFS поиска, проверки скобок.

Очередь (FIFO): первый добавленный элемент удаляется первым. Используется для Event Loop, планирования задач, BFS поиска, асинхронных операций.

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