
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


begin
    % define a Queue type that will hold StringQueueElements %
    record StringQueue ( reference(StringQueueElement) front, back );
    % define the StringQueueElement type %
    record StringQueueElement ( string(8)                     element
                              ; reference(StringQueueElement) next
                              );
    % we would need separate types for other element types   %
    % adds s to the end of the StringQueue q                 %
    procedure pushString ( reference(StringQueue) value q
                         ; string(8)              value e
                         ) ;
    begin
        reference(StringQueueElement) newElement;
        newElement := StringQueueElement( e, null );
        if front(q) = null then begin
            % adding to an empty queue %
            front(q) := newElement;
            back(q)  := newElement
            end
        else begin
            % the queue is not empty %
            next(back(q)) := newElement;
            back(q)       := newElement
        end
    end pushString ;
    % removes an element from the front of the StringQueue q %
    % asserts the queue is not empty, which will stop the    %
    % program if it is                                       %
    string(8) procedure popString ( reference(StringQueue) value q ) ;
    begin
        string(8) v;
        assert( not isEmptyStringQueue( q ) );
        v        := element(front(q));
        front(q) := next(front(q));
        if front(q) = null then % just popped the last element % back(q) := null;
        v
    end popStringQueue ;
    % returns true if the StringQueue q is empty, false otherwise %
    logical procedure isEmptyStringQueue ( reference(StringQueue) value q ) ; front(q) = null;
 
    begin % test the StringQueue operations %
        reference(StringQueue) q;
        q := StringQueue( null, null );
        pushString( q, "fred"   );
        pushString( q, "whilma" );
        pushString( q, "betty"  );
        pushString( q, "barney" );
        while not isEmptyStringQueue( q ) do write( popString( q ) )
    end
end.