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

[Vanya]

Привет всем. Подскажите пожалуйста, что такое очереди и стеки в Паскале. Если можно, то напишите пример как организовать эти динамические струтуры данных

[Naeel Maqsudov]

Это структуры, организованные на базе динамических списков.

Списки состоят из элементов типа Запись, содержащих поле Next типа Pointer с указателем (адресом) на следующий элемент. А также, если список двусвязный, то и поле Prev, с указателем на предыдущий.

Для добавления элемента выделяется память с помощью New(), затем заполняются поля с данными, поля Next/Prev а зетем корректируются поля Next у предыдущего элемента и Prev у следующего. После этого элемент оказывается включенным в список.

Стеки - это структуры (основанные на динамических списках или как-то иначе), для которых определены операции добавления элемента на вершину и снятия элемента с вершины или с основания. (Под снятием понимается извлечение и удаление). В зависимости от того с какой стороны снимаются элементы различают FILO-стеки (Их обычно называют просто стеками), когда элементы снимаются с вершины; и FIFO-стеки (Их обычно называют очередями).

FILO - First In Last Out - первым вошел, последним вышел
FIFO - Fist In Firs Out - первым вошел, первым вышел

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

[Vanya]

Naeel Maqsudov, Спасибо! Да, стеки нужны на базе динамических списков. А какие более эффектные решения?

[Naeel Maqsudov]

Более эффективным решением может быть массив с циклически "бегающими" по нему указателями или индексами. Сначала указатели указывают на нулевой элемент. При добавлении значения в очередь. Указатель на вершину увеличивается и в ячейку по этому указателю записывается это значение.

Неравенство указателей означает что очередь не пуста. Тогда для чтения элемента из очереди увеличиваем указатель на конец очереди и читаем значение по этому указателю.

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

Со стеками то же самое. Только проще - есть только один указатель на вершину стека который увеличивается при добавлении элементов, и уменьшается при снятии.

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

При работе с динамическими списками теоретически нет ограничений, но практически надо ловить эксепшн при вызове New() для выделения памяти.

[Naeel Maqsudov]

Итак, стеки FIFO и FILO в студию!
Пам-пам-пара-ра-па-па-пам-пам...

Код: Выделить всё

type
  TData = integer; {or any other type}

  PListItem = ^TListItem;
  TListItem = record
    AData: TData;
    Next: PListItem;
  end;

  PCommonList = ^TCommonList;
  TCommonList = object
    Top : PListItem;
    Bottom :PListItem;
    Size: longint;
    constructor Init;
    destructor Done;
    procedure AddTopItem(X:TData);
    procedure AddBottomItem(X:TData);
    function RemoveTopItem(var X:TData):boolean;
    function RemoveBottomItem(var X:TData):boolean;
  end;

  TStackMethod=(FIFO,FILO);

  PStack = ^TStack;
  TStack = object(TCommonList)
    Method: TStackMethod;
    constructor Init(AMethod:TStackMethod);
    procedure Push(X:TData);
    function Pop(var X:TData):boolean;
  end;


constructor TCommonList.Init;
begin
  Top:=nil;
  Bottom:=nil;
  Size:=0;
end;

destructor TCommonList.Done;
var
  tmp:PListItem;
begin
  while Top<>nil do begin
    tmp:=Top^.Next;
    dispose(Top);
    Top:=tmp;
  end;
end;

procedure TCommonList.AddTopItem(X:TData);
var
  tmp:PListItem;
begin
  new(tmp);
  tmp^.AData:=X;
  tmp^.Next:=Top;
  if Size=0 then Bottom:=tmp;
  Top:=tmp;
  inc(Size);
end;

procedure TCommonList.AddBottomItem(X:TData);
var
  tmp:PListItem;
begin
  new(tmp);
  tmp^.AData:=X;
  tmp^.Next:=nil;
  if Size=0 then begin
    Top:=tmp;
  end else begin
    Bottom^.Next:=tmp;
  end;
  Bottom:=tmp;
  inc(Size);
end;

function TCommonList.RemoveTopItem(var X:TData):boolean;
var
  tmp:PListItem;
begin
  if Size>0 then begin
    RemoveTopItem:=true;
    X:=Top^.AData;
    tmp:=Top;
    Top:=Top^.Next;
    dec(Size);
    Dispose(tmp);
    if Size=0 then Bottom:=nil;
  end else begin
    RemoveTopItem:=false;
  end;
end;

function TCommonList.RemoveBottomItem(var X:TData):boolean;
var
  tmp:PListItem;
begin
  if Size>0 then begin
    RemoveBottomItem:=true;
    X:=Bottom^.AData;
    tmp:=Top;
    while tmp^.Next<>Bottom do tmp:=tmp^.Next;
    tmp^.Next:=nil;
    Dispose(Bottom);
    Bottom:=tmp;
    dec(Size);
    if Size=0 then Bottom:=nil;
  end else begin
    RemoveBottomItem:=false;
  end;
end;


constructor TStack.Init(AMethod:TStackMethod);
begin
  inherited Init;
  Method:=AMethod;
end;

procedure TStack.Push(X:TData);
begin
  case Method of
    FIFO: AddBottomItem(X);
    FILO: AddTopItem(X);
  end;
end;

function TStack.Pop(var X:TData):boolean;
begin
  Pop:=RemoveTopItem(X);
end;

procedure PrintStack(AStack:PStack);
var
  X:TData;
begin
  while AStack^.Pop(X) do Write(X,', ');
  Writeln('The end');
end;

var
  Stack1, Queue1 : PStack;


begin


  New(Stack1,Init(FILO));
  New(Queue1,Init(FIFO));

  Stack1^.Push(1);
  Stack1^.Push(2);
  Stack1^.Push(3);
  PrintStack(Stack1);


  Queue1^.Push(1);
  Queue1^.Push(2);
  Queue1^.Push(3);
  PrintStack(Queue1);


  Dispose(Stack1,Done);
  Dispose(Queue1,Done);
  readln;
end.

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

TStack - это класс который реализует стеки с двумя алгоритмами обслуживания.
В стеках определены методы PUSH и POP которые соответственно запихивают и снимают элементы со стека.

В зависимости от алгоритма обслуживания запИхнутые числа 1,2,3 выйут обратном (FILO) или прямом (FIFO) порядке.

[Vanya]

Это на Паскале? А что такое constructor? Оъекты мы еще не проходили. Но за алгоритм спасибо!!!

[Naeel Maqsudov]

Это на ЧИСТОМ турбо-паскале, начиная с версии 5.5.

constructor и destructor - это процедуры вызываемые при создании и декомпозиции объекта, соответственно. В принципе, если объекты не проходили, то можно обойтись и без объектов.
Вместо объектов нужно определить записи, и использовать глобаольные переменные этих типов.

т.е.

Код: Выделить всё

  TStack = record 
    Top : PListItem; 
    Bottom :PListItem; 
    Size: longint; 
    Method: TStackMethod; 
  end; 

Var Stack1:TStack;

При этом в процедурах и функциях (бывших методах) надо добавить еще один параметр
типа TStack, чтобы процедура знала с каким именно стеком надо работать.
Примерно так:

Код: Выделить всё

function Pop(var AStack:TStack; var X:TData):boolean; 
begin 
  Pop:=RemoveTopItem(AStack,X); 
end; 

Т.е. можно минимальными переделками обойтись