** 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 ***************

## No comments:

## Post a Comment

Please do not enter any spam link in the comment box and use English and Hindi language for comment.