ت
اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد�ﺔ اﻻﻟ��وﻧ�ﺔ
ت
اﻻﻟ��وﻧ�ﺔ اﻟﺠﺎﻣﻌﺔ اﻟﺴﻌﻮد�ﺔ
26/12/2021
1
College of Computing and Informatics
IT Program
IT245
Data Structure
2
IT245
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:
[Link]
3. Java Queue: [Link]
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: [Link]
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:
([Link]
24
Different Operations on Queue
• The following code shows the different operations on Queue:
([Link]
25
Different Operations on Queue
• The following code shows the different operations on Queue:
([Link]
simple/)
26
Different Operations on Queue
• The following code shows the
different operations on Queue:
([Link]
of-queue-simple/)
27
• Linked list implementation of Queue
28
Linked list implementation of Queue
package [Link].java2blog;
• Java Program to implement public class QueueUsingLinkedListMain
Queue using Linked List:
{
• ([Link] private Node front, rear;
queue-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);
• ([Link] }
queue-using-linked-list-in-java/)
//Remove item from the beginning of the list.
public int dequeue()
{
int data = [Link];
front = [Link];
if (isEmpty())
{
rear = null;
}
currentSize--;
[Link](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: {
• ([Link] Node oldRear = rear;
queue-using-linked-list-in-java/) rear = new Node();
[Link] = data;
[Link] = null;
if (isEmpty())
{
front = rear;
}
else
{
[Link] = rear;
}
currentSize++;
[Link](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 QueueUsingLinkedListMain();
• ([Link]
queue-using-linked-list-in-java/) [Link](6);
[Link]();
[Link](3);
[Link](99);
[Link](56);
[Link]();
[Link](43);
[Link]();
[Link](89);
[Link](77);
[Link]();
[Link](32);
[Link](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 [Link];
import [Link];
import [Link];
import [Link];
public class QueueClass {
public static void main(String[] args) {
Queue myQueue = new LinkedList();
// add elements in the queue using offer() - return true/false
[Link]("Monday");
[Link]("Thursday");
boolean flag = [Link]("Wednesday");
[Link]("Wednesday inserted successfully? "+flag);
// add more elements using add() - throws IllegalStateException
try {
[Link]("Thursday");
[Link]("Friday");
[Link]("Weekend");
} catch (IllegalStateException e) {
[Link]();
}
35
Applications of Queue
• Example for Adding Weekdays:
package [Link];
import [Link];
[Link]("Pick the head of the queue: " + [Link]());
import [Link];
import [Link];
String head = null;
try {
public class QueueClass { // remove head - remove()
head = [Link]();
public static void main(String[] args) { [Link]("1) Push out " + head + " from the queue ");
[Link]("and the new head is now: "+[Link]());
Queue myQueue = new LinkedList(); } catch (NoSuchElementException e) {
[Link]();
// add elements in the queue using offer() - return true/false }
[Link]("Monday");
[Link]("Thursday"); // remove the head - poll()
boolean flag = [Link]("Wednesday"); head = [Link]();
[Link]("2) Push out " + head + " from the queue");
[Link]("Wednesday inserted successfully? "+flag); [Link]("and the new head is now: "+[Link]());
// add more elements using add() - throws IllegalStateException // find out if the queue contains an object
try { [Link]("Does the queue contain 'Weekend'? " +
[Link]("Thursday"); [Link]("Weekend"));
[Link]("Friday"); [Link]("Does the queue contain 'Monday'? " + [Link]("Monday"));
[Link]("Weekend"); }
} catch (IllegalStateException e) {
[Link](); }
}
36
Applications of Queue
• Example for Adding Weekdays:
Reference: [Link]
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: [Link]
38
Applications of Queue
import [Link];
public class BinaryCounter {
public static void main(String[] args) {
private Queue<String> q;
[Link]("Count in binary to what decimal value?");
public void countTo(int n) {
Scanner scanner = new Scanner([Link]);
q = new QueueArray<String>();
int n = [Link]();
[Link]("1");
for (int i = 0; i < n; i++) { [Link]();
String front = [Link](); BinaryCounter binaryCounter = new BinaryCounter();
[Link](front); [Link](n);
[Link](front+"0"); }
[Link](front+"1"); }
}
39
References
1. Data structures and algorithm analysis in Java by Mark Allen Weiss
40
Thank You
41