Лабораторная работа 3.

Стеки и очереди.

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

Исходные теоретические сведения

Стеки и очереди - это динамические структуры данных с ограниченным видом операций включением новых и выключением старых переменных.

Стек представляет собой последовательность элементов с одной точкой доступа, называемой вершиной стека. Все элементы последовательности, кроме элемента, расположенного в вершине стека, недоступны. Новый элемент добавляется только в вершину стека, сдвигая остальные элементы последовательности. Исключить можно только элемент из вершины стека. Остальные элементы при этом сдвигаются в сторону вершины. Таким образом стек работает по принципу «последним пришел - первым ушел», и часто называется структурой LIFO (Last In - First Out).

В алгоритмах операцию добавления элемента в стек записывают в виде S^X (элемент X поместить в вершину стека S); операцию исключения в виде X^S (исключить элемент X из вершины стека S и присвоить его значение переменной X). В литературе эти операции традиционно называются PUSH (добавление) и POP (исключение).

Очередь представляет собой последовательность элементов с двумя точками доступа: начало (голова) и конец (хвост). Новый элемент добавляется всегда в конец очереди, исключается всегда элемент, расположенный в начале очереди. Таким образом очередь работает по принципу «первым зашел - первым ушел» и часто называется структурой FIFO (First In - First Out).

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

Стеки и очереди удобно реализовывать с помощью указателей, т.к. указатели имеют весьма гибкую структуру.

Описание типа стек:

^typ^e

ct=^Acelltype;

celltype=record

element:byte;

next:ct;

end;

stack=record

top:ct;

fin:ct;

end;

где top - указатель на вершину стека.

Описание типа очередь: type

ct=^Acelltype;

celltype=record

element:byte;

next:ct;

end;

queue=record

front:ct;

rear:ct;

end;

где front - указатель на начало очереди, rear - указатель на конец очереди.

Варианты заданий.

Вариант	Задание
1	Разработайте реализации для очередей, состоящих из действительных чисел, с использованием массивов и указателей.
2	Реализовать двухстороннюю очередь, если элементами являются действительных чисел.
3	Разработайте реализации для стека, состоящих из действительных чисел, с использованием массивов и указателей.
4	Напишите процедуру поиска элементов в позициях p для стека.
5	Напишите процедуру поиска элементов в позициях p для очереди.
6	Напишите процедуру сортировки элементов для очереди.
7	Напишите процедуру обмена элементами в позициях p и NEXT(p) для стека.
8	Напишите процедуру обмена элементами в позициях p и NEXT(p) для очереди.
9	Напишите программу сложения и умножения двух стеков.
10	Напишите программу сложения и умножения двух очередей.

Пример выполнения.

Задание: написать программы, реализующие операции над стеками и очередями, с помощью указателей:

1. функция STACKTOP(Q), которая определяет значение элемента в вершине стека Q без его удаления (не определена для пустого стека);

2. процедура INSERT(S,X), которая помещает элемент X в конец очереди S;

3. функция REMOVE(S), которая удаляет элемент из начала очереди S, т.е. операция X:=REMOVE (S) удаляет элемент из начала очереди S и присваивает его значение переменной X (не определена для пустой очереди).

Блок-схема алгоритма

начало

Ввод n

Г><С i:=1,n

Печат ь x

конец

Реализация функции STACKTOP( Q ): function stacktop(var s:stack):byte; begin

stacktop:=s.top^A.next^A.element;

end;

Реализация процедуры INSERT( S.X ): procedure insert(var q:queue;x:byte); begin

new(q.rear^A.next);

q.rear:=q.rear^A.next;

q.rear^A.element:=x;

q.rear^A.next:=nil;

end;

Реализация функции REMOVE( S): function remove(var q:queue):byte; begin

remove: =q.frontA .nextA .element; delstart(q); end;

Текст программы:

Очередь:

uses

crt;

const

n=10;

type

ct=^Acelltype;

celltype=record

element:byte;

next:ct;

end;

queue=record

front:ct;

rear:ct;

end;

var

s:queue;

x:byte;

procedure insert(var q:queue;x:byte); begin

new(q.rear^A.next);

q.rear:=q.rear^A.next;

q.rear^A.element:=x;

q.rear^A.next:=nil;

end;

procedure create(var q:queue); var

i,x:byte; begin

new(q.front); q.frontA.next:=nil; q.rear:=q.front; for i:=1 to n do begin

x:=round(random*100);

insert(q,x);

end;

writeln('QUEUE IS CREATE.'); end;

procedure delstart(var q:queue); begin

q.front:=q.frontA .next; end;

function remove(var q:queue):byte; begin

remove: =q.front^A .next^A .element; delstart(q); end;

procedure printqueue(var q:queue); var temp:queue; begin

writeln('QUEUE:');

temp:=q;

while temp.front^A.next<>nil do begin

write(temp.front^A.next^A.element,' '); temp.front:=temp.front^A.next; end; writeln; end;

procedure delqueue(var q:queue); begin

while q.frontA.next<>nil do delstart(q); writeln('QUEUE IS DELETE.'); end;

begin

clrscr;

randomize;

create(s);

printqueue(s);

x:=remove(s);

writeln('X:=',x);

printqueue(s);

delqueue(s);

readkey;

end.

Стек:

uses

crt;

const

n=10;

type

ct=Acelltype;

celltype=record

element:byte;

next:ct;

end;

stack=record

top:ct;

fin:ct;

end;

var

q:stack;

x:byte;

procedure push(var s:stack); begin

new(s.fin^A.next);

s.fin:=s.fin^A.next;

s.fin^A.element:=round(random*100);

s.fin^A.next:=nil;

end;

procedure create(var s:stack); var i:byte; begin

new(s.top);

s.top^A.next:=nil;

s.fin:=s.top;

for i:=1 to n do push(s); writeln('STACK IS CREATE.'); end;

procedure pop(var s:stack); var temp:stack; begin temp:=s;

while temp.topA.nextos.fin do temp.top:=temp.topA.next; s.fin:=temp.top; end;

function stacktop(var s:stack):byte; begin

stacktop:=s.topA.nextA.element;

end;

procedure printstack(var s:stack); var temp:stack; begin

writeln('STACK:');

temp:=s;

while temp.topA.nextonil do begin

write(temp.topA .nextA .element,' '); temp.top: =temp.topA.next; end; writeln; end;

procedure delstack(var s:stack); begin

s.topA.next:=nil; writeln('STACK IS DELETE.'); end;

begin

clrscr;

randomize;

create(q);

printstack(q);

x:=stacktop(q);

writeln('TOP:=',x);

delstack(q);

readkey;

end.

Результаты расчетов.

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