CS 103 1 Queues • Definition of a Queue • Examples of Queues

 Page 1


CS 103 1 
Queues 
• Definition of a Queue  
• Examples of Queues 
• Design of a Queue Class  
• Different Implementations of the 
Queue Class 
Page 2


CS 103 1 
Queues 
• Definition of a Queue  
• Examples of Queues 
• Design of a Queue Class  
• Different Implementations of the 
Queue Class 
CS 103 2 
Definition of a Queue 
• A queue is a data structure that models/enforces 
the first-come first-serve order, or equivalently 
the first-in first-out (FIFO) order. 
• That is, the element that is inserted first into the 
queue will be the element that will deleted first, 
and the element that is inserted last is deleted last. 
• A waiting line is a good real-life example of a 
queue. (In fact, the Britich word for “line” is 
“queue”.) 
 
Page 3


CS 103 1 
Queues 
• Definition of a Queue  
• Examples of Queues 
• Design of a Queue Class  
• Different Implementations of the 
Queue Class 
CS 103 2 
Definition of a Queue 
• A queue is a data structure that models/enforces 
the first-come first-serve order, or equivalently 
the first-in first-out (FIFO) order. 
• That is, the element that is inserted first into the 
queue will be the element that will deleted first, 
and the element that is inserted last is deleted last. 
• A waiting line is a good real-life example of a 
queue. (In fact, the Britich word for “line” is 
“queue”.) 
 
CS 103 3 
A Graphic Model of a Queue 
 
 
 
 
Tail: 
All new items  
are added on  
this end 
      Head: 
All items are  
deleted from  
this end 
Page 4


CS 103 1 
Queues 
• Definition of a Queue  
• Examples of Queues 
• Design of a Queue Class  
• Different Implementations of the 
Queue Class 
CS 103 2 
Definition of a Queue 
• A queue is a data structure that models/enforces 
the first-come first-serve order, or equivalently 
the first-in first-out (FIFO) order. 
• That is, the element that is inserted first into the 
queue will be the element that will deleted first, 
and the element that is inserted last is deleted last. 
• A waiting line is a good real-life example of a 
queue. (In fact, the Britich word for “line” is 
“queue”.) 
 
CS 103 3 
A Graphic Model of a Queue 
 
 
 
 
Tail: 
All new items  
are added on  
this end 
      Head: 
All items are  
deleted from  
this end 
CS 103 4 
Operations on Queues 
• Insert(item): (also called enqueue) 
– It adds a new item to the tail of the queue 
• Remove( ):  (also called delete or dequeue) 
– It deletes the head item of the queue, and returns to the caller. If the queue 
is already empty, this operation returns NULL 
• getHead( ): 
– Returns the value in the head element of the queue 
• getTail( ): 
– Returns the value in the tail element of the queue 
• isEmpty( ) 
– Returns true if the queue has no items 
• size( ) 
– Returns the number of items in the queue 
Page 5


CS 103 1 
Queues 
• Definition of a Queue  
• Examples of Queues 
• Design of a Queue Class  
• Different Implementations of the 
Queue Class 
CS 103 2 
Definition of a Queue 
• A queue is a data structure that models/enforces 
the first-come first-serve order, or equivalently 
the first-in first-out (FIFO) order. 
• That is, the element that is inserted first into the 
queue will be the element that will deleted first, 
and the element that is inserted last is deleted last. 
• A waiting line is a good real-life example of a 
queue. (In fact, the Britich word for “line” is 
“queue”.) 
 
CS 103 3 
A Graphic Model of a Queue 
 
 
 
 
Tail: 
All new items  
are added on  
this end 
      Head: 
All items are  
deleted from  
this end 
CS 103 4 
Operations on Queues 
• Insert(item): (also called enqueue) 
– It adds a new item to the tail of the queue 
• Remove( ):  (also called delete or dequeue) 
– It deletes the head item of the queue, and returns to the caller. If the queue 
is already empty, this operation returns NULL 
• getHead( ): 
– Returns the value in the head element of the queue 
• getTail( ): 
– Returns the value in the tail element of the queue 
• isEmpty( ) 
– Returns true if the queue has no items 
• size( ) 
– Returns the number of items in the queue 
CS 103 5 
Examples of Queues 
• An electronic mailbox is a queue 
– The ordering is chronological (by arrival time) 
• A waiting line in a store, at a service 
counter, on a one-lane road 
• Equal-priority processes waiting to run on a 
processor in a computer system