Board index » delphi » Double Sided Queue

Double Sided Queue

I am trying to create a double ended queue in pascal in a circular array.

Can anyone please tell me the concept about. Or can anyone tell me where can
i find it ( the link in the internet )

deque( double queue )  :

It is a list in which entrys can be added or deleted from either the first
or last position of the list, but no changes can be made elsewhere in the
list. Thus a deque is a generslisation of both a stack and a queue.

 

Re:Double Sided Queue


Quote
"Thomas Ng" <t...@nel.com.sg> wrote:
>I am trying to create a double ended queue in pascal in a circular array.
>Can anyone please tell me the concept about. Or can anyone tell me where can
>i find it ( the link in the internet )
>deque( double queue )  :
>It is a list in which entrys can be added or deleted from either the first
>or last position of the list, but no changes can be made elsewhere in the
>list. Thus a deque is a generslisation of both a stack and a queue.

=============================

{The closest thing to your description in the field of linked lists is
the doubly linked list or double linked list. Each node points to both
the previous and the next node in the list. You can traverse the list
from either the head or the tail but you must take care of the
bookkeeping as to which nodes are the head and the tail.

Restricting additions and deletions to the head or tail is an artificial
restriction for, as with any linked list, you can add or delete any node
at any time. However, here is a demo that you can modifiy as you wish.

Turbo v6.0   <clifp...@airmail.net>   May 31, 1998 }

Program DoubleLinkedListDemo;

TYPE
    nPtr = ^node;   {points to linked list node}
    node = RECORD
              ch:Char;          {data}
              prev, nxt:nPtr;   {links}
           End;
VAR
   head, tail: nPtr;    {pointers to head and tail of list}
   s:String;
   n:Integer;

Procedure ExtendList(VAR hd1, t1:nPtr; c1:Char);
         { t1 (tail) is NIL before adding very first node}
VAR  tmp:nPtr;
Begin
     tmp := t1;
     NEW(t1);                     {assigns heap for new node}
     t1^.ch := c1;                {node data}
     t1^.prev := tmp;             {points to NIL or previous node}
     t1^.nxt := NIL;              {tail always points to nxt of NIL}
     If tmp = NIL then hd1 := t1  {for first node to mark head}
     Else tmp^.nxt := t1;         {link old tail to new}
End;

Procedure NewHead(VAR hd2, t2:nPtr; c2:Char);
Var tmp:nPtr;
Begin
     If hd2 = NIL then ExtendList(hd2, t2, c2)   {no list yet}
     Else
     Begin    {add and link new head}
          tmp := hd2;        {old head}
          NEW(hd2);          {get new node for new head}
          tmp^.prev := hd2;  {link old head to new}
          hd2^.prev := NIL;  {head always points to prev of NIL}
          hd2^.nxt := tmp;   {link new head to old}
          hd2^.ch := c2;     {store data}
     End;
End;

Procedure Drop(VAR cell:nPtr);
{Drops either head or tail node depending on "cell".}
VAR tmp:nPtr;
Begin
     tmp := cell;
     If tmp <> NIL Then  {list is not empty}
     Begin
        If tmp^.prev = NIL then  {detach head}
        Begin
             cell := tmp^.nxt;
             cell^.prev := NIL;
        End
        Else                     {detach tail}
        Begin
             cell := tmp^.prev;
             cell^.nxt := NIL;
        End;
        DISPOSE(tmp);  {drops either head or tail}
     End;
End;

Procedure ShowList(hd, tl:nPtr);
VAR tmp:nPtr;
Begin
     Writeln; Write('From head: ');
     tmp := hd;
     While tmp <> NIL Do
     Begin
          Write(tmp^.ch);
          tmp := tmp^.nxt;
     End;

     Writeln; Write('From tail: ');
     tmp := tl;
     While tmp <> NIL Do
     Begin
          Write(tmp^.ch);
          tmp := tmp^.prev;
     End;
     Writeln; Writeln('<<< Press Enter >>>':30); Readln;
End;

Begin
     For n := 1 to 10 Do Writeln;  {cosmetic}

     head := NIL;   tail := NIL;  {VERY IMPORTANT}
     s := 'brown fox jumped ';
     For n := 1 to Length(s) Do ExtendList(head, tail, s[n]);
     Writeln; Writeln;
     ShowList(head, tail);

     s := 'The quick ';   {Add chars to head in reverse order}
     For n := Length(s) downto 1 Do NewHead(head, tail, s[n]);
     Writeln('After adding several new "head" chars: ');
     ShowList(head, tail);

     s := 'over the lazy dogs back.';
     For n := 1 to Length(s) Do ExtendList(head, tail, s[n]);
     Writeln('After adding several tail chars:');
     ShowList(head, tail);

     For n := 1 to 5 Do Drop(head);
     For n := 1 to 8 Do Drop(tail);
     Writeln('5 nodes were dropped from head and 8 from tail:');
     ShowList(head, tail);
End.

Re:Double Sided Queue


Quote
Clif Penn wrote in message

<754B447AD860CA8A.6EDE19B1FB27A2D1.CE2159236BFC2...@library-proxy.airn
ews.net>...

Quote

