
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

Create a queue data structure and demonstrate its operations.

(For implementations of queues, see the FIFO task.)



Operations:

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


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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% definitions of queue
empty(U-V) :-
    unify_with_occurs_check(U, V).
 
push(Queue, Value, NewQueue) :-
    append_dl(Queue, [Value|X]-X, NewQueue).
 
 
pop([X|V]-U, X, V-U) :-
    \+empty([X|V]-U).
 
 
 
append_dl(X-Y, Y-Z, X-Z).
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% use of queue
queue :-
    % create an empty queue
    empty(Q),
    format('Create queue ~w~n~n', [Q]),
 
    % add numbers 1 and 2
    write('Add numbers 1 and 2 : '),
    push(Q, 1, Q1),
    push(Q1, 2, Q2),
 
    % display queue
    format('~w~n~n', [Q2]),
 
    % pop element
    pop(Q2, V, Q3),
 
    % display results
    format('Pop : Value ~w Queue : ~w~n~n', [V, Q3]),
 
    % test the queue
    write('Test of the queue : '),
    (   empty(Q3) -> writeln('Queue empy'); writeln('Queue not empty')), nl,
 
    % pop the elements
    write('Pop the queue : '),
    pop(Q3, V1, Q4),
    format('Value ~w Queue : ~w~n~n', [V1, Q4]),
 
    write('Pop the queue : '),
    pop(Q4, _V, _Q5).
 