Faculty of Information Technology - Computer Science Department 1
Data Structures
Faculty of Information Technology - Computer Science Department 2
Chapter 3
Queue Data Structure using Array
Faculty of Information Technology - Computer Science Department 3
Outline
Queue Specifications Structure
Queue Methods Using Array
Methods Implementation
Faculty of Information Technology - Computer Science Department 4
Queue Specifications Structure
• A queue is an ordered list (According to the arrival time) where insertions are made at
one end (the rear) and deletions are made at the other end (the front).
• Front (head): the first (oldest) entry in the queue.
• Rear (tail): the last entry in the queue. That is the most recent entry.
Front of Queue Rare of Queue
Faculty of Information Technology - Computer Science Department 5
Queue Property
A Queue is a First-In-First-Out (FIFO) data structure:
The first item inserted into a queue is the first to be served (serving implies removing
the item from the queue).
A queue is a dynamic object: It expands and shrinks with each insertion (append) and
deletion (serve).
Faculty of Information Technology - Computer Science Department 6
ADT Definition for Queue
1. Objects:
A finite ordered list with zero or more elements.
front (head) indicator indicates the first (oldest) entry in the queue.
rear (tail) indicator indicates the last (most recent) entry in the queue.
2. Methods (operations) implemented using Array:
isEmpty(): Check if the queue is empty.
isFull(): Check if the queue is full.
enqueue(): Add (store) an item to the queue.
dequeue(): Remove (access) an item from the queue.
length(): Retrieve the number of elements in the queue.
first(): Returns the element at the front of the queue but does not remove
it.
Faculty of Information Technology - Computer Science Department 7
How to Hold Queue Elements?
•We have two design options for how to hold the queue elements in the array:
Fixed front design: The front indicator of the queue is fixed while the
rare
indicator changes.
Floating front design: Both front and rear indicators change and the array
is treated as a circular structure.
Faculty of Information Technology - Computer Science Department 8
Fixed-Front Design
•In this approach, the front of the queue is
fixed and always in index 0. Only the rear
is changed.
•Assume we call enqueue( ) with
arguments ‘A’, ‘B’, ‘C’, and ‘D’ as
shown in the first queue. front =0, rear =
3.
•When we call dequeue( ) to remove the
front element we need to move every
element in the queue up one slot (Shift)
•This dequeue operation is inefficient, so Source: textbook
we do not use this approach.
Faculty of Information Technology - Computer Science Department 9
Floating-Front Design
This approach allows both the front and the
rear to move.
For a dequeue(), we remove the element at
the front and adjust the location of the front.
No movement of elements is required.
We have to keep track of the array indexes of
both the front and the rear of the queue.
Faculty of Information Technology - Computer Science Department 10
Methods Implementation
11
Faculty of Information Technology - Computer Science Department
Exercises
1. For the 𝑄𝑢𝑒𝑢𝑒𝐴𝑟𝑟 class, add the implementation of both methods
𝑙𝑒𝑛𝑔𝑡ℎ() and
𝑓𝑖𝑟𝑠𝑡().
𝑄𝑢𝑒𝑢𝑒𝐴𝑟𝑟
2. In the main class (𝑄𝑢𝑒𝑢𝑒𝐴𝑟𝑟𝐷𝑒𝑚𝑜), create a queue object using
class and test all its methods.
12
Faculty of Information Technology - Computer Science Department