>{The closest thing to your description in the field of linked lists
is
>the doubly linked list or double linked list. Each node points to
both
>the previous and the next node in the list. You can traverse the list
>from either the head or the tail but you must take care of the
>bookkeeping as to which nodes are the head and the tail.

One useful variation is that the head and tail can be held in a normal
node if possible. The ends of the list are then identified by a
pointer pointing to the head/tail node, rather than being NIL. This
wastes a small amount of space if the nodes are normal records but
makes the insertions and deletions simpler. I have suggested corrected
code below. If the nodes in the list are objects with one or more
virtual methods, the head and tail could be an ancestral object with
no data, wasting no space.

The example below can also be used to store nodes of different types,
as long as they are descended from tNode. But it would be up to the
user to decide how to determine the exact type of a node.

It has some other problems: don't pass the head/tail pointers as a Var
parameter for instance (see ShowList below) and there is some casting
from tNode into the actual data type. And the For statements dropping
nodes from the list would cause problems if they tried to delete more
elements than actually existed, or tried to remove the head/tail
pointers.

FP

Program DoubleLinkedListDemo;
Type
  ptNode  = ^tnode;   {points to linked list node}
  tNode   = Object
    pPrev, pNext:ptNode;   {links}
    Constructor Init;
    Destructor Done; Virtual;
      { Because there is a virtual method, there is a VMT. This
        means that SizeOf and Dispose will work with the actual
        size of a node rather than assuming it is the same size
        as tNode.
      }
    Procedure InsertBefore(var Node:tNode);
      { Insert Self before Node in whatever list Node is
        in.
        If Node is the first node in a list then Self
          becomes the new first node.
        If Node is the head/tail pointers of a list
        then Self becomes the last element in the list
        (extends the list) because the list is circular.
      }
    Procedure Unlink;
      { Remove Self from the list. If Self is not in a list then
        this will do nothing (because both pPrev and pNext will
        be pointing at Self.
      }
  End;
  ptChNode = ^tChNode;
  tChNode = Object(tNode)
    ch:Char;          {data}
  End;

Constructor tNode.Init;
Begin
  { The pointers only need to be initialised if the node is to
    be the head/tail pointers of a list, because otherwise they
    will be set when the node is inserted into a list.
    So initialise the node so that it is an empty list.
    This also has the effect that Unlink is harmless
  }
  pPrev := @Self;
  pNext := @Self;
End;

Destructor tNode.Done;
Begin
  { If the node is in a list, remove it before the node is
    deleted from the heap.
  }
  Unlink;
End;

Procedure tNode.InsertBefore(var Node:tNode);
Begin
  pPrev := Node.pPrev;
  Node.pPrev := @Self;
  pNext := pPrev^.pNext;
  pPrev^.pNext := @Self;
    { No special cases! This works whether Self is being
      inserted at the head or tail of the list, or anywhere
      in between.
    }
End;

Procedure tNode.Unlink;
Begin
  pPrev^.pNext := pNext;
  pNext^.pPrev := pPrev;
    { Again no special cases.
    }

  { Set the pointers so that another unlink will
    be harmless
  }
  pPrev := @Self;
  pNext := @Self;
End;

{ The rest is Clif's program changed where necessary to
  use the tNode and tChNode objects, so you can compare
  the two.

Quote
}

Procedure ExtendList(Var List:tNode; c:Char);
  { This is just a wrapper for InsertBefore to replace
    the function of the same name in the previous code
  }
Var
  pN : ptChNode;
Begin
  New(pN, Init);
  pN^.Ch := c;
  pN^.InsertBefore(List);
End;

Procedure NewHead(Var List:tNode; c:Char);
  { Again, this replaces the function of the same
    name in the previous code
  }
Begin
  ExtendList(List.pNext^, c);
End;

Procedure Drop(pCell:ptNode);
{Drops either head or tail node depending on "cell".}
Begin
  Dispose(pCell, Done);
End;

Procedure ShowList(var List:tNode);
  { Display the list of ptChNodes of which List holds the
    head and tail pointers.
    The var is important because the address of List is used
    to indicate the end of the list. In fact, it's so
    important that it might be better to pass a pointer
    (C-style) rather than a var parameter, just to emphasise
    the point; I'm in two minds about that.
  }
Var
  pN : ptChNode;
Begin
  Writeln; Write('From head: ');
  pN := ptChNode(List.pNext);
  While pN <> Addr(List) Do
  Begin
    Write(pN^.ch);
    pN := ptChNode(pN^.pNext);
  End;
  Writeln; Write('From tail: ');
  pN := ptChNode(List.pPrev);
  While pN <> Addr(List) Do
  Begin
    Write(pN^.ch);
    pN := ptChNode(pN^.pPrev);
  End;
  Writeln; Writeln('<<< Press Enter >>>':30); Readln;
End;

VAR
   List:tNode; { head & tail pointers }
   s:String;
   n:Integer;
Begin
     For n := 1 to 10 Do Writeln;  {cosmetic}
     List.Init;   {VERY IMPORTANT}
     s := 'brown fox jumped ';
     For n := 1 to Length(s) Do ExtendList(List, s[n]);
     Writeln; Writeln;
     ShowList(List);
     s := 'The quick ';   {Add chars to head in reverse order}
     For n := Length(s) downto 1 Do NewHead(List, s[n]);
     Writeln('After adding several new "head" chars: ');
     ShowList(List);
     s := 'over the lazy dogs back.';
     For n := 1 to Length(s) Do ExtendList(List, s[n]);
     Writeln('After adding several tail chars:');
     ShowList(List);
     For n := 1 to 5 Do Drop(List.pNext);
     For n := 1 to 8 Do Drop(List.pPrev);
     Writeln('5 nodes were dropped from head and 8 from tail:');
     ShowList(List);
     While List.pNext<>Addr(List) do
       Dispose(List.pNext, Done);
     List.Done;
End.

Other Threads