Queue Data Structures Lecture Notes PDF

CS201 Data Structures and Algorithm Design Lecture 8 – Week 9 Queues ADT Faculty of Computers Science & Artificial Intelligence  Lecture’s Contents Queues ADT. Queues Operations: 1) Enqueue 2) Dequeue Types of Queue. Implementing a...

CS201 Data Structures and Algorithm Design Lecture 8 – Week 9 Queues ADT Faculty of Computers Science & Artificial Intelligence  Lecture’s Contents Queues ADT. Queues Operations: 1) Enqueue 2) Dequeue Types of Queue. Implementing a Queue:  Using Python List.  Using a linked list Removing Element – Dequeue. Exercises Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 2  Queues Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 3  Queues (buffers) ADT A queue is defined as a linear data structure of ordered items that is open at both ends and the operations are performed in First In First Out (FIFO) order. Items in the queue can be inserted only at one end and removed at the other end. Insertion is done at rear (the tail or end) Deletion is done at the other end called the front (the head). Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 4  Queues Operations Queue operations include:- 1) Enqueue:- Add an item to the queue at the end (Rear) 2) Dequeue:- Remove an item from the front of the queue (Head) These operations are also called insert and getFront in order to simplify things. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 5  Types of Queue Types of queue include:- Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 6  Implementing a Queue Just like a stack, we can implement a queue in two ways:  Using an array.  Using a linked list. Using an array to implement a queue is significantly harder than using an array to implement a stack. Why? Unlike a stack, where we add and remove at the same end, in a queue we add to one end and remove from the other. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 7  Queue – Array based Example (Queue of char). Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 8  Example 1 – Simple Queue Example queue of size 4. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 9  Example 2 – Simple Queue Suppose we have a queue of size 6, do the following operations:  Enqueue ( 2), (10), ( - 1 )  Dequeue (2)  Enqueue (0), (1), (5) Initially a queue is empty  Rear = Front = - 1 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 10  Simple Queue Disadvantages Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 11  Simple Queue Disadvantages 66 can’t be added to the queue as the rear reached the max size of the queue  rear = size -1. This drawback can be treated using circular queue. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 12  Queue -Basic Operations Creates an empty queue. Adding or storing an element at the rear of queue. Deleting or removing an element from the front of queue. Get the element at the front of the queue. Checks if the queue is empty. Checks if the queue is full. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 13  Queue -Basic List Operations Operations associated with queue using List are:  Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity : O(1)  Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity : O(1) Python Queue can be implemented by the following ways:  List  Using Queue module Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 14  Implementing a Queue using List A queue can be implemented using python list, where we can use the append() and pop() methods to add and remove elements. However, lists are quite slow for this purpose because inserting or deleting an element at the beginning requires shifting all of the other elements by one, requiring O(n) time.. queue = [] Initial queue queue.append('a') ['a', 'b', 'c', 10, 50] queue.append('b') queue.append('c') queue.append(10) Elements dequeued from queue queue.append(50) a print("Initial queue") b print(queue) c print("\nElements dequeued from queue") print(queue.pop(0)) Queue after removing elements print(queue.pop(0)) [10, 50] print(queue.pop(0)) print("\nQueue after removing elements") print(queue) Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 15  Implementing a Queue using Queue Queue is built-in module of Python, which is used to implement a queue, queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. This Queue follows FIFO rule. There are various functions available in this module such as:  Maxsize :- Number of items allowed in the queue.  empty() :- Return True if the queue is empty, False otherwise.  full() :- Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (means a infinite queue), then full() never returns True.  get() :- Remove and return an item from the queue. If queue is empty, wait until an item is available.  put(item) :- Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.  qsize() :- Return the number of items in the queue. Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 16  Implementing a Queue using Queue from queue import Queue This following code q = Queue(maxsize = 3) Current Queue Size= 0 utilizes the Queue class print("Current Queue Size=",q.qsize()) Current Queue Size= 3 from the queue module. q.put(10) q.put(20) Is Queue Full: True q.put(30) print("Current Queue Size=",q.qsize()) Elements dequeued from the queue print("\nIs Queue Full: ", q.full()) 10 print("\nElements dequeued from the queue") 20 print(q.get()) 30 print(q.get()) print(q.get()) Empty: True print("\nEmpty: ", q.empty()) q.put(50) Is Queue Empty: False print("\nIs Queue Empty: ", q.empty()) Is Queue Full: False print("Is Queue Full: ", q.full()) Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 17  Implementing a Queue using List A queue can be implemented using python list, where we can use the append() and pop() methods to add and remove elements. There is no insertion as data elements are always added at the end of the queue. def show(self): class Queue: print("Queue Contents : ", self.q) def __init__(self): print("Queue Size= ", len(self.q)) self.q = [] # list() print("Queue Front= ", self.f) self.f = -1 print("Queue Rear= ", self.r) self.r = -1 Queue Contents: ['Aly', 'Judy', 'Mona', 'Omar'] def enqueue(self, val): q1 = Queue() Queue Size= 4 if val not in self.q: q1.enqueue("Aly") Queue Front= 0 if self.f==-1: self.f+=1 q1.enqueue("Judy") Queue Rear= 3 self.q.append(val) q1.enqueue("Mona") self.r+=1 q1.enqueue("Omar") q1.show() Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 18  Removing Element - Dequeue We remove the data using the built- in pop method with the help of current front value. class Queue: def __init__(self): def show(self): self.q = [] # list() print("Queue Contents : ",self.q) self.f = -1 print("Queue Size= ",len(self.q)) self.r = -1 print("Queue Front= ",self.f) Queue Contents : ['Aly', 'Judy', 'Mona', 'Omar'] def enqueue(self, val): print("Queue Rear= ",self.r) Queue Size= 4 if val not in self.q: Queue Front= 0 if self.f==-1: self.f+=1 q1 = Queue() Queue Rear= 3 self.q.append(val) q1.enqueue("Aly") Dequeue --> Aly self.r+=1 q1.enqueue("Judy") Dequeue --> Judy q1.enqueue("Mona") Queue Contents : ['Mona', 'Omar'] def dequeue(self): q1.enqueue("Omar") Queue Size= 2 if len(self.q)>0: q1.show() Queue Front= 2 d= self.q.pop(0) print("Dequeue --> ",q1.dequeue()) Queue Rear= 3 self.f+=1 return d print("Dequeue --> ",q1.dequeue()) return ("No elements in Queue!") q1.show() Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 19  Implementing a Queue using Linked List class Node: We can write a Python program to implement queue using def __init__(self,data): linked list as follow: self.data=data self.next=None def Traverse(self): class Queue: if self.front==None: print("No Nodes exist") def __init__(self): return self.front=None temp=self.front self.rear=None self.ctr=0 while temp is not None: print(temp.data) def Enqueue(self,data): temp=temp.next node=Node(data) print("Number of Elements in the Queue= ",self.ctr) if self.front==None: q1=Queue() self.front=node q1.Enqueue("One") One self.rear=node q1.Enqueue("Two") Two self.ctr+=1 q1.Enqueue("Three") Three else: q1.Traverse() Number of Elements in the Queue= 3 self.rear.next=node self.rear=node Faculty of Computers self.ctr+=1Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 20  Implementing a Queue using Linked List class Node: Add Dequeue method to previous program, as q1=Queue() def __init__(self,data): follow: q1.Traverse() self.data=data q1.Enqueue("One") self.next=None def Dequeue(self): q1.Enqueue("Two") class Queue: if self.front==None: q1.Enqueue("Three") def __init__(self): print("No Nodes exist") q1.Traverse() self.front=None else: q1.Dequeue() self.ctr=0 print("Dequeued from queue",self.front.data) q1.Traverse() self.rear=None self.front=self.front.next def Enqueue(self,data): self.ctr-=1 No Nodes exist node=Node(data) def Traverse(self): One if self.front==None: Two if self.front==None: Three self.front=node print("No Nodes exist") Number of Elements in the Queue= 3 self.rear=node return Dequeued from queue One self.ctr+=1 temp=self.front Two else: while temp is not None: Three self.rear.next=node print(temp.data) Number of Elements in the Queue= 2 self.rear=node temp=temp.next Facultyself.ctr+=1 print("Number of Computers Science & Artificial of Elements in the Queue= Intelligence ",self.ctr) Dr. Alaa Abd El-Hamid Radwan 21  Exercises 1) A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________ A) Queue B) Stack C) Tree D) Linked list 2) A normal queue, if implemented using an array (List) of size MAX_SIZE, gets full when? A) Rear = MAX_SIZE – 1 B) Front = (rear + 1)mod MAX_SIZE C) Front = rear + 1 D) Rear = front 3) A queue follows __________ A) FIFO (First In First Out) principle B) LIFO (Last In First Out) principle C) Ordered array D) Linear tree 4) If the elements “A” , “B” , “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed? A) ABCD B) DCBA C) DCAB D) ABDC Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 22  Questions 1) A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________ A) Queue B) Stack C) Tree D) Linked list 2) A normal queue, if implemented using an array (List) of size MAX_SIZE, gets full when? A) Rear = MAX_SIZE – 1 B) Front = (rear + 1)mod MAX_SIZE C) Front = rear + 1 D) Rear = front 3) A queue follows __________ A) FIFO (First In First Out) principle B) LIFO (Last In First Out) principle C) Ordered array D) Linear tree 4) If the elements “A” , “B” , “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed? A) ABCD B) DCBA C) DCAB D) ABDC Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 23  Questions 5) Given a 5 element queue Q (from front to back: 1, 3, 5, 7, 9), and an empty stack S, remove the elements one-by-one from Q and insert them into S, then remove them one-by- one from S and re-insert them into Q. The queue now looks like (from front to back). A) 1, 3, 5, 7, 9 B) 9, 7, 5, 3, 1 C) 9, 7, 1, 3, 5 D) 1, 3, 9, 7, 5 Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 24  Exercise 1 1) Draw the queue after each of the following operations, assume that you start with an empty queue. 1) enqueue (A) 2) enqueue (B) 3) enqueue (C) 4) dequeue () 5) enqueue (D) 6) enqueue (E) 7) dequeue () Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 25  Exercise 2 2) Starting with an empty queue, perform the following operations and draw the queue after each dequeue operation. 1) enqueue (21) 2) enqueue (12) 3) enqueue (31) 4) dequeue () 5) enqueue (41) 6) enqueue (7) 7) enqueue (37) 8) dequeue () 9) enqueue (44) 10) enqueue (5) 11) enqueue (23) 12) dequeue () Faculty of Computers Science & Artificial Intelligence Dr. Alaa Abd El-Hamid Radwan 26