Стек и очередь: полное руководство с реализацией на JavaScript и Python

Почему стек и очередь важны?

Стек и очередь — фундаментальные структуры данных, без которых невозможно представить программирование:

• 🏗️ Основа для понимания более сложных структур
• 🔧 Используются повсеместно: браузеры, ОС, компиляторы
• 💼 Обязательные вопросы на собеседованиях
• 🧩 Ключ к решению многих алгоритмических задач
• ⚡ Операции за O(1) — максимальная эффективность

Стек (Stack)

Что такое стек?

Стек — структура данных, работающая по принципу LIFO (Last In, First Out) — последний вошёл, первый вышел.

Аналогия: стопка тарелок
┌─────────┐
│  Новая  │  ← push (добавить сверху)
├─────────┤
│ Тарелка │
├─────────┤
│ Тарелка │
├─────────┤
│ Тарелка │  ← pop (взять сверху)
└─────────┘

Можно взять только верхнюю тарелку!

Основные операции

Реализация стека на JavaScript

// Реализация на основе массива
class Stack {
  constructor() {
    this.items = [];
  }

  // Добавить элемент
  push(element) {
    this.items.push(element);
  }

  // Удалить и вернуть верхний элемент
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

  // Посмотреть верхний элемент
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  // Проверить пустой ли стек
  isEmpty() {
    return this.items.length === 0;
  }

  // Размер стека
  size() {
    return this.items.length;
  }

  // Очистить стек
  clear() {
    this.items = [];
  }

  // Вывести содержимое
  print() {
    console.log(this.items.toString());
  }
}

// Использование
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.peek());  // 30
console.log(stack.pop());   // 30
console.log(stack.pop());   // 20
console.log(stack.size());  // 1

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Реализация стека на Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """Добавить элемент на вершину"""
        self.items.append(item)

    def pop(self):
        """Удалить и вернуть верхний элемент"""
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self):
        """Посмотреть верхний элемент"""
        if self.is_empty():
            return None
        return self.items[-1]

    def is_empty(self):
        """Проверить пустой ли стек"""
        return len(self.items) == 0

    def size(self):
        """Количество элементов"""
        return len(self.items)

    def clear(self):
        """Очистить стек"""
        self.items = []


# Использование
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print(stack.peek())  # 30
print(stack.pop())   # 30
print(stack.size())  # 2

# Альтернатива: использовать list напрямую
stack = []
stack.append(10)  # push
stack.append(20)
stack.pop()       # pop -> 20

Где используется стек?

1. История браузера — кнопка "Назад"
2. Undo/Redo — отмена действий в редакторах
3. Стек вызовов — выполнение функций в программе
4. Парсинг выражений — проверка скобок, вычисление формул
5. DFS (поиск в глубину) — обход графов и деревьев
6. Рекурсия — каждый вызов функции кладётся в стек

Очередь (Queue)

Что такое очередь?

Очередь — структура данных, работающая по принципу FIFO (First In, First Out) — первый вошёл, первый вышел.

Аналогия: очередь в магазине

Вход →  [Новый] [Клиент] [Клиент] [Клиент]  → Выход
         enqueue                              dequeue

Кто первый пришёл, тот первый уйдёт!

Основные операции

*O(1) при правильной реализации

Реализация очереди на JavaScript

// Простая реализация (неоптимальный dequeue — O(n))
class SimpleQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();  // O(n) — сдвиг всех элементов!
  }

  front() {
    if (this.isEmpty()) return null;
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Оптимизированная реализация с O(1) для всех операций
class Queue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  enqueue(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }

  dequeue() {
    if (this.isEmpty()) return null;

    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }

  front() {
    if (this.isEmpty()) return null;
    return this.items[this.frontIndex];
  }

  isEmpty() {
    return this.backIndex === this.frontIndex;
  }

  size() {
    return this.backIndex - this.frontIndex;
  }
}

