Chapter 3 - QUEUE
Definition of Queue
Specifications for Queue
Implementations of Queue
Linked Queue
Contiguous Queue
Applications of Queue
1
Linear List Concepts
FIFO
(Queue)
2
Queue - FIFO data structure
• Queues are one of the most common of all data-processing
structures.
• Queues are used where someone must wait one's turn before
having access to something.
• Queues are used in every operating system and network:
processing system services and resource supply: printer, disk
storage, use of the CPU,...
• Queues are used in business online applications: processing
customer requests, jobs, and orders.
3
Queue ADT
DEFINITION: A Queue of elements of type T is a finite
sequence of elements of T, in which data can be
inserted only at one end, called the rear, and deleted
from the other end, called the front.
Queue is a First In - First Out (FIFO) data structure.
Basic operations:
• Construct a Queue, leaving it empty.

Basic operation of Queue
(QueueFront)
Before After
QueueFront
(Queue
remains
unchanged)
a) Successful operation: function returns success
b) Unsuccessful operation: function returns underflow
rear front rear front
QueueFront
X
Received data:
Queue remains
unchanged
X
7
Basic operation of Queue
(QueueRear)
Before After
QueueRear
(Queue
remains
unchanged)
a) Successful operation: function returns success
b) Unsuccessful operation: function returns underflow
rear front rear front
QueueRear
X
Received data:

Built Queue ADT
Queue may be fully inhirited from a List, inside its
operations calling List’s operations.
Similar for other operations of Queue…
<ErrorCode> EnQueue (val DataIn <DataType>)
Call List::InsertTail(DataIn)
or
Call List::Insert(DataIn, Size()) // insert after last lement
end EnQueue
<ErrorCode> DeQueue (val DataOut <DataType>)
Call List::RemoveHead(DataOut)
or
Call List::Remove(DataOut, 0) // remove element from the 1
st
position
end EnQueue
11
Implementations of Queue
Contiguous Implementation.
Linked Implementation.
12
Linked Queue
Node
Data <DataType>
link <pointer>
end Node
Queue
front <pointer>
rear <pointer>
count <integer>

2. rear = NULL
3. count = 0
4. Return
end Create
15
EnQueue
Before:
After:
pNew
pNew->data = DataIn
pNew->link = NULL
rear->link = pNew
rear = pNew
count = count + 1
4
count
front
rear
5
count
front
rear
16
EnQueue (cont.)
Before:
After:
0
Count
front
rear

After:
0
Count
front
rear
1
Count
front
rear
pDel
pDel= front
front = NULL
rear = NULL
recycle pDel
count = count - 1
pDel
19
EnQueue & DeQueue Algorithm
 EnQueue is successful when queue is not full.
 DeQueue successful when queue is not empty.
 Regular cases:
o EnQueue: only rear must be updated (points to new
element).
o DeQueue: only front must be updated (points to next
element if exists).
 Irregular cases:
o EnQueue an element to an empty queue: both rear
and front must be updated (point to new element).
o DeQueue a queue having only one element: both rear
and front must be updated (receive NULL value).