Стеки и очереди в Паскале

Всё нижеописанное возможно имеет неточности и несоответствия. Пишу, так как себе представляю эту тему.

Итак начнем…

Стек представляет собой последовательную область данных, добавление в которую происходит по типу «Первый пришел, последний ушел».

Стек можно представить как стопку бумаги на столе. Мы можем забирать и добавлять листы бумаги только сверху.

Грубо говоря, по определенному адресу в памяти мы заносим данные и адрес в памяти следующей порции данных. Последняя порция данных в стеке уже никуда не ссылается.

Теперь попробуем все это реализовать в коде. Напомню что писать мы будем на Паскале. Код тестировался в среде Delphi.

Наша программа будет уметь не только добавлять и удалять данные из стека, но и удалять данные в любом месте стека.

Program Stek;

{$APPTYPE CONSOLE}

uses
SysUtils;

Type Ukaz = ^Stack;
Stack = record
Inf: integer;
Next: ukaz
End;
var Top, Kon, newel, Next, Prev: ukaz; value, max, i: integer;

{Добавление новых элементов}
Procedure Push;
Begin
New (newel);
Newel^.next := Top;
Newel^.inf := value;
Top := newel;
End;

{Удаление элемента из стека}
Procedure Pop;
Begin
Top:= Top^.next;
End;

Procedure writ; {Печать элементов стека}
Begin
Kon := Top;
While Kon <> nil do
Begin
Writeln(Kon^.inf);
Kon := Kon^.next;
End;
End;

Begin

write(‘Vsego elementov steka: ‘);
readln(max);//Вводим общее количество элементов стека
for i := 1 to max do begin//вводим каждое значение
write(‘Vvedite znachenie: ‘);
readln(value);
Push;
end;

write(‘Udalit: ‘);//вводим число которое надо удалить из стека
readln(value);
Next := Top;
While Next <> nil do//ищем это число в стеке
Begin
if Next^.inf = value then begin
if Prev = nil then
Top := Top^.next
else
Prev^.next := Next^.next;
break;
end;
Prev := Next;
Next := Next^.next;
End;

writ;
End.

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

В коде нет ничего сложного, поэтому я думаю поломав немного голову вы всё поймете.

А теперь поговорим о очередях.

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

Итак, напишем программу умеющую добавлять и удалять из очереди, а также менять местами данные в двух указанных местах.

Program Ochered;

{$APPTYPE CONSOLE}

uses
SysUtils;

Type
Ukaz = ^Stack;
Stack = record
Inf: integer;
Next: ukaz
End;
var Pp, Kon, newel, Right, Left: ukaz; num, value, max, i, Pervoe, Vtoroe: integer;

Procedure Sozd; {Организация очереди}
Begin
New(Kon);
Kon^.next := Left;
Kon^.inf := value;
Right := Kon;
Left := Kon;

End;

Procedure Dob; {Добавление новых элементов в уже существующую очередь. Добавление происходит справа}
Begin
New (newel);
Right^.Next := Newel;
Newel^.next := nil;
Newel^.inf := value;
Right := newel;

End;
Procedure Udal; {Удаление элемента из очереди, уда-ление происходит слева}
Begin
Left:= Left^.next;
End;
Procedure writ; {Печать элементов очереди}
Begin
Pp := Left;
While Pp <> nil do
Begin
Writeln(Pp^.inf);
Pp := Pp^.next;
End;
End;
Begin

write(‘Vsego elementov ocheredi: ‘);
readln(max);//Вводим общее количество элементов очереди
write(‘Vvedite znachenie: ‘);
readln(value);
sozd; //создаем очередь
for i := 1 to max-1 do begin//вводим каждое значение
if max=1 then break;
write(‘Vvedite znachenie: ‘);
readln(value);
dob; //добавляем новые элементы
end;

write(‘Pervoe: ‘); //вводим число которое надо поменять местами
readln(Pervoe);

write(‘Vtoroe: ‘); //вводим второе число которое надо поменять местами
readln(Vtoroe);

Pp := Left;
While Pp <> nil do
Begin
if Pp^.inf = Pervoe then begin
Pp^.inf := Vtoroe;
Pp := Pp^.next;
continue;
end;
if Pp^.inf = Vtoroe then begin
Pp^.inf := Pervoe;
Pp := Pp^.next;
continue;
end;
Pp := Pp^.next;
End;

writ;

End.

Напомню, что код тестировался в среде Delphi, отсюда и эта директива компиляции {$APPTYPE CONSOLE} и Uses SysUtils.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *