next: pnode; { Ссылка на следующий элемент. }
end;
Сама очередь задается совокупностью указателя на первый элемент и переменной, хранящей текущее количество элементов.
type queue = record
first: pnode; { Указатель на первый элемент. }
count: integer; { Количество элементов. }
end;
Инициализация очереди осуществляется путем присваивания пустой ссылки указателю на первый элемент очереди и обнуления переменной, хранящей количество элементов.
{ Операция инициализации очереди. }
{ Входные параметры: }
{ q - очередь. }
procedure init(var q: queue);
begin
q.first := nil;
q.count := 0;
end;
Операция добавления нового элемента зависит от того, пуста ли очередь. Если в очереди нет ни одного элемента, то добавление произойдет в начало. В противном случае циклом необходимо дойти до конца очереди, новый элемент будет последним. Здесь сложность операции, в отличие от реализации на массиве, составляет O(n), поскольку необходимо осуществлять поиск последнего элемента.
{ Операция добавления нового элемента. }
{ Входные параметры: }
{ q - очередь; }
{ item - новый элемент. }
procedure add(var q: queue; item: integer);
var
i: pnode;
begin
{ Если ссылка на первый элемент пуста, значит }
{ в списке нет ни одного элемента. Добавляемый }
{ элемент будет первым. }
if (q.first = nil) then
begin
new(q.first);
q.first^.data := item;
q.first^.next := nil;
end
{ В противном случае доходим до последнего элемента }
{ списка. Добавляем новый элемент в конец. }
else
begin
i := q.first;
while (i^.next <> nil) do
i := i^.next;
new(i^.next);
i^.next^.next := nil;
i^.next^.data := item;
end;
{ После добавления увеличиваем количество элементов }
{ в списке на единицу. }
inc(q.count);
end;
Операция удаления элемента также зависит от общего числа элементов. Если очередь пуста, ничего удалять не нужно. Сложность операции O(1), поскольку мы всегда храним указатель на первый элемент.
{ Операция удаления элемента. }
{ Входные параметры: }
{ q - очередь. }
procedure remove(var q: queue);
var
i: pnode;
begin
{ Если в очереди есть хотя бы один элемент, }
{ удаляем первый. На его место ставим второй элемент. }
if (q.count > 0) then
begin
i := q.first^.next;
dispose(q.first);
q.first := i;
{ Уменьшаем количество элементов на 1. }
dec(q.count);
end;
end;
Для получения первого элемента очереди возвращаем его полезную информацию. Если очередь пуста, возвращаем 0. Сложность операции O(1).
{ Операция получения первого элемента очереди. }
{ Входные параметры: }
{ q - очередь. }
function get_first(q: queue): integer;
begin
{ Если в очереди есть хотя бы один элемент, }
{ возвращаем первый. }
if (q.count > 0) then
get_first := q.first^.data
else
{ В противном случае возвращаем 0. }
get_first := 0;
end;
Для получения последнего элемента очереди, необходимо циклом осуществить переход к нему и вернуть его содержимое. Если очередь пуста, возвращаем 0. Сложность операции O(n).
{ Операция получения последнего элемента очереди. }
{ Входные параметры: }
{ q - очередь. }
function get_last(q: queue): integer;
var
i: pnode;
begin
{ Если в очереди есть хотя бы один элемент, переходим }
{ к последнему элементу и возвращаем значение, }
{ в нем. }
if (q.count > 0) then
begin
i := q.first;
while (i^.next <> nil) do
i := i^.next;
get_last := i^.data;
end
{ В противном случае возвращаем 0. }
else
get_last := 0;
end;
4. Стеки. Реализации на базе массива и списка
4.1. Понятие стека
| выход |
| вход |
| 2 |
| 1 |
| 3 |
Рис. 6. Стек.
Для добавления и удаления элементов необходимо получить доступ к вершине стека. Доступ к другим элементам невозможен логически. Принцип доступа, реализуемый стеком называется LIFO (Last In, First Out), что по русски означает «Первым выйдет тот, кто пришел последним».
Стек предоставляет три основные операции:
- добавление нового элемента;
- удаление элемента из вершины стека;
- получение элемента, находящегося в вершине (без удаления).
4.2. Реализация стека на базе массива
Реализация стека на основе массива делает ограничение на максимальное количество элементов, одновременно хранящихся в стеке. В качестве примера реализуем стек, хранящий целочисленные элементы. Стек представляется в виде структуры, содержащую массив элементов и переменную, хранящую количество элементов в стеке:
type stack = record
buf: array [1..max_size] { Массив элементов. }
of integer;
count: integer; { Количество элементов. }
end;
Инициализация стека осуществляется путем присваивания переменной count значения 0:
{ Операция инициализации стека. }
{ Входные параметры: }
{ s - стек; }
procedure init(var s: stack);
begin
s.count := 0;
end;
При добавлении элемента в стек следует следить за текущим количеством элементов в стеке (оно должно быть больше максимального количества элементов). Сложность операции O(1):
{ Операция добавления нового элемента. }
{ Входные параметры: }
{ s - стек; }
{ item - новый элемент; }
procedure push(var s: stack; item: integer);
begin
{ Если текущее количество элементов меньше }
{ максимального, выполняем добавление элемента. }
if (s.count < max_size) then
begin
s.buf[s.count + 1] := item;
{ Увеличиваем число элементов на 1. }
inc(s.count);
end;
end;
При просмотре верхнего элемента стека отдельно обрабатывается случай, когда число элементов равно 0. В данном случае возвращается некое фиксированное значение или код ошибки. Если стек содержит хотябы один элемент, то возвращается верхушка стека. Сложность операции O(1):
{ Операция просмотра вершины стека. }
{ Входные параметры: }
{ s - стек; }
function peek(s: stack): integer;
begin
{ Если нет ни одного элемента, возвращаем 0. }
if (s.count <= 0) then
peek := 0
{ В противном случае возвращаем элемент из вершины. }
else
peek := s.buf[1];
end;
Операция удаления элемента из стека производит выемку элемента из вершины с его возвратом. При этом, если стек пуст, возвращается код ошибки. Сложность операции O(n):
{ Операция удаления элемента из вершины стека. }
{ Входные параметры: }
{ s - стек; }
function pop(var s: stack): integer;
var
i: integer;
begin
{ Если в стеке нет элементов, возвращаем 0. }
if (s.count <= 0) then
pop := 0
else
begin
{ Удаляем элемент из вершины. Все остальные }
{ сдвигаем влево на одну позицию. }
pop := s.buf[1];
i := 1;
while (i < s.count) do
begin
s.buf[i] := s.buf[i + 1];
inc(i);
end;
{ Уменьшаем количество элементов на 1. }
dec(s.count);
end;
end;
4.3. Реализация стека на базе связного списка
Преимущество реализации на базе связного списка заключено в том, что ограничение на максимальное число элементов отсутствует. Для реализации необходимо описать элемент стека. Это структура, содержащая полезную информацию и ссылку на следующий элемент:
type pnode = ^node; { Тип: указатель на узел стека. }
node = record { Объявление узла стека. }
data: integer; { Полезная информация. }
next: pnode; { Ссылка на следующий элемент. }
end;
Сам стек является структурой, содержащей указатель на первый элемент и переменную, хранящую количество элементов в стеке:
type stack = record
first: pnode; { Указатель на первый элемент. }
count: integer; { Количество элементов. }
end;
Инициализация стека производится обнулением количества элементов в стеке и присваиванием пустой ссылки указателю на первый элемент:
{ Операция инициализации стека. }
{ Входные параметры: }
{ s - стек; }
procedure init(var s: stack);
begin
s.first := nil;
s.count := 0;
end;
Добавление элемента производится в начало стека. При этом ссылка на первый элемент должна указывать на новый элемент. Если стек пустой, то необходимо произвести инициализацию указателя на первый элемент. Сложнойсть операции O(1):
{ Операция добавления нового элемента. }
{ Входные параметры: }
{ s - стек; }
{ item - новый элемент; }
procedure push(var s: stack; item: integer);
var
i: pnode;
begin
{ Если ссылка на первый элемент пуста, значит }
{ в стеке нет ни одного элемента. Добавляемый }
{ элемент будет первым. }
if (s.first = nil) then
begin
new(s.first);
s.first^.data := item;
s.first^.next := nil;
end
{ В противном случае добавляем элемент в начало стека. }
else
begin
i := s.first;
new(s.first);
s.first^.data := item;
s.first^.next := i;
end;
{ После добавления увеличиваем количество элементов }
{ в стеке на единицу. }
inc(s.count);
end;
Операция просмотра первого элемента в стеке возвращает 0, если он пуст. В противном случае, возвращает элемент в вершине стека. Сложность операции O(1):
{ Операция просмотра вершины стека. }
{ Входные параметры: }
{ s - стек; }
function peek(s: stack): integer;
begin
{ Если нет ни одного элемента, возвращаем 0. }
if (s.count <= 0) then
peek := 0
{ В противном случае возвращаем элемент из вершины. }
else
peek := s.first^.data;
end;
Операция удаления элемента очищает память, занимаемую первым элементов стека и переставляет указатель на вершину. Функция возвращает данные, хранимые в удаленном элементе. Следует обрабатывать ситуации, когда стек пуст. В данном случае функция возвращает 0 в качестве кода ошибки. Сложность операции O(1):
{ Операция удаления элемента из вершины стека. }
{ Входные параметры: }
{ s - стек; }
function pop(var s: stack): integer;
var
i: pnode;
begin
{ Если в стеке нет элементов, возвращаем 0. }
if (s.count <= 0) then
pop := 0
else
begin
{ Удаляем элемент из вершины. Второй элемент }
{ становится на место первого. }
pop := s.first^.data;
i := s.first^.next;
dispose(s.first);
s.first := i;
{ Уменьшаем количество элементов на 1. }
dec(s.count);
end;
end;
5. Заключение
В данной главе мы рассмотрели понятие линейных динамических структур данных, в частности связанного списка, очереди и стека и их реализации. Кроме того, мы рассмотрели реализации основных операций, применяемых в работе с данными структурами. Понимание этих типов данных крайне важно в изучении теории программирования. Правильное применение структур данных определяет качество, производительность и надежность разрабатываемой программы.
6. Литература
6.1. Использованные источники информации
- Фаронов В. В. Turbo Pascal 7.0. Учебный курс – КноРус, 2009. – 368 с.
- Вирт Н. Алгоритмы и структуры данных. – Невский Диалект, 2008. – 352 с.
- Статья Википедии, посвященная динамической памяти.
6.2. Информационные ресурсы сети Интернет
- Статья Википедии, посвященная структурам данных.
- Курс «Структуры данных и модели вычислений» в интернете информационных технологий.