
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 c:\cxpl\codes;
def Size=8;
int Fifo(Size);
int In, Out;            \fill and empty indexes into Fifo
 
proc Push(A);           \Add integer A to queue
int  A;                 \(overflow not detected)
[Fifo(In):= A;
In:= In+1;
if In >= Size then In:= 0;
];
 
func Pop;               \Return first integer in queue
int  A;
[if Out=In then                   \if popping empty queue
    [Text(0, "Error");  exit 1];  \ then exit program with error code 1
A:= Fifo(Out);
Out:= Out+1;
if Out >= Size then Out:= 0;
return A;
];
 
func Empty;             \Return 'true' if queue is empty
return In = Out;
 
[In:= 0;  Out:= 0;
Push(0);
Text(0, if Empty then "true" else "false");  CrLf(0);
IntOut(0, Pop);  CrLf(0);
Push(1);
Push(2);
Push(3);
IntOut(0, Pop);  CrLf(0);
IntOut(0, Pop);  CrLf(0);
IntOut(0, Pop);  CrLf(0);
Text(0, if Empty then "true" else "false");  CrLf(0);
 
\A 256-byte queue is built in as device 8:
OpenI(8);  OpenO(8);
ChOut(8, ^0);                   \push
ChOut(0, ChIn(8));  CrLf(0);    \pop
ChOut(8, ^1);                   \push
ChOut(8, ^2);                   \push
ChOut(8, ^3);                   \push
ChOut(0, ChIn(8));  CrLf(0);    \pop
ChOut(0, ChIn(8));  CrLf(0);    \pop
ChOut(0, ChIn(8));  CrLf(0);    \pop
]