View source for Epita:Algo:Course:Sup-Info:Elementary Data Structures

== The linear list ==

The ''linear list'' is the most fundamental abstract data type that can be found. They are sequences of elements. The order of elements in a list doesn't depend on the element values, but on their position in the list. There are two ways to describe a list : iteratively or recursively. We will consider both and see what kind of memory implementation is best suited for these different types of list. Lists are a particularly flexible structure because they can grow and shrink on demand, and elements can be accessed, inserted, modified and deleted at any position within a list. Lists can also (for the same price:)) be concatenated together, split into sublists, used to retrieve information, and so on.

=== The ''recursive list'' type ===

 '''types'''<br/>
    list, box<br/>
 '''uses'''<br/>
    element<br/>
 '''operations'''<br/>
    emptylist : <math>\rightarrow</math> list
         cons : list x element <math>\rightarrow</math> list
         tail : list <math>\rightarrow</math> list
         head : list <math>\rightarrow</math> box
     contents : box <math>\rightarrow</math> element
        first : list <math>\rightarrow</math> element
         next : box <math>\rightarrow</math> box<br/>
 '''preconditions'''<br/>
    tail(''l'') is-defined-iaoi ''l'' ≠ emptylist
    head(''l'') is-defined-iaoi ''l'' ≠ emptylist
    first(''l'') is-defined-iaoi ''l'' ≠ emptylist<br/>
 '''axioms'''<br/>
    first(''l'') = contents(head(''l''))
    tail(cons(''e,l'')) = ''l''
    first(cons(''e,l'')) = ''e''
    next(head(''l'')) = head(tail(''l''))<br/>
 '''with'''<br/>
    list ''l''
    element ''e''

Thereafter we won't give terminology elements used in abstract type definitions.
So, for the last time, in the above abstract type we have:

<br/>

* <tt>List</tt> and <tt>Box</tt> as defined types
* <tt>element</tt> as predefined types
* <tt>head</tt> and <tt>next</tt> as internal operations of Box
* <tt>contents</tt> as observer of Box
* <tt>emptylist</tt>, <tt>tail</tt> and <tt>cons</tt> as internal operations of list
* <tt>first</tt> as observer of list

<br/>

These operations are not defined everywhere, therefore there are '''preconditions'''.
The algebraic definition gives to the various functions the following roles:

<br/>

* <tt>emptylist</tt> create a <tt>list</tt> without <tt>element</tt> (a kind of "constructor")
* <tt>head</tt> retrieves the first <tt>box</tt> 
* <tt>contents</tt> retrieves the <tt>element</tt> which is inside a <tt>box</tt>
* <tt>first</tt> retrieves the first <tt>element</tt> of a <tt>list</tt> (without using intermediate <tt>box</tt> )
* <tt>tail</tt> deletes the <tt>head</tt> <tt>element</tt> and retrieves the rest of the <tt>list</tt>
* <tt>cons</tt> creates an <tt>element</tt> at the first position (inserting it in a new <tt>box</tt> just before the existing <tt>list</tt>)
* <tt>next</tt> pass to the next <tt>box</tt>

<br/>

=== The ''iterative list'' type ===

 '''types'''<br/>
    list, box<br/>
 '''uses'''<br/>
    integer, element<br/>
 '''operations'''<br/>
    emptylist : <math>\rightarrow</math> list
       access : list x integer <math>\rightarrow</math> box
     contents : box <math>\rightarrow</math> element
          nth : list x integer <math>\rightarrow</math> element
       length : list <math>\rightarrow</math> integer
       delete : list x integer <math>\rightarrow</math> list
       insert : liste x integer x element <math>\rightarrow</math> list
         next : box <math>\rightarrow</math> box<br/>
 '''preconditions'''<br/>
    access(''l,k'') is-defined-iaoi ''l'' ≠ emptylist & ''1'' ≤ ''k'' ≤ length(''l'')
    delete(''l,k'') is-defined-iaoi ''l'' ≠ emptylist & ''1'' ≤ ''k'' ≤ length(''l'')
    insert(''l,k,e'') is-defined-iaoi ''1'' ≤ ''k'' ≤ length(''l'')+1<br/>
 '''axioms'''<br/>
    length(emptylist) = ''0''
    length(delete(''l,k'')) = length(''l'')-''1''
    length(insert(''l,k,e'')) = length(''l'')+''1''<br/>
    1 ≤ i < k <math>\Rightarrow</math> nth(delete(''l,k''),''i'') = nth(''l,i'')
    k ≤ i ≤ length(''l'')-1 <math>\Rightarrow</math> nth(delete(''l,k''),''i'') = nth(''l,i+1'')<br/>
    1 ≤ i < k <math>\Rightarrow</math> nth(insert(''l,k,e''),''i'') = nth(''l,i'')
    k = i <math>\Rightarrow</math> nth(insert(''l,k,e''),''i'') = ''e''
    k < i ≤ length(''l'')+''1'' <math>\Rightarrow</math> nth(insert(''l,k,e''),''i'') = nth(''l,i-1'')<br/>
    contents(access(''l,k'')) = nth(''l,k'')
    next(access(''l,k'')) = access(''l'',''k+1'')<br/>
 '''with'''
    list ''l''
    integer ''i,k''
    element ''e''

