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

Разница между Stack и Очередью (Queue)

Stack (стек) и Queue (очередь) — это две фундаментальные структуры данных, которые отличаются порядком добавления и удаления элементов. Несмотря на кажущуюся простоту, они критичны для понимания алгоритмов и архитектуры приложений.

Stack (LIFO — Last In, First Out)

Stack — это структура, где последний добавленный элемент удаляется первым. Представь стопку тарелок: кладешь, кладешь, берешь верхнюю.

class Stack {
  constructor() {
    this.items = [];
  }
  
  // push - добавить элемент (в конец)
  push(element) {
    this.items.push(element);
  }
  
  // pop - удалить и получить последний элемент
  pop() {
    return this.items.pop();
  }
  
  // peek - посмотреть последний элемент без удаления
  peek() {
    return this.items[this.items.length - 1];
  }
  
  // isEmpty
  isEmpty() {
    return this.items.length === 0;
  }
  
  // size
  size() {
    return this.items.length;
  }
}

// Использование
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

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

Визуализация Stack:

После push(1), push(2), push(3):

| 3 | <- pop() вернет 3
| 2 |
| 1 |
------

Queue (FIFO — First In, First Out)

Queue — это структура, где первый добавленный элемент удаляется первым. Представь очередь в магазине: кто первый встал, тот первый выходит.

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

// Использование
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue());  // 1 (первый добавленный)
console.log(queue.dequeue());  // 2
console.log(queue.dequeue());  // 3

Визуализация Queue:

После enqueue(1), enqueue(2), enqueue(3):

| 1 | <- dequeue() вернет 1 (первый)
| 2 |
| 3 |
--------

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

Практические применения в Frontend

Stack:

1. История навигации браузера

class BrowserHistory {
  constructor() {
    this.backStack = new Stack();
    this.forwardStack = new Stack();
  }
  
  visitPage(page) {
    this.backStack.push(page);
    this.forwardStack.clear(); // Очищаем forward при новом посещении
  }
  
  back() {
    const current = this.backStack.pop();
    this.forwardStack.push(current);
    return this.backStack.peek();
  }
  
  forward() {
    const page = this.forwardStack.pop();
    this.backStack.push(page);
    return page;
  }
}

1. Проверка скобок

function isBalanced(str) {
  const stack = new Stack();
  const pairs = { '(': ')', '{': '}', '[': ']' };
  
  for (const char of str) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (char === ')' || char === '}' || char === ']') {
      const top = stack.pop();
      if (pairs[top] !== char) {
        return false;
      }
    }
  }
  
  return stack.isEmpty();
}

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

1. Система отмены (Undo/Redo)

class TextEditor {
  constructor() {
    this.undoStack = new Stack();
    this.redoStack = new Stack();
    this.text = '';
  }
  
  type(char) {
    this.undoStack.push(this.text);
    this.text += char;
    this.redoStack.clear();
  }
  
  undo() {
    if (!this.undoStack.isEmpty()) {
      this.redoStack.push(this.text);
      this.text = this.undoStack.pop();
    }
  }
  
  redo() {
    if (!this.redoStack.isEmpty()) {
      this.undoStack.push(this.text);
      this.text = this.redoStack.pop();
    }
  }
}

Queue:

1. Асинхронные задачи (Event Loop)

// JavaScript Event Loop использует Queue

console.log('1');

setTimeout(() => {
  console.log('2');
}, 0);

console.log('3');

// Вывод:
// 1
// 3
// 2 (в конце, из macrotask queue)

// setTimeout колбэк добавляется в Queue
// и выполняется после основного кода

1. Обработка задач в очереди

class TaskQueue {
  constructor() {
    this.queue = new Queue();
    this.isProcessing = false;
  }
  
  addTask(task) {
    this.queue.enqueue(task);
    if (!this.isProcessing) {
      this.processTasks();
    }
  }
  
  async processTasks() {
    this.isProcessing = true;
    
    while (!this.queue.isEmpty()) {
      const task = this.queue.dequeue();
      await task();
    }
    
    this.isProcessing = false;
  }
}

const taskQueue = new TaskQueue();
taskQueue.addTask(async () => {
  console.log('Task 1');
  await new Promise(r => setTimeout(r, 1000));
});
taskQueue.addTask(() => console.log('Task 2'));
// Выведет:
// Task 1
// (ждет 1 сек)
// Task 2

1. Очередь сообщений для обработки

class MessageQueue {
  constructor() {
    this.queue = new Queue();
  }
  
  publish(message) {
    this.queue.enqueue(message);
  }
  
  getNextMessage() {
    return this.queue.dequeue();
  }
  
  processAll(callback) {
    while (!this.queue.isEmpty()) {
      const message = this.queue.dequeue();
      callback(message);
    }
  }
}

Ключевые различия для интервью

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

Array.shift() медленный (O(n)), лучше использовать объект:

class OptimizedQueue {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(element) {
    this.items[this.rear] = element;
    this.rear++;
  }
  
  dequeue() {
    const element = this.items[this.front];
    delete this.items[this.front];
    this.front++;
    return element;
  }
  
  size() {
    return this.rear - this.front;
  }
}

Эта реализация работает за O(1) вместо O(n) для удаления.