10: Linear Queue

linear queue
a queue is a data structure that is somewhat like a stack, except that in a queue the first item inserted is the first to be removed (first-in-first-out, fifo), while in a stack, as we ve seen, the last item inserted is the first to be removed (lifo). a queue works like the line you wait in.
the queue abstract data type defines a collection that keeps objects in a sequence, where:
- element access and deletion are restricted to the first element in the sequence, which is called the front of the queue, and
- element insertion is restricted to the end of the sequence, which is called the rear of the queue.
in a linear queue, the traversal through the queue is possible only once,i.e.,once an element is deletingd, we cannot insert another element in its position. this disadvantage of a linear queue is overcome by a circular queue, thus saving memory.
this restriction enforces the rule that items are inserted and deletingd in a queue according to the first-in first-out (fifo) principle. the queue supports the following two fundamental methods:
? enqueue(e): insert element e at the rear of the queue (end).
? dequeue(): remove and return from the queue the object at the front an error occurs if the queue is empty.
additionally, similar to the case with the stack adt, the queue adt includes the following supporting methods:
size(): return the number of objects in the queue.
isempty(): return a boolean value that indicates whether the queue is empty.
front(): return, but do not remove, the front object in the queue an error occurs if the queue is empty.
linear queue implementation
queue can be implemented in two different ways:
1. contiguous linear queue: the queue is implemented as an array.
2. linked linear queue: pointers and dynamic memory allocation is used to implement the queue.