‫الجامعة السعودية االلكترونية‬

‫الجامعة السعودية االلكترونية‬

‫‪26/12/2021‬‬
‫‪1‬‬
College of Computing and
Informatics
Data Structure

2
Data Structure
Module 5
Queue

3
 1. Queue Model
2. Array implementation of Queue
3. Different Operations on Queue
4. Linked list implementation of Queue
5. Applications of Queue

Contents

4
 1. Understand Queue Abstract Data Type Model

2. Array Implementation of Queues

3. Recognize some applications adopt queue data structure

Weekly
Learning
Outcomes

5
Required Reading
1. Chapter 3 (Data structures and algorithm
analysis in Java by Mark Allen Weiss)
Recommended Reading
1. Chapter 10 (al, Cormen Thomas H et. Introduction to
Algorithms. Cambridge, MA: MIT Press, 2009)
2. Queue Class:
https://docs.oracle.com/javase/7/docs/api/java/util/Queue.h
tml
3. Java Queue: 6
• Queue Model

7
Queue Model

• Stacks are Last In First Out

• Queues are First In First Out

• first-come first-served

• Operations: enqueue and dequeue

8
Queue Model

• The basic operations on a queue are:

• Enqueue
• Which inserts an element at the end of the list (called the rear)
• Dequeue
• Which deletes (and returns) the element at the start of the list (known as the front).

9
Queue Model

Reference: https://www.geeksforgeeks.org/queue-data-structure/

10
• Array implementation of Queue

11
Array implementation of Queue

Any list implementation is legal for queues.

Like stacks, both the linked list and array implementations give fast O(1) running
times for every operation.

The linked list implementation is straightforward, we will cover it at next section.

In the following slides we will discuss the Array implementation of Queue

12
Array implementation of Queue

• Create the Array

• Keep the positions front and back, which represent the ends of the
queue.
• Keep track of the number of elements that are actually in the queue,
currentSize.

13
Array implementation of Queue

• The operations should be clear.

• To enqueue an element x,
• we increment currentSize and back,
• then set theArray[back]=x.
• To dequeue an element,
• we set the return value to theArray[front],
• decrement currentSize,
• and then increment front.

14
Array implementation of Queue

After 10 enqueues, the queue appears to be full,

since back is now at the last array index, and the next enqueue would be in a nonexistent position.

The simple solution is that whenever front or back gets to the end of the array,
it is wrapped around to the beginning.

This is known as a circular array implementation.

15
Array implementation of Queue

• Circular array:

• Don't shift after removing from array list

• Keep track of start and end of queue

• When run out of space, wrap around; modular arithmetic

• When array is full, increase size using list tactic

16
Array implementation of Queue

17
Array implementation of Queue

18
Array implementation of Queue

19
Array implementation of Queue

20
Array implementation of Queue

Reference: Chapter 10 (al, Cormen Thomas H et. Introduction to Algorithms. Cambridge, MA: MIT Press, 2009)

21
Array implementation of Queue

• Simple Algorithm:

Reference: Chapter 10 (al, Cormen Thomas H et. Introduction to Algorithms. Cambridge, MA: MIT Press, 2009)

22
• Different Operations on Queue

23
Different Operations on Queue

• The following code shows the different operations on Queue:

