Queue data structure

 DATA STRUCTURE USING 'C' (Note)

 

UNIT: - 4.2

STACKS AND QUEUES: -

 Representation of Queue using arrays and linked list

Circular queues, Priority Queue

Queue: -

1. Queue is also an abstract data type or a linear data structure and can be defined as order list in which elements may be added or insertion operations done through one end called the REAR and delete operation can be performed at other end called FRONT.

2. REAR is also called TAIL and FRONT is also called as HEAD.

3. Queue is also known as FIFO (First in First out) because the first element which is added to the queue will be the first element to be removed from the queue.

4. Suppose a line of passenger waiting to buy tickets in a reservation counter each new passenger gets in line at the rear and the passenger at the front will be served.

5. The process to insert an element into queue is called Enqueue and the process of delete an element from the queue is called Dequeue.

6. Types of queue are: -

a. Linear queue

b. Circular queue

c. Priority queue

d. Deque

 

 

Queue basic features: -

1. Queue is also an ordered list of elements of similar data types like stack.

2. Queue follows FIFO (First in First out) principle.

3. Element which is inserted first will remove first in queue.

4. The function PEEK()is often used to return the value of first element without dequeue (remove) it.

Applications of linear queue: -

1. Queue is useful in CPU scheduling, Disk scheduling. When multiple processes require CPU at same time then queue data structure is used.

2. Various CPU scheduling algorithm are used which are implemented using queue data structure.

3. In printer, spooling documents are loaded into a buffer and then the printer pulls them off the buffer at its own.

4. Handling of interrupts in real-time systems. The interrupt are handled in the same order as they arrive FCFS (First Come First Serve).

 

Queue data structure can be represented in two different ways:-

1. Static Implementation

Static implementation is done by using array.

2. Dynamic Implementation

Dynamic implementation is done by using linked list.

The basic operations associated with queues are: -

1. Enqueue(): -To add an element into queue Enqueue function is called and if queue is full then it return overflow.

2. Dequeue(): -To delete an element from queue Dequeue function is called and if queue is empty it return underflow.

3. Front() : - To show the front element of the queue.

4. Rear() : - To show the rear element of the queue.

Array implementation of Queue: -

1. Queues may be represented in the computer memory by means of linear array.

2. There are two pointer variables i.e. front and rear where front denotes the location of the first element of the queue and rear denotes the least element of the queue.

3. Initial/ starting value of rear and front pointer is -1

Rear = -1;

Front = -1;

4. While inserting first element into the queue the value of front should be set to 0(zero).

Front = 0;

5. When an element is added to the queue the value of rear is increased by 1,

Rear = Rear + 1;

6. Condition to check either the queue is full or not

 Rear = Maxsize – 1;

7. When an item is deleted from the queue the front value is incremented by 1

Front = Front + 1;

8. When the last element is deleted from the queue front and rear must be set to -1.

Front = -1;

Rear = -1;

9. Condition to check either queue is empty or not

Front = = -1

Algorithm of basic operation of the array implementation: -

Enqueue(): -

Step 1: -        Check whether the queue is full.

if (rear =  maxsize-1)

               printf(“Queue is overflow”);

Step 2: -        Increment the rear index

rear = rear + 1;

Step 3: -        Insert the new element at rear end of queue.

queue[rear] = element;

Step 4: -        If initially the queue is empty then adjust front index.

if (front = = -1)

    front = o;

Dequeue (): -

Step 1: -        Check whether the queue is empty.

if (front = = -1)

printf(“Queue is underflow”);

Step 2: -        Delete the queue element at front end and return its value into temporary variable temp;

temp = queue[front]

Step 3: -        If queue is empty after deletion then set front and rear index t0 -1 else increment the front index.

if (front = =  rear)

    front = -1;

    rear = -1;

else

    front = front + 1;

Step 4: -        return (temp)

 

Implementation of queue using Linked List: -  

1. The major problem with the queue implemented using array is, it will work for an only fixed number of data values.

2. That means the amount of the data must be specified at the beginning itself.

3. A queue data structure can be implemented using a linked list data structure.

4. The queue which is implemented using linked list can work for unlimited number of values.

5. The queue implemented using linked list can organize as many data values we want.

6. In linked list implementation of a queue the last inserted node is always pointed by ‘rear’ and the first node is always pointed by ‘front’.                                                                                                                                                                                            

                                                                                                        

Circular queue: -

1. The limitation of linear queue is that even if there is a free memory space available in the linear queue we can nit uses that free memory space to insert element.

2. Circular queue is designed to overcome the limitation of linear queue.

3. Circular queue avoids the wastage of space in a linear queue implementation using arrays.

4. A circular queue is similar to a linear queue as it is also based on the FIFO principle except that the last position is connected to the first position in a circular queue that forms a circle.

5. Circular queue is also known as Ring buffer queue.

 

Algorithm of basic operation of the array implementation: -

Enqueue(): -

Step 1: -        Check whether the queue is full.

if ((front==0)&&(rear==maxsize-1)||(front == rear+1))

               printf(“Queue is overflow”);

Step 2: -        Increment the rear index

if (front == -1)

    front =0;

    rear = 0;

else

    if (rear== maxsize-1)

         rear = 0;

    else

         rear = rear +;

Step 3: -        Insert the new element at rear end of queue.

queue[rear] = element;

Step 4: -        Return

 

Dequeue (): -

Step 1: -        Check whether the queue is empty.

if (front = = -1)

printf(“Queue is underflow”);

Step 2: -        Delete the queue element at front end and return its value into temporary variable temp;

temp = queue[front]

Step 3: -        If queue is empty after deletion then set front and rear index t0 -1 else increment the front index.

if (front = =  rear)

    front = -1;

    rear = -1;

else

    if (front == maxsize-1)

         front = 0;

    else

         front = front + 1;

Step 4: -        return (temp)

 

*************** THE END ***************