Все
Истории
Дизайн
Код
Геймдев
Бизнес
Маркетинг
Управление
Кино
Музыка
Проектная фотография
Развитие
Здоровье
Деньги
Образование
EdTech
Корп. обучение
Блог Skillbox
Глоссарий
Спецпроекты
Профориентация
Задача: создать стек с помощью очередей
Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня пытаемся понять, как сделать стек из нескольких очередей.
Сергей Голицын
Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.
Условие. Реализовать стек last-in-first-out (LIFO), используя максимум две очереди. Он должен поддерживать все стандартные функции обычного стека — push, pop, top и empty:
- push — добавляет элемент на вершину стека;
- pop — убирает элемент с вершины и возвращает его как результат;
- top — возвращает элемент с вершины стека, но не убирает его;
- empty — возвращает true, если стек пустой, иначе — false.
Примечание: вы должны использовать только стандартные операции с очередями — push, peek/pop, size и empty. А если ваш язык не поддерживает очереди, то их можно реализовать через обычный список или двухстороннюю очередь, но при этом использовать только функции, приведённые выше.
Ввод и вывод. Пример
Ввод:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Вывод:
[null, null, null, 2, 2, false]
Пояснение:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // вернёт 2
myStack.pop(); // вернёт 2
myStack.empty(); // вернёт False
Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.
Решение
Первый вариант. Мы решим эту задачу двумя способами. Первый будет использовать две очереди, а второй — одну. Начнём с первого.
В этом варианте нам понадобится дополнительная память. Сначала создадим класс MyStack с двумя очередями current и tmp:
static class MyStack {
private Queue<Integer> current;
private Queue<Integer> tmp;
public MyStack() {
current = new ArrayDeque<>();
tmp = new ArrayDeque<>();
} Теперь давайте реализуем метод push:
public void push(int x) {
current.add(x);
} Всё просто — мы добавляем новый элемент в очередь current. Но главный трюк будет с методом pop. Чтобы он заработал, мы должны при его вызове положить все элементы, кроме последнего, в очередь tmp. А единственный элемент из очереди current мы вернём как результат.
Давайте напишем его:
public int pop() {
if (current.isEmpty()){
return -1;
}
int size = current.size();
for (int i = 0; i < size - 1; i ++){
tmp.add(current.poll());
}
int ret = current.poll();
current = tmp;
return ret;
}Метод top будет похож на метод pop:
public int top() {
if (current.isEmpty()){
return -1;
}
int size = current.size();
for (int i = 0; i < size - 1; i ++){
tmp.add(current.poll());
}
int ret = current.peek();
tmp.add(current.poll());
current = tmp;
return ret;
}А для метода empty нам просто нужно проверить, пуста ли очередь current:
public boolean empty() {
return current.isEmpty();
}Второй вариант. В этом случае нам не понадобится дополнительная память. Мы ограничимся всего одной очередью.
Вот так выглядит наш класс:
static class MyStack2 {
private Queue<Integer> current;
public MyStack2() {
current = new ArrayDeque<>();
}
}Чтобы реализовать метод push, нам нужно добавлять новый элемент в очередь и после этого перемещать все прочие элементы в конец этой же очереди.
Например, если у нас есть очередь [2, 1] и мы добавляем элемент 3, то получаем очередь [3, 2, 1]. Но теперь мы берём последовательно все элементы, кроме 3, и добавляем их в конец: [3, 2, 1] → [1, 3, 2] → [2, 1, 3].
Получится такая функция:
public void push(int x) {
current.add(x);
int size = current.size();
for (int i = 0; i < size-1; i ++){
current.add(current.poll());
}
}А для методов pop, top и empty мы будем использовать встроенные функции:
public int pop() {
return current.poll();
}
public int top() {
return current.peek();
}
public boolean empty() {
return current.isEmpty();
}Результаты
Временная сложность. Вариант с двумя очередями: push — O(1), pop — O(N). А вариант с одной очередью: push — O(N), pop — O(1).
Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.
