
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


 
component GenericQueue ( Queue, Element );
 type Queue;
      Queue (MaxLength = integer) -> Queue;
      Length( Queue )           -> integer;
      Empty ( Queue )           -> boolean;
      Full ( Queue )            -> boolean;
      Push ( Queue, Element)    -> nothing;
      Pull ( Queue )            -> Element;
begin
      Queue (MaxLength) = Queue:[ MaxLength; length:=0; list=alist(Element) ];
      Length ( queue ) = queue.length;
      Empty ( queue ) = (queue.length <= 0);
      Full ( queue ) = (queue.length >= queue.MaxLength);
 
      Push ( queue, element ) = 
                   [ exception (Full(queue), "Queue Overflow");
                     queue.length:= queue.length + 1;
                     add (queue.list, element)];
      Pull ( queue ) = 
                   [ exception (Empty(queue), "Queue Underflow");
                     queue.length:= queue.length - 1;
                     remove(first(queue.list))]; 
end component GenericQueue;
 