(https://www.geeksforgeeks.org/array-implementation-of-queue-simple/)

24
Different Operations on Queue
• The following code shows the different operations on Queue:
(https://www.geeksforgeeks.org/array-implementation-of-queue-simple/)

25
Different Operations on Queue

• The following code shows the different operations on Queue:

(
https://www.geeksforgeeks.org/array-implementation-of-queue-simple
/
)

26
Different Operations on Queue

• The following code shows the

different operations on Queue:
(
https://www.geeksforgeeks.org/array-implementation-of-
queue-simple/
)

27
• Linked list implementation of Queue

28
 Linked list implementation of Queue
package org.arpit.java2blog;
• Java Program to implement public class QueueUsingLinkedListMain
Queue using Linked List:
{
• ( private Node front, rear;
https://java2blog.com/implement-q
ueue-using-linked-list-in-java/ private int currentSize; // number of items
) //class to define linked node
private class Node
{
int data;
Node next;
}
//Zero argument constructor
public QueueUsingLinkedListMain()
{
front = null;
rear = null;
currentSize = 0;
}
29
 Linked list implementation of Queue
public boolean isEmpty()
• Java Program to implement {
Queue using Linked List: return (currentSize == 0);
• ( }
https://java2blog.com/implement-q
ueue-using-linked-list-in-java/ //Remove item from the beginning of the list.
) public int dequeue()
{
int data = front.data;
front = front.next;
if (isEmpty())
{
rear = null;
}
currentSize--;
System.out.println(data+ " removed from the queue");
return data;
}
30
 Linked list implementation of Queue
//Add data to the end of the list.
• Java Program to implement public void enqueue(int data)
Queue using Linked List: {

• ( Node oldRear = rear;

https://java2blog.com/implement-q rear = new Node();
ueue-using-linked-list-in-java/
) rear.data = data;
rear.next = null;
if (isEmpty())
{
front = rear;
}
else
{
oldRear.next = rear;
}
currentSize++;
System.out.println(data+ " added to the queue");
}

31
 Linked list implementation of Queue

• Java Program to implement

Queue using Linked List: public static void main(String a[]){
QueueUsingLinkedListMain queue = new QueueUsingLinkedList-
• (
Main();
https://java2blog.com/implement-q
ueue-using-linked-list-in-java/ queue.enqueue(6);
) queue.dequeue();
queue.enqueue(3);
queue.enqueue(99);
queue.enqueue(56);
queue.dequeue();
queue.enqueue(43);
queue.dequeue();
queue.enqueue(89);
queue.enqueue(77);
queue.dequeue();
queue.enqueue(32);
queue.enqueue(232);
}
32
• Applications of Queue

33
Applications of Queue

When jobs are submitted to a printer, they are arranged in order of

arrival. Thus, essentially, jobs sent to a line printer are placed on a queue

Virtually every real-life line is (supposed to be) a queue. For instance,

lines at ticket counters are queues, because service is first-come first-
served.

Calls to large companies are generally placed on a queue when all

operators are busy.

34
Applications of Queue

• Example for Adding Weekdays:

package com.javacodegeeks.core.queue;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

public class QueueClass {

public static void main(String[] args) {

Queue myQueue = new LinkedList();

// add elements in the queue using offer() - return true/false

myQueue.offer("Monday");
myQueue.offer("Thursday");
boolean flag = myQueue.offer("Wednesday");

System.out.println("Wednesday inserted successfully? "+flag);

// add more elements using add() - throws IllegalStateException

try {
myQueue.add("Thursday");
myQueue.add("Friday");
myQueue.add("Weekend");
} catch (IllegalStateException e) {
e.printStackTrace();
}
35
Applications of Queue

• Example for Adding Weekdays:

package com.javacodegeeks.core.queue;
import java.util.LinkedList; System.out.println("Pick the head of the queue: " + myQueue.peek());
import java.util.NoSuchElementException;
import java.util.Queue; String head = null;
try {
public class QueueClass { // remove head - remove()
head = myQueue.remove();
public static void main(String[] args) { System.out.print("1) Push out " + head + " from the queue ");
System.out.println("and the new head is now: "+myQueue.element());
Queue myQueue = new LinkedList(); } catch (NoSuchElementException e) {
e.printStackTrace();
}
// add elements in the queue using offer() - return true/false
myQueue.offer("Monday");
myQueue.offer("Thursday"); // remove the head - poll()
head = myQueue.poll();
boolean flag = myQueue.offer("Wednesday");
System.out.print("2) Push out " + head + " from the queue");
System.out.println("and the new head is now: "+myQueue.peek());
System.out.println("Wednesday inserted successfully? "+flag);
// find out if the queue contains an object
// add more elements using add() - throws IllegalStateException
System.out.println("Does the queue contain 'Weekend'? " +
try {
myQueue.contains("Weekend"));
myQueue.add("Thursday");
System.out.println("Does the queue contain 'Monday'? " +
myQueue.add("Friday");
myQueue.add("Weekend"); myQueue.contains("Monday"));
}
} catch (IllegalStateException e) {
e.printStackTrace();
} }
36
Applications of Queue

• Example for Adding Weekdays:

Reference: https://examples.javacodegeeks.com/java-queue-example/

37
Applications of Queue

• Write a class BinaryCounter:

• that prompts the user for a value n,
• and then uses a queue to generate and print all binary numbers with decimal
values from 1 to n,
• in a manner similar to the sample run shown below.
• Use the QueueArray implementation.

Reference: http://math.oxford.emory.edu/site/cs171/probSetUsingQueues/
38
 Applications of Queue
import java.util.Scanner;
public class BinaryCounter {
public static void main(String[] args) {
private Queue<String> q;
System.out.println("Count in binary to what decimal value?");
public void countTo(int n) {
Scanner scanner = new Scanner(System.in);
q = new QueueArray<String>();
q.enqueue("1"); int n = scanner.nextInt();

for (int i = 0; i < n; i++) { scanner.close();

String front = q.dequeue(); BinaryCounter binaryCounter = new BinaryCounter();

System.out.println(front); binaryCounter.countTo(n);
q.enqueue(front+"0"); }
q.enqueue(front+"1"); }
}

39
References

1. Data structures and algorithm analysis in Java by Mark Allen Weiss

40
Thank
You

41