#stack #linked-list
#стек #связанный список
Вопрос:
Вот как может выглядеть связанный список, реализующий стек с 3 элементами:
list
|
v
-------- -------- ---------
| C | - -->| B | - -->| A | 0 |
-------- -------- ---------
Где мы должны считать вершину стека, начало или конец списка, и почему?
Заранее спасибо.
Ответ №1:
Самым быстрым элементом для доступа в связанном списке обычно является head (хотя некоторые реализации также сохраняют ссылку на элемент tail). Поскольку стеку требуется только доступ к верхнему элементу, это должен быть элемент head связанного списка. Это позволит избежать необходимости перебирать весь список для каждой операции.
Комментарии:
1. Я очень смущен, где здесь будет находиться вершина стека? Поскольку вершина стека указывает на ячейку памяти, где будет сохранен следующий элемент, мы не зарезервировали здесь ячейку памяти.
Ответ №2:
list.head будет вершиной стека. Элементы будут добавлены в head как
Вставить (L, x)
1. x.next = head.next 2. head = x
Аналогично удаление будет выполнено в head.
Удалить (L)
1. x= head 2. head = head.next 3. Освободите x
Таким образом, вставка и удаление будут выполняться в порядке LIFO, который является стеком.