Representation of Queue Using Linked List |Queue Part 3 |Priority Queue | Data Structure & Algorithm

QUEUES

A queue is a linear list of elements in which deletions can take place only at one end, called the front, and insertions can take place only at the other end, called the rear. The terms "front" and "rear" are used in describing a linear list only when it is implemented as a queue. Queues are also called first-in first-out (FIFO) lists, since the first element in a queue will be the first element out of the queue. In other words, the order in which elements enter a queue is the order in which they leave. This contrasts with stacks, which are last-in first-out (LIFO) lists. Queues abound in everyday life. The automobiles waiting to pass through an intersection form a queue, in which the first car in line is the first car through; the people waiting in line at a bank form a queue, where the first person in line is the first person to be waited on; and so on. An important example of a queue in computer science occurs in a timesharing system, in which programs with the same priority form a queue while waiting to be executed. LINKED REPRESENTATION OF QUEUES In this video we discuss the linked representation of a queue. A linked queue is a queue implemented as a linked list with two pointer variables FRONT and REAR pointing to the nodes which is in the FRONT and REAR of the queue. The INFO fields of the list hold the elements of the queue and the LINK fields hold pointers to the neighboring elements in the queue. In the case of insertion into a linked queue, a node borrowed from the AVAIL list and carrying the item to be inserted is added as the last node of the linked list representing the queue. The REAR pointer is updated to point to the last node just added to the list. In the case of deletion, the first node of the list pointed to by FRONT is deleted and the FRONT pointer is updated to point to the next node in the list. The array representation of a queue suffers from the drawback of limited queue capacity. This in turn calls for the Checking of OVERFLOW condition every time an insertion is made into the queue. Also, due to the inherent disadvantage of the array data structure in which data movement is expensive, the maintenance of the queue calls for its circular implementation. In contrast, the linked queue is not limited in capacity and therefore as many nodes as the AVAIL list can provide, may be inserted into the queue. This dispenses with the need to check for the OVERFLOW condition during insertion. Also. unlike the array representation, the linked queue functions as a linear queue and there is no need to view it as 'circular' for efficient management of space. Representation of Queue Using Linked List Insertion Operation into Queue using Linked List LINKQ_INSERT(INFO,LINK, FRONT. REAR,AVAIL,ITEM) This procedure inserts an ITEM into a linked queue 1. [Available space?] If AVAIL = NULL, then Write OVERFLOW and Exit 2. [Remove first node from AVAIL list] Set NEW = AVAIL and AVAIL = LINK[AVAIL] 3. Set INFO[NEW] = ITEM and LINK[NEW]=NULL [Copies ITEM into new node] 4. If (FRONT = NULL) then FRONT = REAR = NEW [If Q is empty then ITEM is the first element in the queue Q] else set LINK[REAR) = NEW and REAR = NEW [REAR points to the new node appended to the end of the list] 5. Exit Representation of Queue Using Linked List Deletion Operation into Queue using Linked List LINKQ_DELETE (INFO, LINK, FRONT. REAR, AVAIL, ITEM) This procedure deletes the front element of the linked queue and stores it in ITEM 1. [Linked queue empty?] if (FRONT = NULL) then Write: UNDERFLOW and Exit 2. Set TEMP = FRONT [If linked queue is nonempty, remember FRONT in a temporary variable TEMP] 3. ITEM = INFO[TEMP] 4. FRONT = LINK [TEMP] [Reset FRONT to point to the next element in the queue] 5. LINK[TEMP] =AVAIL and AVAIL=TEMP [return the deleted node TEMP to the AVAIL list] 6. Exit

For more Details Click Here