Algorithm Queues in VB.NET

A queue is an ordered list in which all insertions take place at one end called the rear end.
  • 2364

A queue is an ordered list in which all insertions take place at one end called the rear end, while all deletions take place at the other end called the front end. A queue  is a pile in which items are added an one end and removed from the other. In this respect, a queue is like the line of customers waiting to be served by a bank teller.
 
As customers arrive, they join the end of the queue while the teller serves the customer at the head of the queue.
This makes the queue a First-In-First-Out (FIFO) data structure. 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.

queues.gif
 

A minimal set of useful operations on queue includes the following.

Create ( ) :- Q;

Insertion (Q, e) :- updated Q;

Deletion (Q) :- Q, e;

Isfull (Q) :- Boolean;

Isempty (Q) :- Boolean;

Front (Q) :- e;

Back (Q);

Destroy (Q);

Following are the algorithms for some functions of queue.

Algorithm: Create

Output: Q, Queue created

Method:

    Declare Q[SIZE] //Array with size=SIZE
    Declare and Initialize F=0, R=0

    //Front and Rear pointers to keep track of the front element and the rear element respectively

Algorithm ends

Algorithm: Isempty

Input: Q, Queue

Output: Boolean

Method:

    If (F==0)
        Return (yes)
    Else
        Return (no)
    If end

Algorithm ends

Algorithm: Isfull

Input: Q, Queue

Output: Boolean

Method:

   
If (R==SIZE)
        Return (yes)
    Else
        Return (no)
    If end

Algorithm ends

Algorithm: Front

Input: Q, Queue

Output: element in the front

Method:

    If (Isempty (Q))
        Print 'no front element'
    Else
        Return (Q[F])
    If end

Algorithm ends

Algorithm: Rear

Input: Q, Queue

Output: element in the rear

Method:

    If (Isempty (Q))
        Print 'no back element'
    Else
        Return (Q[R])
    If end

Algorithm ends

Algorithm: Insertion

Input: (1) Q, Queue; (2) e, element to be inserted; (3) SIZE, size of the Queue;

            (4) F, the front pointer; (5) R, the rear pointer

Output: (1) Q, updated; (2) F, updated; (3) R, updated

Method:

   
If (Isfull (Q)) then
        Print ('overflow')
    Else
        R=R+1;
        Q[R]=e
        If (F==0)
            F=1;
        If end
    If end

Algorithm ends

Algorithm: Deletion

Input: (1) Q, Queue; (2) SIZE, size of the Queue; (3) F, the front pointer; (4) R, the rear pointer

Output: (1) Q, updated; (2) F, updated; (3) R, updated; (4) e, element if deleted;

Method:

   
If (Isempty (Q)) then
        Print ('Queue is empty')
    Else
        e = Q[F]
        If (F==R)
            F=R=0;
        Else
            F=F+1;
        If end
    If end

Algorithm ends

However, the linear queue makes less utilization of memory i.e., the 'return (isfull (Q)) = yes' does not necessarily imply that there are n elements in the queue. This can be overcome by the using an alternate  queue called the circular queue.

Categories

More Articles

© 2013 dotNetheaven. All rights reserved.