[go: up one dir, main page]
Scribd
Upload
7 views8 pages

2.1 Queue

lecture note of CSC508 data structure

Uploaded by

2023217748
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views8 pages

2.1 Queue

lecture note of CSC508 data structure

Uploaded by

2023217748
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

QUEUE

Topic 2 Queue

Prepared by: Nik Marsyahariani Nik Daud

Content

• Introduction to Queue
• Queue Interface in Collection Framework
• Queue Implementation
• Queue Application

• Circular Queue
• Priority Queue

2
Introduction To Queues

▪ A linear data structure where the elements are stored in sequence.

▪ 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.

▪ First In First Out (FIFO) data structure.

Examples Of Queues

Front/First Back/Rear

▪ Customers at a bank counter

▪ Cars waiting to pay toll

▪ Job Scheduling for CPU


processing

4
Queue in Java Collection Framework

▪ The Queue interface follows:


public interface Queue<E> extends Collection<E>{
E element();
E add(E e);
E peek();
E poll();
E remove();
}

▪ Besides basic Collection operations, queues provide additional


insertion, removal, and inspection operations.

Queue Interface in Java Collection Framework

6
Queue Implementation

• Inherits methods from linkedlist class or arraylist class but with more
restrictions that are consistent with queue concept.
• Queue properties:
• Front node
• Rear node
FRONT REAR

20 13 8

Queue Operations

▪ isEmpty : Determines whether the queue is empty. If the queue is


empty, it returns the value true; otherwise, it returns the value false.
▪ front : Returns the front (first) element of the queue; the queue
must exist.
▪ back : Returns the rear (last) element of the queue; the queue
must exist.
▪ enqueue : Adds a new element to the rear of the queue; the
queue must exist and must not be full.
▪ dequeue : Removes the front element of the queue; the queue must
exist and must not be empty.

8
Java Implementation

public class Queue{


node front,rear;
int size;
public Queue(){
front = rear = null; size =0;}
public boolean isEmpty(){
if(size == 0)return true; else return false;}
public void enqueue(Object obj){
if(isEmpty())
front = rear = new node(obj);
else{
rear.next = new node(obj);
rear = rear.next;
}
size++;
}

Java Implementation

public Object dequeue()


//remove object from beginning of the queue

public Object getFirst()


//get Object data at the beginning of the queue

public Object getLast()


//get Object data from the end of the queue
}

10
Queue Application (Primitive Data Type)

public class testQueueInt


{
public static void main(String [] a){
Queue queueInt = new Queue();

for(int i = 1;i<4;i++){
queueInt.enqueue(i*10);
}
while(!queueInt.isEmpty())
System.out.print(Integer.parseInt(queueInt.dequeue().toString())
);

}}

13

Queue Application (Abstract Data Type)

import java.util.Scanner; while(!queueCar.isEmpty()){


c = (Car) queueCar.dequeue();
System.out.println(c.toString());
public class testQueueCar{ }
public static void main(String[] a){
Scanner sc = new Scanner(System.in);
Queue queueCar = new Queue();
String model;double price; Car c;

for(int i=0;i<2;i++){
model = sc.next();
price = sc.nextDouble();
c = new Car(price,model);
queueCar.enqueue(c);
}

14
Circular Queue Concept

• Circular queue is an extended queue where the last node of the queue is
connected to the first node in the queue.
• Also known as ring buffer
• With queue, once the queue is full, data cannot be added even if there is a
space in front of the queue.
• This occurs especially when the queue is implemented using array or
arraylist.
• Circular queue allows for flexible movement of front and rear node.

16

Circular Queue
FRONT REAR

20 13 8

FRONT REAR

New node?
20 13 8 56
33

REAR FRONT

33 20 13 8 56

CIRCULAR QUEUE

17
Priority Queue

▪ FIFO rules of a queue are relaxed.


▪ In hospital, patients with severe symptoms are treated first.

▪ Customers or jobs with higher priority are pushed to front of queue

▪ Restrictions during data insertion where data value if checked to see its
priority.

▪ Removal of data is always at the top of the queue.

▪ To implement:
▪ use an ordinary linked list, which keeps the items in order from the
highest to lowest priority
▪ use a treelike structure

18

Summary

• Introduction to Queue
• Queue Interface in Collection Framework
• Queue Implementation
• Queue Application

• Circular Queue
• Priority Queue

19

You might also like