// Использование
const queue = new Queue();
queue.enqueue('A');
queue.enqueue('B');
queue.enqueue('C');

console.log(queue.front());    // 'A'
console.log(queue.dequeue());  // 'A'
console.log(queue.dequeue());  // 'B'
console.log(queue.size());     // 1

Реализация очереди на Python

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        """Добавить элемент в конец"""
        self.items.append(item)

    def dequeue(self):
        """Удалить и вернуть первый элемент"""
        if self.is_empty():
            return None
        return self.items.pop(0)  # O(n) — не оптимально!

    def front(self):
        """Посмотреть первый элемент"""
        if self.is_empty():
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


# Оптимальная реализация с collections.deque
from collections import deque

class OptimalQueue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)  # O(1)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.popleft()  # O(1)!

    def front(self):
        if self.is_empty():
            return None
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


# Использование
queue = OptimalQueue()
queue.enqueue('A')
queue.enqueue('B')
queue.enqueue('C')

print(queue.dequeue())  # 'A'
print(queue.front())    # 'B'

Где используется очередь?

1. Очередь печати — задания на принтер
2. BFS (поиск в ширину) — обход графов
3. Буферизация — потоковое видео, клавиатура
4. Планировщик задач — обработка запросов на сервере
5. Асинхронная обработка — очереди сообщений (RabbitMQ, Kafka)

Deque (Двусторонняя очередь)

Deque (Double-Ended Queue) — очередь, в которой можно добавлять и удалять элементы с обоих концов.

class Deque {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  // Добавить в начало
  addFront(element) {
    this.frontIndex--;
    this.items[this.frontIndex] = element;
  }

  // Добавить в конец
  addBack(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }

  // Удалить из начала
  removeFront() {
    if (this.isEmpty()) return null;
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }

  // Удалить из конца
  removeBack() {
    if (this.isEmpty()) return null;
    this.backIndex--;
    const item = this.items[this.backIndex];
    delete this.items[this.backIndex];
    return item;
  }

  peekFront() {
    return this.items[this.frontIndex];
  }

  peekBack() {
    return this.items[this.backIndex - 1];
  }

  isEmpty() {
    return this.backIndex === this.frontIndex;
  }

  size() {
    return this.backIndex - this.frontIndex;
  }
}

from collections import deque

# Python deque — встроенная реализация
d = deque()

d.append('B')        # Добавить справа: [B]
d.append('C')        # [B, C]
d.appendleft('A')    # Добавить слева: [A, B, C]

d.pop()              # Удалить справа: C
d.popleft()          # Удалить слева: A

# Результат: [B]

Популярные задачи на стек

Задача 1: Валидные скобки

// Проверить, правильно ли расставлены скобки
// "()[]{}" -> true
// "([)]" -> false
// "{[]}" -> true

function isValid(s) {
  const stack = [];
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

console.log(isValid("()[]{}")); // true
console.log(isValid("([)]"));   // false
console.log(isValid("{[]}"));   // true

Задача 2: Минимальный стек

// Стек с операцией getMin() за O(1)

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];  // Хранит минимумы
  }

  push(val) {
    this.stack.push(val);

    // Добавляем в minStack если это новый минимум
    if (this.minStack.length === 0 || val <= this.getMin()) {
      this.minStack.push(val);
    }
  }

  pop() {
    const val = this.stack.pop();

    // Если удаляем текущий минимум — удаляем из minStack
    if (val === this.getMin()) {
      this.minStack.pop();
    }

    return val;
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(5);
minStack.push(2);
minStack.push(7);
console.log(minStack.getMin()); // 2
minStack.pop();
console.log(minStack.getMin()); // 2
minStack.pop();
console.log(minStack.getMin()); // 5

Задача 3: Вычисление обратной польской нотации

// ["2","1","+","3","*"] -> (2 + 1) * 3 = 9
// ["4","13","5","/","+"] -> 4 + (13 / 5) = 6

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const b = stack.pop();
      const a = stack.pop();

      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(parseInt(token));
    }
  }

  return stack.pop();
}

