Алгоритмический язык Паскаль (стр. 19 из 31)
Для стеков используют два представления - ПОСЛЕДОВАТЕЛЬНОЕ и СВЯЗАННОЕ.
ПОСЛЕДОВАТЕЛЬНОЕ представление требует резервирования блока памяти - одномерного массива А[1], А[2],..., А[N] - по тому же принципу, что и очередь. Величина N должна быть такой, чтобы стек мог расти до своего максимального размера без переполнения блока. Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение I = 0 перед чтением из стека служит признаком его пустоты, а значение I = N перед записью в стек - признаком переполненности стека.
Представление стека в памяти:
| I - вершина | |||||
  | |||||
| . | . | . | |||
| D[K] | D[K-1] | D[3] | D[2] | D[1] | |
| указатель | |||||
| вершины стека | |||||
Связанное представление стека осуществляется путем введения указателя на местоположение следующего (предыдущего) элемента. Указатель на первый элемент стека должен находиться в указателе вершины. Включение и исключение элементов осуществляется, как показано на рисунке:
| СТЕК | D0 | СТЕК | |
  | D1 | D0 | |
   | новый элемент | ||
| D2 | D1 | ||
 | |||
| | |||
| | … | D2 | |
| | |||
| | |||
| | … | ||
| СТЕК | СТЕК | Свободное | |
| | пространство | ||
 | D1 | D1 | |
 | |||
| D2 | D2 | ||
 | |||
| | |||
| | … | … | |
Стек удобен для вычисления значения арифметического выражения, представленного в обратной польской (бесскобочной) записи. Такие вычисления с помощью стека реализуются, например, во многих калькуляторах. Стек используют в обращениях к процедурам, а также при реализации рекурсий в Паскале.
Линейный массив переменного размера, в котором включение и исключение элементов может выполняться в произвольных точках, обычно называется списком (или связанным списком). Доступ к элементам списка, как правило, ограничивается первым и следующим (или иногда предыдущим) по отношению к данному. Следовательно, возможен доступ к любому элементу списка, но только путем "прокручивания" списка, начиная с первого элемента.
Поскольку вероятны произвольные включения и исключения элементов, то для списков используется только связанное представление, главным образом, две его формы:
1. Представление с одной связью: каждый элемент списка соединен со следующим; имеется указатель на первый элемент, который обычно находится в отдельной ячейке, называемой головой списка. Это представление идентично представлению очереди, рассмотренное нами ранее:
| Список | С1 | С2 | Сn | |||
 | … | Nil | ||||
| 0-звено | 1-звено | 2-звено | n-звено | |||
| (голова) | ||||||
2. Представление с двумя связями: каждый элемент списка соединен с последующим и предыдущим; в голове списка имеются указатели и на первый, и на последний элементы. Такие двусвязные списки принято называть деками.
СХЕМА ПРЕДСТАВЛЕНИЯ ДВУХСВЯЗНОГО СПИСКА
 | ||
 | Список | С1 |
  | Ук. 1-го эл-та | |
 | Ук. 2-го эл-та | |
 | ||
| С2 | ||
| | ||
 | ||
| | ||
| | … | |
| | ||
 | … | |
| Сn-1 | ||
| | ||
| | ||
| | ||
| Cn | ||
 | ||
 | ||
| |
Связанное представление с одной связью имеет тот недостаток, что список можно просматривать только в одном направлении. Для движения в обе стороны нужны двусвязные списки (деки), однако они занимают много памяти (содержат две ссылки), поэтому их надо использовать, если движение в обе стороны очень необходимо.