際際滷

際際滷Share a Scribd company logo

Team 5

Download as PPT, PDF
Sathasivam Rangasamy
Sathasivam Rangasamy

A queue is a first-in, first-out (FIFO) data structure where elements are inserted at the rear of the queue and deleted from the front. Insertion is called enqueue and deletion is called dequeue. Real-world examples of queues include lines at checkout counters, call centers, and buffers that hold songs in an mp3 playlist. The key operations for a queue are enqueue, dequeue, isEmpty, isFull, and size.

1 of 11
Downloaded 11 times
IINNTTRROODDUUCCTTIIOONN:: A queue is an abstract data type in which all insertions are made at one end of the list known as rear or tail of the queue. All deletions are made at the other end known as front or head of the queue. An insertion of the queue is also referred to as enqueuing. The deletion operation is referred to as dequeuing.
This makes tthhee qquueeuuee aa FFiirrsstt--IInn--FFiirrsstt--OOuutt ((FFIIFFOO)) ddaattaa ssttrruuccttuurree.. Queue overflow results from trying to add an element onto a full queue. Queue underflow happens when trying to remove an element from an empty queue.
In a FIFO data structure, the first element added to the queue will be the first one to be removed. That is once a new element is added, all elements that were added before have to be removed in order to remove the new element. :
REAL-WORLD EXAMPLES: For example, in check-out lines, every time a customer finishes paying for their items that customer or the object leaves the queue from the front. This represents the dequeue function. Every time another object or customer enters the line to wait, they join the end of the line. This represent the enqueue function. The queue size function would return the length of the line. The empty function would return true only if there is no one in the line.
t The operations thhaatt wwee nneeeedd ttoo iimmpplleemmeenntt aa qquueeuuee aarree:: iinniitt aadddd rreemmoovvee iissFFuullll iissEEmmppttyy Enqueue (new-item: item-type): It adds an item onto the end of the queue.
ffrroonntt (( iitteemm)):: iitteemm--ttyyppee IItt rreettuurrnnss tthhee iitteemm aatt tthhee ffrroonntt ooff tthhee qquueeuuee.. dequeue (new-item: item-type): It removes the item from the front of the queue. is-empty ( item):Boolean True if no more items can be dequeued and there is no front item. is-full (item):Boolean True if no more items can be enqueued. get-size ( ):Integer It returns the number of elements in the queue.
Inserting an item into queue: Initially head and tail position is at zero. Add 42 to queue, again we use the tail pointer to point to the next element. Adding the further values 27, 52 and 99 to the queue.
Removing an item from queue: The first value to remove from the queue is 42. The remaining element is moved one position before it.
Pseudocode for the implementation of queue: Insertion: procedure insert(queue,rear,n,item) { if(rear==n) queue full else rear=rear+1; queue[rear]=item }
Deletion: Procedure delete(queue,front,rear,item) { if(front==rear) queue empty else item=queue[front] front=front+1 }
Applications of queue in real time: 1) Serving requests of a single shared resource (printer, disk, CPU). 2) Call centre phone systems will use a queue to hold people in line until a service representative is free. 3) Buffers on MP3 players and portable CD players, iPod playlist. Playlist for mp3 players add songs to the end, play from the front of the list.

More Related Content

Team 5

  • 1. IINNTTRROODDUUCCTTIIOONN:: A queue is an abstract data type in which all insertions are made at one end of the list known as rear or tail of the queue. All deletions are made at the other end known as front or head of the queue. An insertion of the queue is also referred to as enqueuing. The deletion operation is referred to as dequeuing.
  • 2. This makes tthhee qquueeuuee aa FFiirrsstt--IInn--FFiirrsstt--OOuutt ((FFIIFFOO)) ddaattaa ssttrruuccttuurree.. Queue overflow results from trying to add an element onto a full queue. Queue underflow happens when trying to remove an element from an empty queue.
  • 3. In a FIFO data structure, the first element added to the queue will be the first one to be removed. That is once a new element is added, all elements that were added before have to be removed in order to remove the new element. :
  • 4. REAL-WORLD EXAMPLES: For example, in check-out lines, every time a customer finishes paying for their items that customer or the object leaves the queue from the front. This represents the dequeue function. Every time another object or customer enters the line to wait, they join the end of the line. This represent the enqueue function. The queue size function would return the length of the line. The empty function would return true only if there is no one in the line.
  • 5. t The operations thhaatt wwee nneeeedd ttoo iimmpplleemmeenntt aa qquueeuuee aarree:: iinniitt aadddd rreemmoovvee iissFFuullll iissEEmmppttyy Enqueue (new-item: item-type): It adds an item onto the end of the queue.
  • 6. ffrroonntt (( iitteemm)):: iitteemm--ttyyppee IItt rreettuurrnnss tthhee iitteemm aatt tthhee ffrroonntt ooff tthhee qquueeuuee.. dequeue (new-item: item-type): It removes the item from the front of the queue. is-empty ( item):Boolean True if no more items can be dequeued and there is no front item. is-full (item):Boolean True if no more items can be enqueued. get-size ( ):Integer It returns the number of elements in the queue.
  • 7. Inserting an item into queue: Initially head and tail position is at zero. Add 42 to queue, again we use the tail pointer to point to the next element. Adding the further values 27, 52 and 99 to the queue.
  • 8. Removing an item from queue: The first value to remove from the queue is 42. The remaining element is moved one position before it.
  • 9. Pseudocode for the implementation of queue: Insertion: procedure insert(queue,rear,n,item) { if(rear==n) queue full else rear=rear+1; queue[rear]=item }
  • 10. Deletion: Procedure delete(queue,front,rear,item) { if(front==rear) queue empty else item=queue[front] front=front+1 }
  • 11. Applications of queue in real time: 1) Serving requests of a single shared resource (printer, disk, CPU). 2) Call centre phone systems will use a queue to hold people in line until a service representative is free. 3) Buffers on MP3 players and portable CD players, iPod playlist. Playlist for mp3 players add songs to the end, play from the front of the list.