Задача: создать очередь с помощью стеков
2026-02-21 01:08 Diff
https://skillbox.ru/media/code/zadacha-sozdat-ochered-s-pomoshchyu-stekov/

#статьи

  • 21 ноя 2022
  • 0

Задача: создать очередь с помощью стеков

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся понять, как сделать очередь из нескольких стеков.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Реализовать first-in-first-out (FIFO) очередь, используя максимум два стека. Она должна поддерживать все стандартные функции обычной очереди — push, pop, peek и empty.

  • push — добавляет элемент в конец очереди;
  • pop — убирает элемент из начала и возвращает его как результат;
  • peek — возвращает элемент из начала очереди, но не убирает его;
  • empty — возвращает true, если очередь пустая, иначе — false.

Примечание: вы должны использовать только стандартные операции со стеками — push, peek/pop, size и empty. А если ваш язык не поддерживает стеки, то их можно реализовать через обычный список или двустороннюю очередь, но при этом использовать только функции, приведённые выше.

Ввод: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Вывод: [null, null, null, 1, 1, false] Пояснение: MyQueue myQueue = new MyQueue(); myQueue.push(1); // очередь: [1] myQueue.push(2); // очередь: [1, 2] (начало очереди — самый левый элемент) myQueue.peek(); // вернёт 1 myQueue.pop(); // вернёт 1, очередь: [2] myQueue.empty(); // вернёт false

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Мы будем решать задачу с помощью двух стеков. Самое сложное — реализовать методы pop и peak. Но для начала давайте создадим наш класс:

static class MyQueue { Stack<Integer> current; Stack<Integer> tmp; public MyQueue() { current = new Stack<>(); tmp = new Stack<>(); }

Теперь давайте реализуем метод push:

public void push(int x) { current.push(x); }

Всё просто — добавляем новый элемент в стек current.

Теперь давайте напишем метод pop. Для него нам нужно переместить все элементы из стека current в стек tmp. А перед этим — проверить стек tmp: если в нём есть элементы, то нам просто нужно вернуть элемент из этого стека.

В виде кода это выглядит так:

public int pop() { if (!tmp.isEmpty()) { return tmp.pop(); } while (!current.isEmpty()) { tmp.push(current.pop()); } return tmp.pop();

Чтобы продемонстрировать правильность работы этой фукнции, давайте посмотрим на пример:

  • push 1 → 1;
  • push 2 → 2, 1;
  • push 3 → 3, 2, 1;
  • pop → перемещаем всё в tmp: cur: 2, 1; tmp: 3 → cur: 1; tmp: 2, 3 → cur: ; tmp: 1, 2, 3;
  • теперь все элементы в tmp стоят в правильном порядке.

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

Теперь по похожей логике давайте напишем функцию peek:

public int peek() { if (!tmp.isEmpty()) { return tmp.peek(); } while (!current.isEmpty()) { tmp.push(current.pop()); } return tmp.peek();

И последнее — метод empty:

public boolean empty() { if (!tmp.isEmpty()) { return tmp.isEmpty(); } return current.isEmpty(); }

Здесь нам важно не забыть проверить вторую очередь.

Результаты

Временная сложность: лучший случай — O(1), худший — O(n).

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

Научитесь: Профессия Java-разработчик + ИИ Узнать больше