console.log(evalRPN(["2","1","+","3","*"])); // 9

Задача 4: Ежедневные температуры

// Для каждого дня найти через сколько дней будет теплее
// [73,74,75,71,69,72,76,73] -> [1,1,4,2,1,1,0,0]

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = [];  // Хранит индексы

  for (let i = 0; i < n; i++) {
    // Пока текущая температура выше чем на вершине стека
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      result[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }

  return result;
}

console.log(dailyTemperatures([73,74,75,71,69,72,76,73]));
// [1, 1, 4, 2, 1, 1, 0, 0]

Популярные задачи на очередь

Задача 1: Реализация стека через две очереди

class StackUsingQueues {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }

  push(x) {
    // Добавляем в пустую очередь
    this.q2.push(x);

    // Переносим все из q1 в q2
    while (this.q1.length > 0) {
      this.q2.push(this.q1.shift());
    }

    // Меняем очереди местами
    [this.q1, this.q2] = [this.q2, this.q1];
  }

  pop() {
    return this.q1.shift();
  }

  top() {
    return this.q1[0];
  }

  empty() {
    return this.q1.length === 0;
  }
}

Задача 2: Скользящее окно максимумов

from collections import deque

def maxSlidingWindow(nums, k):
    """
    Найти максимум в каждом окне размера k
    nums = [1,3,-1,-3,5,3,6,7], k = 3
    Результат: [3,3,5,5,6,7]
    """
    result = []
    dq = deque()  # Хранит индексы

    for i in range(len(nums)):
        # Удаляем элементы вне окна
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Удаляем меньшие элементы (они не могут быть максимумом)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Добавляем максимум в результат (начиная с k-1)
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

Задача 3: Первый уникальный символ в потоке

class FirstUnique {
  constructor() {
    this.queue = [];
    this.count = new Map();
  }

  add(char) {
    this.count.set(char, (this.count.get(char) || 0) + 1);
    this.queue.push(char);
  }

  getFirstUnique() {
    while (this.queue.length > 0) {
      const front = this.queue[0];
      if (this.count.get(front) === 1) {
        return front;
      }
      this.queue.shift();  // Удаляем неуникальный
    }
    return null;
  }
}

const fu = new FirstUnique();
fu.add('a');
console.log(fu.getFirstUnique()); // 'a'
fu.add('b');
console.log(fu.getFirstUnique()); // 'a'
fu.add('a');
console.log(fu.getFirstUnique()); // 'b'

Сравнение: стек vs очередь

СТЕК (LIFO)              ОЧЕРЕДЬ (FIFO)
    ┌───┐
    │ 3 │ ← top              Вход → [1] [2] [3] → Выход
    ├───┤                           front    back
    │ 2 │
    ├───┤
    │ 1 │
    └───┘

push(4):                 enqueue(4):
    ┌───┐
    │ 4 │ ← new top      [1] [2] [3] [4]
    ├───┤                            ↑ new
    │ 3 │
    ...

pop() → 4                dequeue() → 1
    ┌───┐
    │ 3 │ ← new top      [2] [3] [4]
    ...                   ↑ new front

Приоритетная очередь

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

import heapq

# Min-Heap (минимальный элемент первым)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)

print(heapq.heappop(pq))  # 1 (минимальный)
print(heapq.heappop(pq))  # 2
print(heapq.heappop(pq))  # 3

# Max-Heap (используем отрицательные числа)
pq = []
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
heapq.heappush(pq, -2)

print(-heapq.heappop(pq))  # 3 (максимальный)

// JavaScript: нет встроенной приоритетной очереди
// Нужно использовать библиотеку или реализовать на основе heap

Заключение

Стек и очередь — фундаментальные структуры данных:

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