Linear QUEUE:
Linear Queue is a Queue in which the elements are arranged in a linear order, one after the other like the elements of one-dimensional array or linked list. The arrangement of elements and storage is similar to array or linked list, but the insertion and deletion are restricted.
Implementation of Linear QUEUE using one-dimensional array:
The linear QUEUE can be represented graphically as consecutive blocks when it is implemented using one-dimensional array. N the maximum number of elements can be added into the QUEUE is called as size of QUEUE. To represent a QUEUE an array of size N can be used. The capacity of QUEUE in this case will be N.
In the above representation the size of QUEUE is 8. FRONT and REAR index variables can be used to do the DELETE and ADD operations respectively. Initially when the QUEUE is empty FRONT and REAR are assigned with a value 0,because of Lower Bound 1 of array. When both are equal to 0, then the QUEUE is said to be empty.
When first element is added into the QUEUE, REAR and FRONT are both incremented by 1 and the element to be added is placed at REAR index of QUEUE, QUEUE is name of the array i.e. FRONT<--1, REAR<--1 and QUEUE[REAR]<--ITEM. ITEM is the element to be added to QUEUE. In the further addition operation, the REAR is incremented and the ITEM is copied at REAR index. When the REAR is equal to N, the QUEUE, QUEUE is said to be full. If any addition is done when the QUEUE is full, ‘overflow’ occurs.
When the element is to be deleted from the QUEUE, the element stored in the QUEUE with FRONT index is deleted by copying it in ITEM and the incrementing FRONT by 1. When FRONT is equal to 0, the QUEUE is empty. When the QUEUE is empty and if the deletion operation is done ‘underflow’, occurs. As an example, consider a QUEUE of size8. It is initially represented as follows:
Linear Queue is a Queue in which the elements are arranged in a linear order, one after the other like the elements of one-dimensional array or linked list. The arrangement of elements and storage is similar to array or linked list, but the insertion and deletion are restricted.
Implementation of Linear QUEUE using one-dimensional array:
The linear QUEUE can be represented graphically as consecutive blocks when it is implemented using one-dimensional array. N the maximum number of elements can be added into the QUEUE is called as size of QUEUE. To represent a QUEUE an array of size N can be used. The capacity of QUEUE in this case will be N.
When first element is added into the QUEUE, REAR and FRONT are both incremented by 1 and the element to be added is placed at REAR index of QUEUE, QUEUE is name of the array i.e. FRONT<--1, REAR<--1 and QUEUE[REAR]<--ITEM. ITEM is the element to be added to QUEUE. In the further addition operation, the REAR is incremented and the ITEM is copied at REAR index. When the REAR is equal to N, the QUEUE, QUEUE is said to be full. If any addition is done when the QUEUE is full, ‘overflow’ occurs.
When the element is to be deleted from the QUEUE, the element stored in the QUEUE with FRONT index is deleted by copying it in ITEM and the incrementing FRONT by 1. When FRONT is equal to 0, the QUEUE is empty. When the QUEUE is empty and if the deletion operation is done ‘underflow’, occurs. As an example, consider a QUEUE of size8. It is initially represented as follows:
When element is deleted from the QUEUE, ITEM is copied with A, because QUEUE [FRONT] gives A and FRONT is incremented, QUEUE becomes,
When G is added into QUEUE, the QUEUE becomes,
When I is added into the QUEUE, overflow occurs because REAR=8, the size of QUEUE and QUEUE is full. Even though 1 2 3 4 indices are free, the overflow occurs, this is the disadvantage Circular Queue is used.