Queue Data Structure

Queue Data Structure

 

Queue data structure is a linear data structure in which addition and deletion takes place at dofferent ends as a Rear and Front end respectively.The end at which new elements added is called rear. And from which elements are deleted is called the front. A queue is a collection of items organized in a structure with the First-In-First-Out property.

 

 

 

Basic Operations of Queue

 

• Enqueue: Insert element at end of queue.
• Dequeue: Delete the first element at the enc of queue.
• IsEmpty: Returns true if and only if queue is empty
• IsFull: Return true  if the queue is full
• Peek: Return the value of the front of the queue without removing the element

 

Enqueue Operation

We can use the following steps to insert an element into queue.

• Step 1 − Check whether the queue is full(rear==SIZE-1)
• Step 2 − If the queue is full,then display “Queue is Full Insertion is not possible” and terminate the function.
• Step 3 − If the queue is not full, ithen ncrement rear value by one (rear++)and set queue[rear]=value

Algorithm for enqueue operation

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Dequeue Operation

• Step 1 − Check whether the queue is empty.(front==rear)
• Step 2 − If the queue is empty, then display “Queue is Empty.Deletion is not possible” and terminate the function.
• Step 3 − If the queue is not empty, then increment the front value by one(front++).then display queue[front]as deleted element.Then check whether both front and rear are equal(front==rear), if it True, then set both front and rear to “-1″(front=rear=-1)

 

Algorithm for dequeue operation

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

 

Complexity of Queue

 

Data Structure	Time Complexity								Space Compleity
	Average				Worst				Worst
	Access	Find(search)	Insertion	Deletion	Access	Search	Insertion	Deletion
Queue	θ(n)	θ(n)	θ(1)	θ(1)	O(n)	O(n)	O(1)	O(1)	O(n)

Applications of Queue

• Queues are frequently used in operating system and networking software modules.
• Job-Scheduling
• Processor queue
• Network router queues of outgoing packets,etc.
• Simulate retail or bank operations such as withdrawing cash from an ATM machine.

 

 

Read more, Stack Data Structure