Queue Part 1 | Introduction of Queue | Circular Queue | Data Structure & Algorithm #btech #cs

 

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. Representation of Queues Queues may be represented in the computer in various ways. usually by means at one-way lists or linear arrays. Unless otherwise stated or implied, each of our queues will be maintained by a linear array QUEUE and two pointer variables: FRONT, containing the location of the front element of the queue; and REAR, containing the location of the rear element of the queue. The condition FRONT = NULL will indicate that the queue is empty. Whenever an element is deleted from the queue, the value of FRONT is increased by 1; this can be implemented by the assignment FRONT = FRONT + 1 Similarly, whenever an element is added to the queue, the value of REAR is increased by 1; this can be implemented by the assignment REAR := REAR + 1 This means that after N insertions, the rear element of the queue will occupy QUEUE[N] or, in other words; eventually the queue will occupy the last part of the array. This occurs even though the queue itself may not contain many elements. Suppose we want to insert an element ITEM into a queue at the time the queue does occupy the last part of the array, i.e.. when REAR = N. One way to do this is to simply move the entire queue to the beginning of the array, changing FRONT and REAR accordingly, and then inserting ITEM as above. This procedure may be very expensive. The procedure we, adopt is to assume that the array QUEUE is circular, that is, that QUEUE[1] comes after QUEUE[N] in the array. With this assumption, we insert ITEM into the queue by assigning ITEM to QUEUE[ 1]. Specifically, instead of increasing REAR to N + 1, we reset REAR = I and then assign QUEUE[REAR] := ITEM Similarly, if FRONT = N and an element of QUEUE is deleted, we reset FRONT = 1 instead of increasing FRONT to N + 1. Suppose that our queue contains only one element, i.e.. suppose that FRONT = REAR != NULL and suppose that the element is deleted. Then we assign FRONT = NULL and REAR = NULL to indicate that the queue is empty.

For more details Click Here