AS/A2 Computing: The queue data structure

Queues are used in printer queues and in the operating system to organise operations to be processed. In different situations more complicated examples of the simple queue structure can be used such as priority queues.

Operations necessary for a queue are Create, Destroy (reinitialise), Enqueue, Serve, Full and Empty.

Defining the data type

const MaxSize = {Length of queue here};
type
  TQueue  = record
    Front : 0..MaxSize;
    Back  : 0..MaxSize;
    Count : 0..MaxSize;
    Que : array [1 ..MaxSize] of integer;
  end; // TQueue definition

Create Queue operation

// Returns true if Queue is created
function CreateQueue(VAR Q: TQueue) : boolean;
begin
with Q do begin
	Front  := 1;
	Back   := 0;
	Count  := 0;
	Result := true;
end; // with Q
end; // CreateQueue

Destroy Queue operation

// Returns true if Queue is destroyed
function DestroyQueue(VAR Q: TQueue) : boolean;
begin
with Q do begin
	Front  := 1;
	Back   := 0;
	Count  := 0;
	Result := true;
end; // with Q
end; // DestroyQueue

Full operation

// Returns true if Queue full
function Full (Q: TQueue) : boolean;
begin
with Q do begin
	Result := (Count = MaxSize);
end; // with Q
end;

Enqueue/Serve operation

// Adds an integer to the back of the Queue
procedure Enqueue (VAR Q: TQueue; e : integer);
begin
with Q do begin
	Back:=(Back mod MaxSize) + 1;
	Que[Back]:=e;
	Inc(Count);
end; // with Q
end; // Enqueue

Serve operation

// Value at the front of the queue served by copying to e
procedure Serve (VAR Q: TQueue; VAR e : integer);
begin
with Q do begin
	e:=Que[Front];
  Que[Front]:=0;
	Dec(Count);
	Front:=(Front mod MaxSize) + 1;
end; // with Q
end; // Serve

Peek operation

// "Peek" at the front of the queue; function returns front element
function Peek(Q: TQueue): integer;
begin
with Q do begin
        Result:=Que[Front];
end; // with Q
end; // Peek

Empty operation

// Returns true if queue empty
function Empty (Q: TQueue) : boolean;
// alternative method to return a boolean value
begin
with Q do begin
	Result := (Count = 0);
end; // with Q
end; // Empty

These notes are from a lesson on 16/09/2004.

Click here to view this page as a PDF file