Паскаль о котором не знали...

[ezswift]

Наиболее универсальным линейным списком, является Двусвязный Список.

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

Сначала давайте разберёмся с узлами списка.

Вот прямая аналогия - вагон состава:
1. Узлом списка является Платформа (node)
2. Частью двусвязного списка Платформа становится ТОЛЬКО после того как к ней прикреплены передняя и задняя сцепки (prev, next). На платформе они антисимметричны!, то есть зацепление происходит только если применены разные сцепки.
3. Контейнер может быть разного типа (сухогруз, цистерна...), но должен быть правильно описан.


Вот картинка схемы двусвязного узла:
Аналогия почти совершенная.


Откуда ведётся доступ?
Разумеется из кабин машинистов, то есть машиниств Тягача и машиниств Толкача.

Зачем такое излишество? Это - для свободы доступа к любому узлу и для поддержания Целостности списка. (при длинном составе, возможен разрыв сцепок, поэтому аналогия прослеживается и здесь.)
Даже, потеряв один адрес (толкача, например) мы можем методом траверсирования (от тягача) его просто восстановить. Это справедливо для любого звена списка.

А вот сам двусвязный список:
Как Вы видите, присутствует и тягач и толкач (header, trailer).


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

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

1. Самый простой функционал - стек.
Создаваемая для коммуникации переменная может доступаться только до header. И с header можно либо взять, либо положить туда какие-то значения.

2. Следующий функционал - очередь посложнее, так как создаваемая для коммуникации переменная может доступаться и до trailer(только для того чтобы положить данные) и до header, чтобы снять оттуда данные.

3. Следующий функционал - двунаправденная очередь.
Это самый интересный функционал и сегодня я Вам продемонстрирую программку, которая с ним работает.
Так как это всё же очередь, то создаваемая для коммуникации переменная может доступаться как до header, так и до trailer. Однако цель диктует расширение доступа то есть можно как положить, так и забрать данные как с header, так и с trailer.

Во всех случаях описанных функционалов доступ к внутренним узлам невозможен, то есть траверсирования в чистом виде НЕТ! (А список это может!)

Вот текст программки:

program deque;
type
(* Container type *)
  infoT = Char;

(* Types for DLL *)
  linkT = ^nodeT;

  nodeT = Record
               data: infoT;
               next, prev: linkT;
             End;

(* Type for deque *)
  deqT = Record
           front,rear: linkT;
         End;

(* Useful functions *)
Function isEmpty(Var deq: deqT): Boolean;
Begin
  isEmpty := (deq.front = nil);
End;

Procedure printDeq(Var deq: deqT);
  Var p: linkT;
Begin
  WriteLn( 'Printing Deque ...' );
  writeln;
  If isEmpty(deq) Then
    Begin
      WriteLn('<empty>'); Exit;
    End;
  p := deq.front;
  While p <> nil Do
    Begin
      Write( p^.data, ' ' );
      p := p^.next;
    End;
  WriteLn;
End;

Procedure pushFront(Var deq: deqT; Ch: infoT);
  Var neo: linkT;
Begin
  new(neo);
  neo^.next := deq.front;
  neo^.prev := nil;
  neo^.data := Ch;
  If deq.front <> nil Then
    deq.front^.prev := neo
  Else
    deq.rear := neo;
  deq.front := neo;
End;

Procedure pushRear(Var deq: deqT; Ch: infoT);
  Var neo: linkT;
Begin
  new(neo);
  neo^.next := nil;
  neo^.prev := deq.rear;
  neo^.data := Ch;
  If deq.rear <> nil Then
    deq.rear^.next := neo
  Else
    deq.front := neo;
  deq.rear := neo;
End;

Function popFront(Var deq: deqT): infoT;
  Var toDelete: linkT;
Begin
  popFront := #0;
  If isEmpty(deq) Then Exit;
  toDelete := deq.front;
  deq.front := toDelete^.next;
  If deq.front <> nil Then
    deq.front^.prev := nil
  Else
    deq.rear := nil;
  popFront := toDelete^.data;
  Dispose(toDelete);
End;

Function popRear(Var deq: deqT): infoT;
  Var toDelete: linkT;
Begin
  popRear := #0;
  If isEmpty(deq) Then Exit;
  toDelete := deq.rear;
  deq.rear := toDelete^.prev;
  If deq.rear <> nil Then
    deq.rear^.next := nil
  Else
    deq.front := nil;
  popRear := toDelete^.data;
  Dispose(toDelete);
End;

Procedure initDeq(Var deq: deqT);
Begin
  deq.front := nil;
  deq.rear := nil;
End;

Procedure killDeq(Var deq: deqT);
  var D: infoT;
Begin
  While not isEmpty(deq) Do D := popFront(deq);
End;

Var mD: deqT;
Begin
  initDeq(mD);
  pushFront(mD, 'A');
  pushFront(mD, 'B');
  pushRear(mD, 'F');
  pushRear(mD, 'G');
  writeln;
  writeln('Forward traversing');
  printDeq(mD);
  writeln;
  writeln('Backward traversing');
  writeln('Printing Deque ...');
  writeln;
  While not isEmpty(mD) Do
    WriteLn( popRear(mD) );
  killDeq(mD);
End.

А вот результат:


zen