Home | | **Object Oriented Programming and Data Structures** | Queue ADT and its applications, Applications, Implementations

A queue is like a "natural" queue of elements. It is an ordered list in which all insertions occur at one end called the back or rear of the queue, whereas all deletions occur at the other end called the front orhead of the queue.

**The Queue ADT**

A queue
is like a "natural" queue of elements. It is an ordered list in which
all insertions occur at one end called the **back**
or **rear** of the queue, whereas all
deletions occur at the other end called the **front** or**head** of the
queue.

**1. The queue ADT and its
applications**

In the
popular terminology, insertion and deletion in a queue are respectively called
the **enqueue **and the** dequeue **operations. The element
dequeued from a queue is always the first to** **have been enqueued among the elements currently present in the
queue. In view of this, a queue is often called a **First-In-First-Out** or a **FIFO**
list.

The
following functions specify the operations on the queue ADT. We are going to
maintain a queue of characters. In practice, each element of a queue can be of
any well-defined data type.

Q =
init();

Initialize
the queue Q to the empty queue.

isEmpty(Q);

Returns
"true" if and only if the queue Q is empty.

isFull(Q);

Returns
"true" if and only if the queue Q is full, provided that we impose a
limit on the maximum size of the queue.

front(Q);

Returns
the element at the front of the queue Q or error if the queue is empty.

Q =
enqueue(Q,ch);

Inserts
the element ch at the back of the queue Q. Insertion request in a full queue
should lead to failure together with some appropriate error messages.

Q =
dequeue(Q);

Delete
one element from the front of the queue Q. A dequeue attempt from an empty
queue should lead to failure and appropriate error messages.

print(Q);

Print the
elements of the queue Q from front to back

**2. Applications of queues**

• For
implementing any "natural" FIFO service, like telephone enquiries,
reservation requests,

traffic
flow, etc.

• For
implementing any "computational" FIFO service, for instance, to
access some resources.

Examples:
printer queues, disk queues, etc.

• F or
searching in special data structures (breadth-first search in graphs and
trees).

• For
handling scheduling of processes in a multitasking operating system.

**3. Implementations of the queue
ADT**

Continuing
with our standard practice followed so far, we are going to provide two
implementations of the queue ADT, the first using static memory, the second
using dynamic memory. The implementations aim at optimizing both the insertion
and deletion operations.

**3.1. Using static arrays**

Recall
that in our implementation of the "ordered list" ADT we always let
the list start from the array index 0. This calls for relocation of elements of
the list in the supporting array after certain operations (usually deletion).
Now we plan to exploit the specific insertion and deletion patterns in queues
to avoid these costly relocations. We maintain two indices to represent the
front and the back of the queue. During an enqueue operation, the back index is
incremented and the new element is written in this location. For a dequeue
operation, on the other hand, the front is simply advanced by one position. It
then follows that the entire queue now moves down the array and the back index
may hit the right end of the array, even when the size of the queue is smaller
than the capacity of the array. In order to avoid waste of space, we allow our
queue to wrap at the end. This means that after the back pointer reaches the
end of the array and needs to proceed further down the line, it comes back to
the zeroth index, provided that there is space at the beginning of the array to
accommodate new elements. Thus, the array is now treated as a circular one with
index MAXLEN treated as 0,MAXLEN + 1 as 1, and so on. That is, index
calculation is done modulo MAXLEN. We still don't have to maintain the total
queue size. As soon as the back index attempts to collide with the front index
modulo MAXLEN, the array is considered to befull.

There is
just one more problem to solve. A little thought reveals that under this
wrap-around technology, there is no difference between a full queue and an
empty queue with respect to arithmetic modulo MAXLEN. This problem can be
tackled if we allow the queue to grow to a maximum size of MAXLEN - 1. This
means we are going to lose one available space, but that loss is
inconsequential. Now the condition for full array is that the front index is
two locations ahead of the back modulo MAXLEN, whereas the empty array is
characterized by that the front index is just one position ahead of the back
again modulo MAXLEN. An implementation of the queue ADT under these design
principles is now given.

#define
MAXLEN 100

typedefstruct
{

char
element[MAXLEN];

int
front;

int back;
}

queue;

queueinit
()

{

queue Q;
Q.front = 0;

Q.back =
MAXLEN - 1;

return Q;

}

intisEmpty
( queue Q )

{

return
(Q.front == (Q.back + 1) % MAXLEN);

}

intisFull
( queue Q )

{

return
(Q.front == (Q.back + 2) % MAXLEN);

}

char
front ( queue Q )

{

if
(isEmpty(Q)) {

fprintf(stderr,"front:
Queue is empty\n"); return '\0';

}

returnQ.element[Q.front];

}

queueenqueue
( queue Q , char ch )

{

if
(isFull(Q)) {

fprintf(stderr,"enqueue:
Queue is full\n"); return Q;

}

++Q.back;

if
(Q.back == MAXLEN) Q.back = 0; Q.element[Q.back] = ch;

return Q;

}

queuedequeue
( queue Q )

{

if
(isEmpty(Q)) {

fprintf(stderr,"dequeue:
Queue is empty\n"); return Q;

}

++Q.front;

if
(Q.front == MAXLEN) Q.front = 0; return Q;

}

void
print ( queue Q )

{

inti;

if
(isEmpty(Q)) return; i = Q.front;

while (1)
{

printf("%c",
Q.element[i]); if (i == Q.back) break;

if (++i
== MAXLEN) i = 0;

}

}

Here is a
sample main() for these functions.

int main
()

{

queue Q;

Q =
init(); printf("Current queue : "); print(Q); printf("\n");

Q =
enqueue(Q,'h'); printf("Current queue : "); print(Q);
printf("\n");

Q =
enqueue(Q,'w'); printf("Current queue : "); print(Q);
printf("\n");

Q =
enqueue(Q,'r'); printf("Current queue : "); print(Q);
printf("\n");

Q =
dequeue(Q); printf("Current queue : "); print(Q);
printf("\n");

Q =
dequeue(Q); printf("Current queue : "); print(Q);
printf("\n");

Q =
enqueue(Q,'c'); printf("Current queue : "); print(Q);
printf("\n");

Q =
dequeue(Q); printf("Current queue : "); print(Q);
printf("\n");

Q =
dequeue(Q); printf("Current queue : "); print(Q);
printf("\n");

Q =
dequeue(Q); printf("Current queue : "); print(Q);
printf("\n");

}

Finally,
this is the output of the complete program.

Current
queue :

Current
queue : h

Current
queue :hw

Current
queue :hwr

Current
queue :wr

Current
queue : r

Current
queue :rc

Current
queue : c

Current
queue : dequeue:

Queue is
empty

Current
queue :

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Linear Data Structures : Queue ADT and its applications, Applications, Implementations |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.