Один из наиболее частых вопросов об очередях и стеках на собеседованиях — как создать одно из другого. В этом блоге мы будем использовать стек, созданный классом, и научимся создавать очередь из того, что нам дано.

Напомню, что класс Stack инициализируется пустым массивом и включает три метода. Метод push() позволит вам добавить элемент в стек, а метод pop() позволит вам удалить элемент из стека. Метод peek() покажет вам последний элемент в списке, который также является тем же элементом, который был бы удален при вызове метода pop(). Обратите внимание, что методы push() и pop() изменяют массив, а метод peek() показывает последний элемент массива, но не изменяет его.

Самая большая разница между очередью и стеком заключается в элементе, который необходимо удалить. Чтобы создать очередь, нам нужно удалить первый элемент в списке, чтобы следовать структуре FIFO (First In First Out). Для этого мы начнем с создания конструктора, который инициализирует два новых стека.

Мы создаем два стека, потому что нам нужно, чтобы один стек содержал все элементы в массиве, а второй стек будет использоваться в качестве временного заполнителя для перемещения элементов вперед и назад.

Подобно классу Stack, класс Queue также будет иметь те же три метода добавления элемента, удаления элемента и просмотра первого элемента в списке.

Метод добавления в очередь

Чтобы создать метод add(), мы воспользуемся методом push() из класса Stack и добавим элемент в первый стек.

Метод удаления очереди

Чтобы создать метод remove(), нам нужно творчески использовать методы push() и pop() из класса Stack. Идея состоит в том, чтобы удалить последний элемент первого стека и поместить его в массив второго стека, пока первый стек не станет пустым. Используя метод peek() внутри цикла while, он будет продолжать проверять, не находится ли что-нибудь внутри первого стека. Как только первый стек опустеет, мы перейдем к следующему шагу.

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

После удаления элемента из очереди нам нужно не забыть поместить остальные элементы обратно в первый стек, следуя тому же методу, что и раньше.

Вот полный метод remove() для очереди:

Метод просмотра очереди

Последний метод класса Queue — это метод peek(). Этот метод помогает нам показать первый элемент в массиве, который также является элементом, который будет удален при вызове метода remove().

Метод peek() будет выглядеть точно так же, как наш метод remove(), но большая разница в том, что мы не удаляем последний элемент из второго стека. Вместо этого мы сохраняем последний элемент внутри переменной и возвращаем его после возвращения первого стека в исходный порядок.

Последние мысли

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

Теперь, когда вы мастер стеков и очередей, вы можете сказать всем своим друзьям:

Спасибо за чтение!