Программа для вставки элемента внизу стека

Учитывая стек S и целое число N , задача состоит в том, чтобы вставить N в конец стека.

Примеры:

Input: N = 7
S = 1 <- (Top)
      2
     3
     4
     5
Output: 1 2 3 4 5 7

Input: N = 17
S = 1 <- (Top)
     12
     34
     47
     15
Output: 1 12 34 47 15 17

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

1. Инициализируйте стек, скажем, temp .
2. Продолжайте извлекать элементы из заданного стека S и помещать извлеченные элементы во временные, пока стек S не станет пустым.
3. Поместите N в стек S.
4. Теперь продолжайте извлекать из временного стека и помещать извлеченные элементы в стек S , пока временный стек не станет пустым.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N)

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

1. Определите функцию рекурсии, которая принимает стек S и целое число в качестве параметров и возвращает стек.
2. Базовый случай, который следует учитывать, - это если стек пуст. Для этого сценария поместите N в стек и верните его.
3. В противном случае удалите верхний элемент Sand, сохраните его в переменной, скажем, X .
4. Рекурсия снова, используя новый стек
5. Вставьте X в S.

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

Временная сложность: O(N), где N — общее количество элементов в стеке.
Вспомогательное пространство: O(N)