Где должна быть вершина стека в реализации стека в связанном списке?

Question

Вот как может выглядеть связанный список, реализующий стек с 3 элементами:

list
 |
 v
--------   --------   ---------
| C | -+-->| B | -+-->| A | 0 |
--------   --------   ---------

Где мы должны рассматривать вершину стека, начало или конец списка и почему?

Заранее спасибо.

Answer 1

Самым быстрым элементом для доступа в связанном списке обычно является заголовок (хотя некоторые реализации также сохраняют ссылку на хвостовой элемент).Поскольку стеку требуется только доступ к верхнему элементу, это должен быть элемент заголовка связанного списка.Это позволит избежать необходимости перебирать весь список для каждой операции.

Answer 2

list.head будет вершиной стека. Элементы будут добавлены в голову как

Вставка (L, х)

1. x.next = head.next
2. head = x

Аналогичным образом удаление будет выполняться в голове.

Удалить (L)

1. x=head
2. head = head.next 
3. Free x

Таким образом, вставка и удаление будут выполняться в порядке LIFO, который является стеком.