Объединение двух отсортированных стеки

Question

Мой учитель дал мне следующее упражнение:

«Учитывая две отсортированные стеки, stack1 и stack2, разработать алгоритм для создания новый отсортированный стек, stack3, сливаться между stack1 и stack2 "

У меня возникли проблемы с поиском самого простого способа решить это упражнение, может ли кто-нибудь порекомендовать мне простой способ? Я подумал, что, возможно, я мог бы хранить как stack1, так и stack2 в какой-то другой структуре (возможно, массив?), А затем продолжить сортировку, но это выглядит долго, интересно, есть ли другой простой способ.

P.S.: Я могу использовать только push и pop, чтобы вставить/извлечь элемент из стеков.

Answer 1

Следует учитывать, что стеки уже отсортированы. Как вы сделаете это как человек?

Я думаю, что вы могли бы сделать что-то вроде следующего:

1. взгляд на верхний элемент в каждом стеке и сравнить эти два элемента.

2. зависимости от того, больше (или меньше, в зависимости от того, как они сортируются) будут добавлены в новый стек

3. повтора.

Возможно, попробуйте интерпретировать этот человеческий алгоритм как psuedocode и попытаться реализовать его, и вы можете получить что-то, что работает. Надеюсь, это поможет вам в правильном направлении!