Developing.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, стеки 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) порядке.

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

Это на ЧИСТОМ турбо-паскале, начиная с версии 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;

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

Developing.ru

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

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