CHAPTER 4

QUEUE
FUNDAMENTALS OF DATA STRUCTURES (CSC248)

PREPARED BY:
MISS MAZNIE MANAF
WHAT IS QUEUE DATA STRUCTURE?

Definition: data structure in which the elements are added at one end, called the
rear, and deleted from the other end, called the front or first

Queue is referred as FIFO (First In First Out) data structure.
USAGE OF QUEUE DATA STRUCTURE

Computer with single processor

only one applications can be serviced at a time, each application requires processor
time to be placed in a queue.

Support spooling in printing

single printer shared by all users in a network, each printing job are placed in a queue
until printer becomes available.

Information packets in computer networks

routing nodes send one packet at a time and must be in queue

File server in a computer network

file access / request from clients are placed in a queue.
QUEUE IMPLEMENTATION

Queue uses Linked list class definition, but with constraint usage where the
element is inserted at the back of the list and remove from front of the list.

Basic operations of Queue :-

enqueue (enQ) – adds new element to the end of queue.

dequeue (deQ) – removes element from front of queue and returns the data from the
removed node.

isEmpty – checks whether the queue is empty or not.
QUEUES CONCEPTS

Figure 1: Illustration of Reality Queues

 QUEUES CONCEPTS CONTINUE

front

Raju Vivian
Budin Limah

enqueue
Caca

What happen if you apply dequeue in this queue?

Figure 2: Illustration of Queue concept
(FIFO)
QUEUE ADT: REQUIREMENTS

Requirements:
1. It must be possible to make a queue empty.
2. It must be possible to test whether a queue is empty.
3. It must be possible to add an element at the rear of a queue.
4. It must be possible to remove the front element from a queue.
5. It must be possible to access the front/end element in a queue without
removing it.
QUEUE ADT: BASIC METHODS

Primary methods:
1. enqueue – add new item at the back
2. dequeue – delete item from the front

Other methods:
1. getFront – to get data at the front
2. getEnd – to get data at the back
3. isEmpty – to check if the queue is empty
QUEUE ADT: OPERATIONS

1. Create a queue
2. Test whether the queue is empty (isEmpty)
3. Enqueue (add) an element at the end of the queue, provided the queue is not
full
4. Dequeue (remove) an element from the front of the queue, provided the queue
is not empty
5. Retrieve the value of the element at the front of the queue (getFront), provided
the queue is not empty
IMPLEMENTATION QUEUE AS ARRAY

A queue is a first in, first out (FIFO) data structure

This is accomplished by inserting at one end (the rear) and
deleting from the other (the front)

0 1 2 3 4 5 6 7
myQueue:
17 23 97 44

front = 0 rear = 3

To insert: put new element in location 4, and set rear to 4

To delete: take element from location 0, and set front to 1
IMPLEMENTATION QUEUE AS ARRAY CONTINUE
front = 0 rear = 3

Initial queue: 17 23 97 44

After insertion: 17 23 97 44 333

After deletion: 23 97 44 333

front = 1 rear = 4

Notice how the array contents “crawl” to the right as elements are inserted and
deleted

This will be a PROBLEM after a while!
IMPLEMENTATION QUEUE AS LINKED LIST

Node to be
last enqueued
first

44 97 23 17

To enqueue (add) a node:

Find the current last node
Change it to point to the new last node
Change the last pointer in the list header
IMPLEMENTATION QUEUE AS LINKED LIST CONTINUE

last
first

44 97 23 17

To dequeue (remove) a node:

Copy the pointer from the first node into the header
QUEUE CLASS DEFINITION

Class : Queue extends LinkedList class

Methods :
Constructor (default)
enqueue (object) // insert element at the end of queue
dequeue () // remove element from front of queue
getFront () // get the front element
getEnd () // get the end element
isEmpty() // check if queue is Empty (inherit from class LinkedList
QUEUE CLASS DEFINITION CONTINUE
public class Queue extends LinkedList
{
public Queue() { } // constructor
public void enqueue( Object elem)
{ insertAtBack (elem); }

public Object dequeue ( )

{ return removeFromFront(); }

public Object getFront()

{ return getFirst(); }

public Object getEnd()

{ Object O = removeFromBack();
insertAtBack(O);
return O;
}
} // end Queue
QUEUE APPLICATION

Searching – search a particular element in queue (check and get the elements
(using dequeue method).

Manipulating – do some operation on Queue

(Example : calculate average, determine maximum & minimum and etc.)

Important thing about application using queue is that queue must be dequeue
(remove data) in order to traverse the queue

It is important to keep removed data from queue into temporary queue if the
data need to be used again

In queue, the order of the data will not change after and inserting process using
temporary queue
EXERCISE 1

Trace the output of above program.

public class Test {
public static void main(String[] args) {
Queue q1 = new Queue();
q1.enqueue("We");
q1.enqueue("So");
q1.enqueue("Are");
q1.enqueue("Happy");
q1.enqueue("How About You?");
System.out.println(q1.dequeue());
q1.dequeue();
while (!q1.isEmpty())
System.out.println(q1.dequeue());
q1.enqueue("Me too");
System.out.println(q1.dequeue());
}}
EXERCISE 2

Write a Java application to

Create a Queue object named as qNumber

Input ten (10) integer numbers and store them into qNumber

Display the first and last element in the queue object

Check whether queue object has no element and display the size of queue object

Calculate and display sum of all number in the queue object