QUEUE OPERATIONS in DATASTRUCTURE AND ALGORITHMS

Queue Introduction and Operations

1. QUEUE
By
Mrs. P. Usha., MCA., M.Phil., SET.,NET.,(Ph.D)
Assistant Professor,
Department of Information Technology, Bishop
Heber College (Autonomous), Trichy-17.

2. QUEUE
Queue is an abstract (LINEAR) data structure
A queue is open at both its ends. One end is always used to insert data (enqueue)
and the other is used to remove data (dequeue).
Element is inserted from one end called the REAR(also called tail), and the removal
of existing element takes place from the other end called as FRONT(also called
head).
Queue follows First-In-First-Out methodology, i.e., the data item stored first will be
accessed first.

3. Basic features of Queue
1.Like stack, queue is also an ordered list of elements of similar data types.
2.Queue is a FIFO( First in First Out ) structure.
3.Once a new element is inserted into the Queue, all the elements inserted
before the new element in the queue must be removed, to remove the new
element.
4.peek( ) function is oftenly used to return the value of first element
without dequeuing it.

4. Basic Operations of Queue
•Enqueue: Add an element to the end of the queue
•Dequeue: Remove an element from the front of the queue
•IsEmpty: Check if the queue is empty
•IsFull: Check if the queue is full
•Peek: Get the value of the front of the queue without removing it

5. Applications of Queue Data Structure
•CPU scheduling, Disk Scheduling
•When data is transferred asynchronously between two processes.The
queue is used for synchronization. eg: IO Buffers, pipes, file IO, etc
•Handling of interrupts in real-time systems.
•Call Center phone systems use Queues to hold people calling them in
an order

6. Algorithm for ENQUEUE operation
•Step 1 − Check if the queue is full.
•Step 2 − If the queue is full, produce overflow error and exit.
•Step 3 − If the queue is not full, increment rear pointer to point the
next empty space.
•Step 4 − Add data element to the queue location, where the rear is
pointing.
•Step 5 − return success.

7. Case 1:
A B c D e
F RN
F=1 R=5 N=5
Step 1: FRONT=1 and REAR=N
F=1 1=1 true &
REAR = N 5=5true OR
FRONT=REAR+1FRONT=6
Print Overflow
 
Case 2:
Let us the queue
Front F=1 R=3 N=5 ITEM=D
A B c  
F R N
Step 1: FRONT=1 & REAR=N
FRONT=1  1=1 true &
REAR=N  3=5false OR
FRONT=REAR+11=4False
Step 2: FRONT=NULL FRONT=01=0false
Else if
REAR=N3=5false
Else
Set REAR=REAR+1REAR=3+1=4REAR=4
Step 3: QUEUE[REAR]= ITEM
QUEUE[4]=D
A B c D 
F R N
Step 4: Exit

8. Dequeue Operation
•Step 1 − Check if the queue is empty.
•Step 2 − If the queue is empty, produce underflow error and exit.
•Step 3 − If the queue is not empty, access the data where front is
pointing.
•Step 4 − Increment front pointer to point to the next available data
element.
•Step 5 − Return success.

9. A    
Case 1:
FR
N
FRONT=1 REAR=1 N=5
Step 1: FRONT=-11=-1False
Step 2: Element=Queue[FRONT]
Element=Queue[1] Element=A
ADeleted
Step 3: FRONT=REAR1=1true
FRONT=REAR=-1
    
Step 4: Return
Case 2:
FRONT=-1 REAR=-1 N=5
Step 1: FRONT=-1-1=-
1true
Print “UNDERFLOW” & Return.
F=1 N=5 R=4
Case 3:
A B c d 
F
RN
Step 1: FRONT=-1 1=-1false
Step 2: Element=Queue[FRONT]
Element= Queue[1]Element=A
A deleted
  B c d 
F
RN
Step 3: FRONT=REAR 1=4false
FRONT=FRONT+1FRONT=1+1=2
FRONT=2
  B c d 
F R N
Step 4: Return