10-12-2012, 05:17 PM
Queues
Queues.doc (Size: 64.5 KB / Downloads: 23)
DEFINITION:
• A queue is a list from which items are deleted from one end (front) and into which items are inserted at the other end (rear, or back)
– It is like line of people waiting to purchase tickets:
• It is referred to as a first-in-first-out (FIFO) data structure.
• Queues have many applications in computer systems:
– Any application where a group of items is waiting to use a shared resource will use a queue. e.g.
• jobs in a single processor computer
• print spooling
• Information packets in computer networks
Basic Operations
• enqueue: insertion at the back of the line
• dequeue: removal of the item from the front of the line.
• getFront: access of the item at the front of the line.
(historically, dequeue and getFront have been combined into one operation)
Circular Array Implementation
• The front and back are the same as the basic model, except: The queue wraps around when the end of the array is reached.
• We need to double the array only when the number of items in the queue is equal to the number of array positions.