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

# 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
this end
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
this end
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
– 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
this end
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
– 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