Код
#статьи

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

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

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

Сергей Голицын


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) — нам нужно заранее определённое количество места в памяти.

Нейросети для работы и творчества!
Хотите разобраться, как их использовать? Смотрите конференцию: четыре топ-эксперта, кейсы и практика. Онлайн, бесплатно. Кликните для подробностей.
Смотреть программу
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована