Рубрики

Как создать объединяемый стек?

Разработайте стек со следующими операциями.

а) push (Stack s, x): добавляет элемент x в стек s
b) pop (Stack s): удаляет верхний элемент из стека s
c) объединить (стек s1, стек s2): объединить содержимое s2 в s1.

Сложность времени всех вышеперечисленных операций должна быть O (1).

Если мы используем реализацию массива стека, то слияние невозможно сделать за O (1), так как мы должны сделать следующие шаги.
а) Удалить старые массивы
б) Создайте новый массив для s1 с размером, равным размеру старого массива для s1 плюс размер s2.
c) Скопировать старое содержимое s1 и s2 в новый массив для s1
Вышеуказанные операции занимают O (n) время.

Мы можем использовать связанный список с двумя указателями, один указатель на первый узел (также используется как верхний, когда элементы добавляются и удаляются из начала). Другой указатель необходим для последнего узла, чтобы мы могли быстро связать связанный список s2 в конце s1. Ниже приведены все операции.
а) push (): добавляет новый элемент в начало связанного списка, используя первый указатель.
б) pop (): удаляет элемент из начала, используя первый указатель.
c) merge (): связывает первый стек второго указателя со следующим последним указателем первого списка.

Можем ли мы сделать это, если нам не разрешено использовать дополнительный указатель?
Мы можем сделать это с помощью кругового связанного списка . Идея состоит в том, чтобы отслеживать последний узел в связанном списке. Следующий из последнего узла указывает на вершину стека.
а) push (): добавляет новый элемент как следующий из последнего узла.
б) pop (): удаляет следующий из последнего узла.
c) merge (): связывает верх (следующий за последним) второго списка с верхом (следующим за последним) первого списка. И делает последний из второго списка как последний из всего списка.

Эта статья предоставлена Рахул Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как создать объединяемый стек?

0.00 (0%) 0 votes