This presentation is another form of implementation of linear lists. In fact, the basic operation is no longer the access to the first box of a list (<tt>head</tt> operation), but the operation <tt>access</tt> which refers to the <tt>k</tt><sup>th</sup> place of this list. Other operations directly arise from this operation.

The '''iterative list''' abstract type, although more adapted to other functionings, can also describe recursive processing.

What is important is to understand is that we are in fact describing the same data, only their manipulations are different. A simple way to demonstrate this is to write a type of operation in terms of the other and vice versa.

''To start, we are going to write the operations of the '''recursive''' type using the operations of the  '''iterative''' type:''

<br/>

{| border="0" cellpadding="2" align="center"
| align="right" | '''recursive'''
| align="center" | ⇔
| align="left" | '''iterative'''
|-
| align="right" | head (''l'')
| 
| align="left" | access (''l,1'') 
|- 
| align="right" | first (''l'')
|
| align="left" |  nth (''l,1'')
|-
| align="right" | tail (''l'')
|
| align="left" | delete (''l,1'')
|- 
| align="right" | cons (''e,l'')
|
| align="left" | insert (''l,1,e'')
|}

<br/>

''And inversely:''

<br/>

{| border="0" cellpadding="3" align="center"
| align="right" | '''iterative'''
| align="center" | ⇔
| align="left" | '''recursive'''
|-
| align="right" | insert (''l,i,e'')
|
| align="left" | ''l2'' <math>\leftarrow</math> emptylist
|-
| align="right" rowspan="2" | '''''(i-1) times'''''
| rowspan="2" |  <math>\Bigg\{</math>
| align="left" | ''l2'' <math>\leftarrow</math> cons (first (''l''),''l2'')
|-
| align="left" | ''l'' <math>\leftarrow</math> tail (''l'')
|-
| align="right" | 
|
| align="left" | ''l'' <math>\leftarrow</math> cons (''e,l'')
|-
| align="right" rowspan="2" | '''''(i-1) times'''''
| rowspan="2" |  <math>\Bigg\{</math>
| align="left" | ''l'' <math>\leftarrow</math> cons (first (''l2''),''l'')
|-
| align="left" | ''l2'' <math>\leftarrow</math> tail (''l2'')
|}

<br/>

As can be seen, the match in this case is not just a single operation but, the operation <tt>insert</tt> has been transcribed using only the operations of the '''recursive list'''.

''<u>Note:</u> The translation of the other operations has been left in exercices.''

<br/>

=== Additional operations on list type ===

Of course, we often need additional operations on lists such as concatenation of two lists or the search for an item in a list. We call them : '''additional operations''' on the defined type. There is no need to represent the abstract type which is assumed to be known (I hope!).

For these two additional operations, we will present the profile, preconditions if necessary, and axioms for iterative and recursive lists.

==== Concatenation of two lists ====

The '''concatenation''' (also called '''append''') of two lists is the operation of joining two lists end-to-end. The elements of the 2<sup>nd</sup> list are added to the end of the first (''elements keep their own place within each list'').

 '''operations'''<br/>
    append : list x list <math>\rightarrow</math> list<br/>
 '''axioms ''(recursive list)'''''<br/>
    append(emptylist,''l'') = ''l''
    append(cons(''e,l''),''l2'') = cons(''e'',append(''l,l2''))<br/>
 '''axioms ''(iterative list)'''''<br/>
    length(append(''l,l2'')) = length(''l'')+length(''l2'')
    ''1'' < ''i'' < length(''l'') <math>\Rightarrow</math> nth(append(''l,l2''),''i'') = nth(''l,i'')
    length(''l'')+''1'' < ''i'' < length(''l'')+length(''l2'')
       <math>\Rightarrow</math> nth(append(l,l2),i) = nth(''l2,i''-length(''l''))<br/>
 '''with'''<br/>
    list ''l,l2''
    integer ''i''
    element ''e''

==== Search for an element ====

The research consists in finding an item in a list and returning its position if this element exists in the list. The problem is that the research is not defined for a non-present element. Therefore a research '''precondition''' is necessary. We will describe it using an auxiliary operation <tt>ispresent</tt>.

 '''operations'''<br/>
     research : element x list <math>\rightarrow</math> box
    ispresent : element x list <math>\rightarrow</math> boolean<br/>
 '''preconditions'''<br/>
    research(''e,l'') is-defined-iaoi ispresent(''e,l'') = ''true''<br/>
 '''axioms ''(recursive list)'''''<br/>
    ispresent(''e,emptylist'') = ''false''
    ''e = e2'' <math>\Rightarrow</math> ispresent(''e2'',cons(''e,l'')) = ''true''
    ''e'' ≠ ''e2'' <math>\Rightarrow</math> ispresent(''e2'',cons(''e,l'')) = ispresent(''e2,l'')
    ispresent(''e,l'') = ''true'' <math>\Rightarrow</math> contents(research(''e,l'')) = ''e''<br/>
 '''axioms ''(iterative list)'''''<br/>
    ispresent(''e'',emptylist) = ''false''
    ''e = e2'' <math>\Rightarrow</math> ispresent(''e2'',insert(''l,i,e'')) = ''true''
    ''e'' ≠ ''e2'' <math>\Rightarrow</math> ispresent(''e2'',insert(''l,i,e'')) = ispresent(''e2,l'')
    ispresent(''e,l'') = ''true'' <math>\Rightarrow</math> contents(research(''e,l'')) = ''e''<br/>
 '''with'''<br/>
    list ''l''
    integer ''i''
    element ''e,e2''

== Implementation of Lists ==

Lists, as all other data types, are implementable in different ways. The two basic forms are '''array implementation''' (static representation) and '''linked list implementation''' (dynamic representation using pointers).

Of course, for sophisticated data types, it is possible to represent them by a hybrid implementation (static and dynamic).

=== Array Implementation of Lists ===

Example of algorithmic declaration :

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    Maxnb = ''20''<br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                     <span style="color:#00FF00;">/* Element Definition */</span>
    t_vectMaxNbelts = Maxnb t_element   <span style="color:#00FF00;">/* Array of elements Definition */</span>
    t_list = '''record'''                     <span style="color:#00FF00;">/* List Definition */</span>
       t_vectNbmaxelts elts
       integer length
    '''end record''' t_list<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_list list

This could correspond to the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:array_implementation_list.png | 600px | ''Array Implementation of Lists'']]
|}

