LinkedListQueueDemo

Queues and stacks may be implemented as linked lists. Program LinkedListQueueDemo uses the same records and type of code as Program LinkedListDemo, which we explained in the Linked List section of this tutorial. You should find the queue easier to follow and to code for yourself than the normal linked list.

program LinkedListQueueDemo;
  {$APPTYPE CONSOLE}
uses
  SysUtils, StrUtils;
type
  PtrProg = ^TProg;
  TProg = record
    ProgramID : integer;
    ProgName : string[15];
    ProgrammerID : integer;
    Next : PtrProg;
  end;
var
  PtrFirst, PtrShow : PtrProg;
  Choice : integer;

procedure AppendRecord;
  var PtrNew, PtrCurrent : PtrProg;
begin
  new(PtrNew);
  write('Program ID? ');
  readln(PtrNew^.ProgramID);
  write('Program Name? ');
  readln(PtrNew^.ProgName);
  write('Programmer ID? ');
  readln(PtrNew^.ProgrammerID);
  PtrNew^.Next := nil;
  if PtrFirst = nil then
    begin
      PtrFirst := PtrNew;
    end
  else
    begin
      //Follow the Next pointers until the rear of the queue is reached.
      PtrCurrent := PtrFirst;
      while PtrCurrent^.Next <> nil do
        begin
          PtrCurrent := PtrCurrent^.Next;
        end;//while
      PtrCurrent^.Next := PtrNew;
    end; //if
end;

procedure DisplayRecord(RecPtr : PtrProg);
begin
  writeln(' Program ID: ', RecPtr^.ProgramID, '   Name: ', RecPtr^.ProgName,
          DupeString(' ', 14 - Length(RecPtr^.ProgName)),
          'Programmer ID: ', RecPtr^.ProgrammerID);
end;

function Dequeue : PtrProg;
begin
  result := PtrFirst;
  if PtrFirst <> nil then
    begin
      PtrFirst := PtrFirst^.Next;
    end;
end;

procedure Init;
begin
   PtrFirst := nil;
end;

begin
  Init;
  repeat
    writeln(#13#10'Please type the number of your choice.');
    writeln('1 - Enqueue a record');
    writeln('2 - Dequeue a record');
    writeln('3 - Quit');
    readln(Choice);
    case choice of
      1 : AppendRecord;
      2 : begin
            PtrShow := Dequeue;
            if PtrShow = nil then
              writeln('Queue empty')
            else
              begin
                writeln('Record removed from queue:'#13#10);
                DisplayRecord(PtrShow);
              end;
          end;
    end;
  until Choice = 3;
end.

In this program we find the position of the rear by following the next pointers until the nil value is reached. You may decide to make it more efficient by maintaining a pointer for the rear of the queue.

Going Further

See also our Smart Pascal demonstration of searching a tree for the use of a queue to store indices of nodes to be visited in a breadth first search (BFS).

Programming - a skill for life!

Demonstrations of queues, circular queues, and linked list queues