
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


# -*- coding: utf-8 -*- #
CO REQUIRES:
  MODE OBJLINK = STRUCT(
    REF OBJLINK next,
    REF OBJLINK prev,
    OBJVALUE value # ... etc. required #
  );
  PROC obj link new = REF OBJLINK: ~;
  PROC obj link free = (REF OBJLINK free)VOID: ~
END CO
 
# actually a pointer to the last LINK, there ITEMs are ADDED/get #
MODE OBJQUEUE = REF OBJLINK; 
 
OBJQUEUE obj queue empty = NIL;
 
BOOL obj queue par = FALSE; # make code thread safe #
SEMA obj queue sema = LEVEL ABS obj queue par;
# Warning: 1 SEMA for all queues of type obj, i.e. not 1 SEMA per queue #
 
PROC obj queue init = (REF OBJQUEUE self)REF OBJQUEUE:
  self := obj queue empty;
 
PROC obj queue put = (REF OBJQUEUE self, OBJVALUE obj)REF OBJQUEUE: (
  REF OBJLINK out = obj link new;
  IF obj queue par THEN DOWN obj queue sema FI;
  IF self IS obj queue empty THEN
    out := (out, out, obj) # self referal #
  ELSE # join into list #
    out := (self, prev OF self, obj);
    next OF prev OF out := prev OF next OF out := out
  FI;
  IF obj queue par THEN UP obj queue sema FI;
  self := out
);
 
# define a useful prepend/put/plusto (+=:) operator... #
PROC obj queue plusto = (OBJVALUE obj, REF OBJQUEUE self)OBJQUEUE: obj queue put(self,obj);
OP +=: = (OBJVALUE obj, REF OBJQUEUE self)REF OBJQUEUE: obj queue put(self,obj);
# a potential append/plusab (+:=) operator...
OP (REF OBJQUEUE, OBJVALUE)OBJQUEUE +:= = obj queue plusab;
#
 
# see if the program/coder wants the OBJ problem mended... #
PROC (REF OBJQUEUE #self#)BOOL obj queue index error mended 
  := (REF OBJQUEUE self)BOOL: (abend("obj queue index error"); stop);
 
PROC on obj queue index error = (REF OBJQUEUE self, PROC(REF OBJQUEUE #self#)BOOL mended)VOID:
  obj queue index error mended := mended;
 
PROC obj queue get = (REF OBJQUEUE self)OBJVALUE: (
# DOWN obj queue sema; #
  IF self IS obj queue empty THEN
    IF NOT obj queue index error mended(self) THEN abend("obj stack index error") FI FI;
  OBJQUEUE old tail = prev OF self;
  IF old tail IS self THEN # free solo member #
    self := obj queue empty
  ELSE # free self/tail member #
    OBJQUEUE new tail = prev OF old tail;
    next OF new tail := self;
    prev OF self := new tail
  FI;
#;UP obj queue sema #
  OBJVALUE out = value OF old tail;
# give a recovery hint to the garbage collector #
  obj link free(old tail);
  out
);
 
PROC obj queue is empty = (REF OBJQUEUE self)BOOL:
  self IS obj queue empty;
 
SKIP