Queue Data Structure

Another basic data structure is the Queue.Queue is a container of the objects that are inserted and removed according to the first in first out principle(FIFO).That is, elements can be inserted at ant time,but only the element that has been in the queue the longest can be removed at any time.We usually say that elements enter the queue at the rear(r) and are removed from the front(f).

Queue ADT (abstract data type):

 In Queue element access and deletion are restricted to the first element which is called the front of the Queue and element insertion is restricted to the end of the sequence, which is called the rear of the Queue.

Queue ADT

• enqueue(O):Insert Object ) at the rear of the Queue
• dequeue():Remove and return Object at the front .
• size():return the number of Objects in the queue.
• isEmpty();return true if Queue is empty.
• front():return front Object int the Queue but do not remove.
• Conditions for Array Based Implementation of queue :

 Conditions for Array Based Implementation of queue :

Let us assume size of Queue is N, f is an index to the cell of Q storing the first element of th queue(which is the next candidate to be removed by a dequeue operation) and r is an index to the next available array cell in the Q.

• enqueue(O)
• dequeue()
• size()
• isEmpty()
• front()

• f=r=N Indicates Queue is full
• f=r=0 Indicates Queue is empty
• No condition
• f=r=0 Indicates Queue is empty
• check whether Queue is empty or not.

Implementation of Circular Queue:

Implementing circular Queue is pretty easy.Each time we increment f or r , we simply compute his increment as (f+1)%N or (r+1)%N .size of the queue can be calculated by the means of expression (N-f+r)%N.

In 'C' we don't have certain API to use, so we need to go for implementation but in java we have Queue class.(java.util.Queue)

java.util.Queue API

public interface java.util.Queue extends java.util.Collection {
  public abstract boolean add(E);
  public abstract boolean offer(E);
  public abstract E remove();
  public abstract E poll();
  public abstract E element();
  public abstract E peek();
}

Real Time Applications

• Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox - add songs to the end, play from the front of the list
• call center phone systems will use a queue to hold people in line until a service representative is free.
• When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
• Os utilize a Queue to allocate CPU time to the runnable threads in the round-robin protocal.Main idea of round robin protocal is to store all runable thread in a Queue.

you may also like

• Stack Data Structure.
•  Snake game in c.
• Creating A Basic Notepad Application.

Stay Connected...!
write your opinion....!

10:55