
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
 Illustration of FIFO behavior
Task

Implement a FIFO queue.

Elements are added at one side and popped from the other in the order of insertion.



Operations:

   push   (aka enqueue)    - add element
   pop     (aka dequeue)    - pop first element
   empty                             - return truth value when empty


Errors:

   handle the error of trying to pop from an empty queue (behavior depends on the language and platform)


See

   Queue/Usage   for the built-in FIFO or queue of your language or standard library.


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


include "strings.coh";
include "malloc.coh";
 
# Define types. The calling code is expected to provide a QueueData type.
record QueueItem is
    data: QueueData;
    next: [QueueItem];
end record;
 
record QueueMeta is 
    head: [QueueItem];
    tail: [QueueItem];
end record;
 
typedef Queue is [QueueMeta]; 
const Q_NONE := 0 as [QueueItem];
 
# Allocate and free the queue datastructure.
sub MakeQueue(): (q: Queue) is
    q := Alloc(@bytesof QueueMeta) as Queue;
    q.head := Q_NONE;
    q.tail := Q_NONE;
end sub;
 
sub FreeQueue(q: Queue) is
    var cur := q.head;
    while cur != Q_NONE loop
        var next := cur.next;
        Free(cur as [uint8]);
        cur := next;
    end loop;
    Free(q as [uint8]);
end sub;
 
# Check if queue is empty.
sub QueueEmpty(q: Queue): (r: uint8) is 
    r := 0;
    if q.head == Q_NONE then
        r := 1;
    end if;
end sub;
 
# Enqueue and dequeue data. Cowgol has no exceptions, so the calling code
# should check QueueEmpty first.
sub Enqueue(q: Queue, d: QueueData) is
    var item := Alloc(@bytesof QueueItem) as [QueueItem];
    item.data := d;
    item.next := Q_NONE;
    if q.head == Q_NONE then
        q.head := item;
    else
        q.tail.next := item;
    end if;
    q.tail := item;
end sub;
 
sub Dequeue(q: Queue): (d: QueueData) is
    d := q.head.data;
    var cur := q.head;
    q.head := q.head.next;
    Free(cur as [uint8]);
    if q.head == Q_NONE then
        q.tail := Q_NONE;
    end if;
end sub;