Представление стека в памяти:

									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

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

Если последнее звено списка имеет ссылку на первое звено как на следующее, а первое звено ссылается на последнее как на предыдущее, то такой список оказывается замкнутым по кольцу и называется кольцевым.

Часто списки строят по иерархическому принципу. В этом случае его записи могут иметь внутреннюю структуру, организованную также по принципу списка (основной список оказывается состоящим из записей-подсписков). В этом случае приходят к многомерным массивам переменного размера.

Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.