Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>21 ноя 2022</li>

3 <li>0</li>

4 </ul><h2>Задача: создать очередь с помощью стеков</h2>

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

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

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

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

9 <ul><li>push - добавляет элемент в конец очереди;</li>

10 <li>pop - убирает элемент из начала и возвращает его как результат;</li>

11 <li>peek - возвращает элемент из начала очереди, но не убирает его;</li>

12 <li>empty - возвращаетtrue,если очередь пустая, иначе -false.</li>

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

14 Ввод: ["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Решить эту задачу самостоятельно и на разных языках программирования можно на <a>LeetCode</a>. Наше решение взято из телеграм-канала Сергея<a>Cracking code interview</a>.

15 Решение

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

17 static class MyQueue { Stack<Integer> current; Stack<Integer> tmp; public MyQueue() { current = new Stack<>(); tmp = new Stack<>(); }Теперь давайте реализуем методpush:

18 public void push(int x) { current.push(x); }Всё просто - добавляем новый элемент в стекcurrent.

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

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

21 public int pop() { if (!tmp.isEmpty()) { return tmp.pop(); } while (!current.isEmpty()) { tmp.push(current.pop()); } return tmp.pop();Чтобы продемонстрировать правильность работы этой фукнции, давайте посмотрим на пример:

22 <ul><li>push 1 → 1;</li>

23 <li>push 2 → 2, 1;</li>

24 <li>push 3 → 3, 2, 1;</li>

25 <li>pop → перемещаем всё в tmp:cur: 2, 1;tmp: 3 →cur: 1;tmp: 2, 3 →cur: ;tmp: 1, 2, 3;</li>

26 <li>теперь все элементы в tmpстоят в правильном порядке.</li>

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

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

29 public int peek() { if (!tmp.isEmpty()) { return tmp.peek(); } while (!current.isEmpty()) { tmp.push(current.pop()); } return tmp.peek();И последнее - методempty:

30 public boolean empty() { if (!tmp.isEmpty()) { return tmp.isEmpty(); } return current.isEmpty(); }Здесь нам важно не забыть проверить вторую очередь.

31 Результаты

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

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

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