Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Дек

Дек - структура данных, выполняющая быстрое удаление/вставку первого и последнего элемента.

Листинг Delphi

type DequeData = integer;
     PDequeNode = ^DequeNode;
     DequeNode = record
       key : DequeData;
       prev, next : PDequeNode;
     end;
     Deque = object
       public
         head, tail : PDequeNode;
       public
         constructor Create;
         function Empty : boolean;
         procedure WriteHead(x : DequeData);
         procedure WriteTail(x : DequeData);
         function ReadHead : DequeData;
         function ReadTail : DequeData;
     end;

implementation

constructor Deque.Create;
  begin
    head := nil;
    tail := nil;
  end;

  function Deque.Empty : boolean;      // Пуст ли дек?
  begin
    Result := (head = nil) and (tail = nil);
  end;

  procedure Deque.WriteHead(x : DequeData);  // Добавление элемента в начало
    var T : PDequeNode;
  begin
    new(T);
    T^.key := x;
    T^.prev := nil;
    T^.next := head;
    head := T;
    if tail <> nil
      then T^.next^.prev := T
      else tail := T;
  end;

  procedure Deque.WriteTail(x : DequeData);  // Добавление элемента в конец
    var T : PDequeNode;
  begin
    new(T);
    T^.key := x;
    T^.next := nil;
    T^.prev := tail;
    tail := T;
    if head <> nil
      then T^.prev^.next := T
      else head := T;
  end;

  function Deque.ReadHead : DequeData;  // Извлечение элемента с начала
    var T : PDequeNode;
  begin
    if Empty
      then { UNDERFLOW }
           exit;
    Result := head^.key;
    if head^.next <> nil
      then head^.next^.prev := nil
      else tail := nil;
    T := head;
    head := T^.next;
    dispose(T); 
  end;

  function Deque.ReadTail : DequeData; // Извлечение элемента с конца
    var T : PDequeNode;
  begin
    if Empty
      then { UNDERFLOW }
           exit;
    Result := tail^.key;
    if tail^.prev <> nil
      then tail^.prev^.next := nil
      else head := nil;
    T := tail;
    tail := T^.prev;
    dispose(T);
  end;


08.12.2007, 19:15