<br/>

In the array Implementation, we define the type '''t_list''' as a record having two fields. The first is an array of '''t_element''' whose length (''Maxnb'') is sufficient to hold the maximum size list that will be encountered. The second field is an integer (''length'') indicating the position of the last list element in the array. Indeed, the array implementation requires us to specify the maximum size of a list, then the field ''length'' indicates how many elements are really used in the array. The <tt>i</tt><sup>th</sup> element of the list is in the <tt>i</tt><sup>th</sup> cell of the array. Positions in the list are represented by integers, the <tt>i</tt><sup>th</sup> position  by the integer <tt>i</tt>. It's very simple (a 5 year-old would understand. At least, I think ...).

<br/>

''<u>Remark 1:</u> Inserting an element into the middle of the list requires shifting all following elements one place over in the array to make room for the new element. Similarly, deleting any element except the last also requires shifting elements to close up the gap. This is what makes this representation inefficient in case of frequent modifications of elements.''


''<u>Remark 2:</u> Contrary to what you might think, this representation is perfectly suited for recursive lists. In this case, the length serves as first position (Head box).''

=== Pointer implementation of Lists ===

Example of Algorithmic declaration :

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...         <span style="color:#00FF00;">/* Element definition */</span>
    t_plist = <math>\uparrow</math>t_liste      <span style="color:#00FF00;">/* pointeur t_plist definition */</span>
    t_list = '''record'''         <span style="color:#00FF00;">/* type t_list definition */</span>
       t_element elt
       t_plist lien
    '''end record''' t_list<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_plist list

