Linear and Circular Queue

Linear and Circular Queue

In linear queue, when we delete any element, only the front is incremented by one but the position is not used later. So, when more addition or deletion is performed, memory wastage is increased. This drawback of array implementation of the linear queue is overcome by the circular queue.

In circular queue, the first element of the array ( the element at position 0) is immediately following its last element of the array. This implies that even if the last element is occupied, a new value can be inserted behind it in the first position of the array as long as the position is empty ( i.e. after insertion at n-1^th position, the next insertion is at 0). Hence, memory is reused and not wasted.

Algorithm

1. Declare and initialize necessary variables

head = 0, tail = 0, MAXSIZE, item, Queue[MAXSIZE]

2. For Enqueue Operation:

If head == (tail+1) % MAXSIZE:

Queue is Full

Else:

Read item from user

Queue[tail] = item

tail = (tail + 1) % MAXSIZE

For next enqueue, repeat step 2.

3, For Dequeue Operation:

If head = tail:

Queue is empty

Else:

item = Queue[head]

head = (head+1) % MAXSIZE

For next dequeue, repeat step 3.

References

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”