The following hybrid method of representing a queue has, to a certain extent, the advantages of...

  

Transcribed Image Text:

The following hybrid method of representing a queue has, to a certain extent, the advantages of both the linked and sequential representations. The queue is represented using a linked list of nodes with two pointers, F and R, to the first and last nodes of the list, respectively. The nodes have two fields, ITEM and LINK. LINK is a pointer to the next node in the list and ITEM is an array of M queue entries, where M is some fixed constant. For example, with M=5, suppose that the 12 values a, b, c, f, g, h, k, m, p, q, t, x were inserted into an empty queue in that order and then two values were deleted from the queue. The resulting queue would be represented by the following list: hkmpq F 1 x R The front of the queue is accessed using the pointer F and an index FIRST indicating the position in the array F ITEM of the first element in the queue. The rear of the queue is accessed using the pointer R and an index LAST indicating the position in the array R ITEM of the last element in the queue. In the above example the value of FIRST would be 3 and the value of LAST would be 2. Notes: (i) It is assumed here that array elements are indexed starting from 1. (ii) An empty queue is represented by F= nil. Give algorithms for the QUEUE and UNQUEUE operations. The following hybrid method of representing a queue has, to a certain extent, the advantages of both the linked and sequential representations. The queue is represented using a linked list of nodes with two pointers, F and R, to the first and last nodes of the list, respectively. The nodes have two fields, ITEM and LINK. LINK is a pointer to the next node in the list and ITEM is an array of M queue entries, where M is some fixed constant. For example, with M=5, suppose that the 12 values a, b, c, f, g, h, k, m, p, q, t, x were inserted into an empty queue in that order and then two values were deleted from the queue. The resulting queue would be represented by the following list: hkmpq F 1 x R The front of the queue is accessed using the pointer F and an index FIRST indicating the position in the array F ITEM of the first element in the queue. The rear of the queue is accessed using the pointer R and an index LAST indicating the position in the array R ITEM of the last element in the queue. In the above example the value of FIRST would be 3 and the value of LAST would be 2. Notes: (i) It is assumed here that array elements are indexed starting from 1. (ii) An empty queue is represented by F= nil. Give algorithms for the QUEUE and UNQUEUE operations.