This could correspond to the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_list.png | 600px | ''Pointer Implementation Lists'']]
|}

<br/>

The <tt>NUL</tt> pointer represents the end of the list ('''emptylist'''). 

The pointer implementation uses only as much space as is needed for the elements currently on the list. This implementation of lists uses pointers to link successive list elements. It frees us from using contiguous memory for storing a list and hence from shifting elements to make room for new elements or to close up a gap created by delete elements.  But one price we pay for this liberty is extra space for the pointer in each cell.

''<u>Remark:</u> The major drawback is not being able to access the <tt>K</tt><sup>th</sup> element directly. Indeed, in this kind of implementation, we have to follow the link cell by cell until locate the searched element. However, it is easy to concatenate two lists, add, or delete an item without having to shift any element. It is also very well suited to recursive processing.''

=== Implementation variants of lists ===

'''Using a sentinel'''

In some implementations, an extra '''sentinel''' or '''dummy''' node may be added before the first data record and/or after the last one.  This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node. 

In this case, the variable declaration becomes:

 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_list list

If we add a sentinel before the first cell, we could have the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_list_sentinel.png | 600px | ''Pointer Implementation of Lists ('''with a sentinel before the first data record''')'']]
|}

<br/>

'''Circular Lists'''

In the last node of a list, the link field often contains a '''null''' reference, a special value used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list. In that case the list is said to be '''circular''' or '''circularly linked''', otherwise it is said to be '''open''' or '''linear'''. If we've got a one element list, this one links itself.

