Все
Истории
Дизайн
Код
Геймдев
Бизнес
Маркетинг
Управление
Кино
Музыка
Проектная фотография
Развитие
Здоровье
Деньги
Образование
EdTech
Корп. обучение
Блог Skillbox
Глоссарий
Спецпроекты
Профориентация
Задача: создать очередь с помощью стеков
Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся понять, как сделать очередь из нескольких стеков.
Сергей Голицын
Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.
Условие. Реализовать first-in-first-out (FIFO) очередь, используя максимум два стека. Она должна поддерживать все стандартные функции обычной очереди — push, pop, peek и empty.
- push — добавляет элемент в конец очереди;
- pop — убирает элемент из начала и возвращает его как результат;
- peek — возвращает элемент из начала очереди, но не убирает его;
- empty — возвращает true, если очередь пустая, иначе — false.
Примечание: вы должны использовать только стандартные операции со стеками — push, peek/pop, size и empty. А если ваш язык не поддерживает стеки, то их можно реализовать через обычный список или двустороннюю очередь, но при этом использовать только функции, приведённые выше.
Ввод и вывод. Пример 1
Ввод:
["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) — нам нужно заранее определённое количество места в памяти.
