3.2. Реализация очереди на базе массива

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

Сперва необходимо задать максимальное количество элементов. Пусть оно равно одной тысяче:

const max_elem_count = 1000;

Сама очередь представляет собой структуру, содержащую массив элементов и переменную, хранящую их текущее количество:

type queue = record

buf: array [1..max_elem_count]

of integer; { Массив элементов. }

count: integer; { Количество элементов. }

end;

Инициализация очереди осуществляется путем обнуления переменной, хранящей количество элементов. Обнулять массив нет необходимости, поскольку он будет затираться входящими элементами:

{ Операция инициализации очереди. }

{ Входные параметры: }

{ q - очередь; }

procedure init(var q: queue);

begin

q.count := 0;

end;

Операция добавления элемента записывает новое значение в конец массива. При этом следует учесть, если текущее количество элементов достигло максимума, ничего добавлять не нужно. Сложность операции O(1).

{ Операция добавления нового элемента. }

{ Входные параметры: }

{ q - очередь; }

{ item - новый элемент. }

procedure add(var q: queue; item: integer);

begin

{ Если текущее количество элементов меньше }

{ максимального, то записываем новый элемент в конец. }

if (q.count < max_elem_count) then

begin

q.buf[q.count + 1] := item;

{ Увеличиваем количество элементов на 1. }

inc(q.count);

end

end;

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

{ Операция удаления элемента. }

{ Входные параметры: }

{ q - очередь. }

procedure remove(var q: queue);

var

i: integer;

begin

{ Если количество елементов не 0, то удаляем. }

if (q.count > 0) then

begin

{ Выполняем сдвиг всех остальных элементов. }

i := 1;

while (i < q.count) do

begin

q.buf[i] := q.buf[i + 1];

inc(i);

end;

{ Уменьшаем количество элементов на 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.buf[1]

{ В противном случае возвращаем 0. }

else

get_first := 0;

end;

Операция получения элемента, стоящего в конце очереди, выполняет возврат элемента массива с индексом, равным количеству элементов в очереди. Если в очереди нет ни одного элемента, метод возвратит 0. Сложность операции O(1).

{ Операция получения последнего элемента очереди. }

{ Входные параметры: }

{ q - очередь. }

function get_last(q: queue): integer;

begin

{ Если очередь содержит хотя бы один элемент, }

{ возвращаем последний. }

if (q.count > 0) then

get_last := q.buf[q.count]

{ В противном случае возвращаем 0. }

else

get_last := 0;

end;

3.3. Реализация очереди на базе связного списка

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

type pnode = ^node; { Тип: указатель на элемент очереди. }

node = record { Объявление узла очереди. }

data: integer; { Полезная информация. }

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

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

Рис. 6. Стек.

Для добавления и удаления элементов необходимо получить доступ к вершине стека. Доступ к другим элементам невозможен логически. Принцип доступа, реализуемый стеком называется LIFO (Last In, First Out), что по русски означает «Первым выйдет тот, кто пришел последним».

Стек предоставляет три основные операции:

добавление нового элемента;

удаление элемента из вершины стека;

получение элемента, находящегося в вершине (без удаления).