In this case, there's no declaration type modification and we could have the following structure

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_list_circular.png | 600px | ''Pointer Implementation of Lists ('''circular''')'''']]
|}

<br/>

''<u>Note :</u> We could also use a sentinel (a node) instead of a single pointer''

<br/>

'''Doubly-Linked Lists'''


In a number of applications we may wish to traverse a list both forwards and backwards efficiently. Or, given an element, we may wish to determine the preceding and following elements quickly. In such situations we might wish to give each cell on a list a pointer to both the next and previous cells on the list.

In a '''doubly linked list''', each node contains, besides the next-node link, a second link field pointing to the ''previous'' node in the sequence.  The two links may be called '''forward'''('''s''') and '''backwards''', or '''next''' and '''prev'''('''ious''').

In this case, the variable declaration becomes:

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...             <span style="color:#00FF00;">/* Element Definition */</span>
    t_penreg = <math>\uparrow</math>t_enreg         <span style="color:#00FF00;">/* Pointer t_penreg Definition */</span>
    t_enreg = '''record'''            <span style="color:#00FF00;">/* t_enreg Definition */</span>
       t_element elt
       t_penreg next,prev
    '''end record''' t_enreg
    t_list = '''record'''             <span style="color:#00FF00;">/* t_liste Définition*/</span>
       t_penreg first,last
    '''end record''' t_list<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_list list

it could correspond to the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_list_doublylink.png | 600px | ''Pointer Implementation of Lists ('''Doubly Linked''')'']]
|}

<br/>

Of course, it is always possible to build other structures, for example a circular doubly linked list.

To conclude on the possible variants of the implementations of lists, it's possible to simulate pointers with cursors, that is, with integers that indicate positions in arrays. In this case, the array elements are records with two fields: the element  and an integer that is used as a cursor. 

In fact almost everything is possible, but using this kind of structure has no interest because it has all the drawbacks of static and dynamic combined (a bit like the Side-Car).

== Stacks and Queues ==
=== Stacks ===

Stacks are '''LIFO''' (''Last In First Out'') structures. That is to say that a stack is a special kind of list in which all inputs (''insertions'') and outputs (''deletions'') take place at one end, called the ''top''. The intuitive model of a stack is a pile of poker chips on a table, books on the floor, or dishes on a shelf where, if you are "''normal''" (and for some of students it's not sure), it is only convenient to remove the top object on the pile or add a new one above the top. In other words, it's a collection of items from which only the most recently added item may be removed.

The algebraic abstract data type Stack is the following:

 '''types'''<br/>
    stack<br/>
 '''uses'''<br/>
    boolean, element<br/>
 '''operations'''<br/>
    emptystack : <math>\rightarrow</math> stack
          push : stack x element <math>\rightarrow</math> stack
           pop : stack <math>\rightarrow</math> stack
           top : stack <math>\rightarrow</math> element
       isempty : stack <math>\rightarrow</math> boolean<br/>
 '''preconditions'''<br/>
    pop(''p'') is-defined-iaoi isempty(''p'') = False
    top(''p'') is-defined-iaoi isempty(''p'') = False<br/>
 '''axioms'''<br/>
    pop(push(''p,e'')) = p
    top(push(''p,e'')) = e
    isempty(emptystack) = True
    isempty(push(''p,e'')) = False<br/>
 '''with'''<br/>
       stack ''p''
     element ''e''

<br/>
The algebraic definition gives to the various functions the following roles:

<br/>

* <tt>emptystack</tt> creates a <tt>stack</tt> without <tt>element</tt> (a kind of "constructor")
* <tt>push</tt> inserts an <tt>element</tt> at the <tt>top</tt> of a <tt>stack</tt>
* <tt>pop</tt> deletes the <tt>top</tt> <tt>element</tt> of a <tt>stack</tt>
* <tt>top</tt> retrieves the <tt>element</tt> at the <tt>top</tt> of a <tt>stack</tt>
* <tt>isempty</tt> returns true if and only if the <tt>stack</tt> is empty 

<br/>

=== Array Implementation of Stacks ===

The array-based implementation of lists we gave before is not a particularly good one for stacks, as every '''push''' or '''pop''' requires moving the entire list up or down, thus taking time proportional to the number of elements on the stack. A better arrangement for using an array takes account of the fact that insertions and deletions occur only at the top. We can anchor the bottom of the stack at the bottom (low-indexed end) of the array, and let the stack grow towards the top (high-indexed end) of the array. A integer cursor called '''top''' indicates the current position of the first stack element. 

Example of algorithmic declaration :

 <span style="color:#0000FF;">'''Constantes'''</span><br/>
    Nbmax = 20                         <span style="color:#00FF00;">/* Maximum number of elements in the stack */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                    <span style="color:#00FF00;">/* Element definition */</span>
    t_elements = Nbmax t_element       <span style="color:#00FF00;">/* Element array definition  */</span>
    t_stack = '''record'''                   <span style="color:#00FF00;">/* Stack type definition */</span>
       t_elements elts
       integer top
    '''end record''' t_stack<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_stack stack

This idea is shown in the following figure :

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:array_implementation_stack.png | 600px | ''Array Implementation of Stacks'']]
|}

<br/>

=== Linked-link representation of stacks ===

The linked-list representation of a stack is easy, as '''push''' and '''pop''' operate only on the header cell and the first cell on the list.
It may be noted that the link is a previous link. When it pops, this link allows us to know what element, if it exists, had previously been stacked.

Example of Algorithmics declaration :

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                   <span style="color:#00FF00;">/* Element Definition */</span>
    t_pstack = <math>\uparrow</math>t_stack               <span style="color:#00FF00;">/* Pointer Type Definition */</span>
    t_stack = '''record'''                  <span style="color:#00FF00;">/* Définition du type t_pile */</span>
       t_element elt
       t_pstack  previous
    '''end record''' t_stack<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_pstack stack

This idea is shown in the following figure :

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_stack.png | 600px | ''Pointer Implementation of Stacks'']]
|}

<br/>

== Queues ==

Queues are another special kind of list, where items in the collection are kept in order. They are inserted at one end (the rear) and deleted or removed at the other end (the front). Another name of Queue is  a '''FIFO (''First In First Out'')''' list. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked.

The intuitive model of a Queue is a people queue in front of a theater. 

Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer. 

The algebraic abstract data type Queue is the following:

 '''types'''<br/>
    queue<br/>
 '''uses'''<br/>
    boolean, element<br/>
 '''operations'''<br/>
    emptyqueue : <math>\rightarrow</math> queue
       enqueue : queue x element <math>\rightarrow</math> queue
       dequeue : queue <math>\rightarrow</math> queue
         front : queue <math>\rightarrow</math> element
       isempty : queue <math>\rightarrow</math> boolean<br/>
 '''preconditions'''<br/>
    dequeue(''q'') is-defined-iaoi isempty(''q'') = False
    front(''q'') is-defined-iaoi isempty(''q'') = False<br/>
 '''axioms'''<br/>
    isempty(''q'') = true <math>\Rightarrow</math> front(enqueue(''q,e'')) = ''e''
    isempty(''q'') = false <math>\Rightarrow</math> front(enqueue(''q,e'')) = front(''q'')
    isempty(''q'') = true <math>\Rightarrow</math> dequeue(enqueue(''q,e'')) = emptyqueue
    isempty(''q'') = false <math>\Rightarrow</math> dequeue(enqueue(''q,e'')) = enqueue(dequeue(''q''),''e'')
    isempty(emptyqueue) = true
    isempty(enqueue(''q,e'')) = false<br/> 
 '''with'''<br/>
       queue ''q''
     element ''e''

<br/>
The algebraic definition gives to the various functions the following roles:

<br/>

* <tt>emptyqueue</tt> creates a <tt>queue</tt> without <tt>element</tt> (a kind of "constructor")
* <tt>enqueue</tt> inserts an <tt>element</tt> at the end of a <tt>queue</tt>
* <tt>dequeue</tt> deletes the <tt>front</tt> <tt>element</tt> ''(the first element of the queue)''
* <tt>front</tt> retrieves the first <tt>element</tt> of a <tt>queue</tt>
* <tt>isempty</tt> returns true if and only if the <tt>queue</tt> is empty 

<br/>
 
=== Array implementation of queues ===

We need an array to store the elements and two integers ''Front'' and ''Rear'' that allow us to always know where the beginning and the end of the Queue are.

Example of algorithmics declaration:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    Nbmax = 8                          <span style="color:#00FF00;">/* Maximum number of elements in the queue */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                    <span style="color:#00FF00;">/* Element type definition */</span>
    t_elements = Nbmax t_element       <span style="color:#00FF00;">/* Elements array definition */</span>
    t_queue = '''record'''                   <span style="color:#00FF00;">/* Queue type definition */</span>
       t_elements elts
       integer font,rear
    '''end record''' t_queue<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_queue queue

it could correspond to the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:array_implementation_queue.png | 600px  | ''Array Implementation of Queues'']]
|}

<br/>

But this representation is not very efficient. Indeed, <tt>Dequeue</tt>, which removes the first element, requires the entire queue be moved up one position in the array. Thus <tt>Dequeue</tt> takes <math>\omega (n)</math> times if the queue has <math>n</math> elements.

To avoid this expense, we must take a different viewpoint. Think of an array as a circle, where the first position follows the last as suggested in the next figure. The queue is found somewhere around the circle in consecutive positions, with the <tt>rear</tt> of the queue somewhere clockwise from the front.

To <tt>enqueue</tt> an element, we move the <tt>rear</tt> pointer one position clockwise and put the element in that position. To <tt>dequeue</tt> we simply move <tt>front</tt> one position clockwise. 

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:array_implementation_circle_queue.png | 600px | ''Circular Array Implementation of Queues'']]
|}

<br/>

For these two examples, we set Nbmax to 8. Except for the passage of 8 to 1, the values of Head and Tail are increased by 1. This overshoot is simply managed, just using a modulo Nbmax, the value 8 in this case.

=== Pointer implementation of queues ===

As for stacks, any list implementation is legal for queues. We can keep two pointers, one to the first element and one to the last one. These pointers are useful for executing <tt>enqueue</tt> and <tt>dequeue</tt> operations.

Exaple of algorithmics declaration:

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                   <span style="color:#00FF00;">/* element type definition */</span>
    t_prec = <math>\uparrow</math>t_rec                   <span style="color:#00FF00;">/* t_prec pointer type definition */</span>
    t_rec = '''record'''                    <span style="color:#00FF00;">/* t_queue type definition */</span>
       t_element elt
       t_prec    next
    '''end record''' t_rec<br/>
    t_queue = '''record'''                   <span style="color:#00FF00;">/* queue type definition */</span>
       t_prec front,rear
    '''end record''' t_queue<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_queue queue

It could correspond to the following structure '''''(a)''''':

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:pointer_implementation_queue.png | 600px | ''Pointer Implementation of Queues'']]
|}

<br/>

Note that in the case of a circular implementation '''''(b)''''', the <tt>front</tt> pointer is useless. Just follow the <tt>next</tt> link from the last element to determine the first element.
----
<small>''(Christophe "krisboul" Boullay)''</small>