Проверьте, равны ли два стека или нет без изменения

Учитывая два стека S1 и S2 , задача состоит в том, чтобы проверить, равны ли оба стека или нет в том же порядке, не теряя исходные стеки. Если оба стека равны, то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: S1 = {3, 4, 2, 1}, S2 = {3, 4, 2, 1}
Output: Yes

Input: S1 = {3, 4, 6}, S2 = {7, 2, 1}
Output: No

Подход: данная проблема может быть решена путем перемещения некоторого количества элементов между заданными двумя стеками для проверки каждого соответствующего элемента в двух стеках. Выполните следующие шаги, чтобы решить проблему:

• Сохраните размер стека S1 и S2 в переменных N и M соответственно.
• Если N не равно M , то выведите « No » и вернитесь.
• Переберите диапазон [1, N] и выполните следующие операции:
  • Вставьте верхние (N – i) элементы стека S1 в стек S2 .
  • Теперь сохраните верхний элемент S1stack в переменной, скажем, val .
  • Теперь поместите верхние 2 * (N – i) элементов из стека S2 в стек S1 .
  • Если значение val не равно верхнему значению стека S2, то выведите « No » и вернитесь.
  • В противном случае восстановите стеки, переместив верхние (N – i) элементы из стека S1 в стек S2.
• После выполнения вышеуказанных шагов, если ни один из вышеперечисленных случаев не удовлетворяет, то выведите « Да ».

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1), так как дополнительное пространство не занято.