DSA Chap 4.pptxDSA Chap 4.pptxDSA Chap 4.pptx

DSA Chap 4.pptxDSA Chap 4.pptxDSA Chap 4.pptxDSA Chap 4.pptx

1. Chapter 4 1

2. Queue 2

3. Objective At the end of the session students should have basic understanding of Queue : what is it? Basic operations of queue Implementation of queue Types of queues Application of queue 3

4. A queue is linear data structure and collection of elements. A queue is another special kind of list, where items are inserted at one end called the rear and deleted at the other end called the front . The principle of queue is a “FIFO” or “First-in-first-out” . Queue is an abstract data structure. A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall , where the first person entering the queue is the first person who gets the ticket. 4 1. Introduction

5. 5

6. A queue is logically a first in first out ( FIFO or first come first serve) linear data structure. E.g.1 A customer come and join in a queue to take the train ticket at the end ( rear ) and the ticket is issued from the front end of queue. That is, the customer who arrived first will receive the ticket first. It means the customers are serviced in the order in which they arrive at the service centre. 6 1. Introduction

7. E.g.2 A line of people waiting for a bank teller. The queue has a front and a rear . $ $ Front Rear 7

8. New elements are added at one end called rear , and the existing elements are deleted from other end called front . The basic operations that can be performed on queue are 1. Insert (or add) an element to the queue ( enqueue ). 2. Delete (or remove) an element from a queue ( dequeue ) 8 2. Queue operations

9. Queue operations work as follows: 1. Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue. 2. When initializing the queue, we set the value of FRONT and REAR to 0. 3. On enqueuing an element, we increase the value of REAR index and place the new element in the position pointed to by REAR. 4. On dequeuing an element, we return the value pointed to by FRONT and increase the FRONT index. 5. Before enqueuing, we check if queue is already full. 6. Before dequeuing, we check if queue is already empty. 7. When enqueuing the first element, we set the value of FRONT to 1. 8. When dequeuing the last element, we reset the values of FRONT and REAR to 0. 9

10. Insert (or add) an element to the queue ( enqueue ). When an item is inserted to the queue, it always goes to the end. $ $ Front Rear 10

11. 2. Delete (or remove) an element from a queue ( dequeue ) When an item is taken from the queue, it always comes from the front. $ $ Front Rear 11

12. 12 Operations on Queues Insert( item ) : (also called enqueue ) It adds a new item to the tail of the queue Remove( ) : (also called delete or dequeue ) It deletes the head item of the queue, and returns to the caller. If the queue is already empty, this operation returns NULL getHead ( ): Returns the value in the head element of the queue

13. Operations… getTail ( ): Returns the value in the tail element of the queue isEmpty ( ): Returns true if the queue has no items size( ): Returns the number of items in the queue 13

14. Example 14

15. 1.Queue using Array: Let us consider a queue, which can hold maximum of five elements. Initially the queue is empty. Now, insert 11 to the queue. Then queue status will be: 15

16. Next, insert 22 to the queue. Then the queue status is: Again insert another element 33 to the queue. The status of the queue is: Now, delete an element. The element deleted is the element at the front of the queue. So the status of the queue is: 16

17. Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So, 22 is deleted. The queue status is as follows: Now, insert new elements 44 and 55 into the queue. The queue status is: 17

18. Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The queue status is as follows: 18

19. Now it is not possible to insert an element 66 even though there are two vacant positions in the linear queue. To overcome this problem the elements of the queue are to be shifted towards the beginning of the queue so that it creates vacant position at the rear end. Then the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the rear end. After this operation, the queue status is as follows: This difficulty can overcome if we treat queue position with index 0 as a position that comes after position with index 4 i.e., we treat the queue as a circular queue. 19

20. 20

21. 21

22. 3. Queue Implementation Queues can be implemented using An array (static implementation) 22

23. 3.1 Array-based Queue Implementation A queue can be implemented with an array, as shown here. For example, this queue contains the integers 4 (at the front), 8 and 6 (at the rear). [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . An array of integers to implement a queue of integers 4 8 6 We don't care what's in this part of the array. 23

24. Array based Implementation The easiest implementation also keeps track of the number of items in the queue and the index of the first element (at the front of the queue), the last element (at the rear). [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . 4 8 6 size 3 first last 2 24

25. A Dequeue Operation When an element leaves the queue, size is decremented, and first changes, too. [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . 4 8 6 size 2 first 1 last 2 25

26. An Enqueue Operation When an element enters the queue, size is incremented, and last changes, too. [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . 2 8 6 size 3 first 1 last 3 26

27. Class Activity Create a Queue and insert these elements one by one 7,6,5,4,12,3,67,8 27

28. Class Activity 28 Enqueue: Draw a diagram of an empty queue. Add 5 people to the queue, one at a time. Draw the queue after each addition. Label the front and rear of the queue. Dequeue: Remove 2 people from the queue, one at a time. Draw the queue after each removal. Label the new front and rear.

29. Circular array implementation of enqueue and dequeue operations A problem with simple arrays is we run out of space even if the queue never reaches the size of the array. Circular arrays can be used to solve this problem. 29

30. Circular array implementation… There is special behaviour at the end of the array. For example, suppose we want to add a new element to this queue, where the last index is [5]: [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] 2 1 6 size 3 first 3 last 5 30

31. Circular array implementation… The new element goes at the front of the array (if that spot isn’t already used): [ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] 2 1 6 size 4 first 3 last 4 31

32. Example: Consider a queue with MAX_SIZE = 4 32

33. Circular array implementation 33

34. Exercise 2 Perform this Operations using Circular Array Array size = 5 34 Enqueue (a) Enqueue (b) Dequeue () Enqueue (c) Enqueue (d) Dequeue () Enqueue (e) Enqueue (f) Enqueue (g) Dequeue () Enqueue (h)

35. 4. Types of queues Deque Priority Queue Demerging Queues Merging Queues 35

36. Deque (pronounced as Deck) - is a Double Ended Queue insertion and deletion can occur at either end 36

37. Deque … 37

38. Priority Queue is a queue where each data has an associated key that is provided at the time of insertion. dequeue operation deletes data having highest priority in the list has a front and rear as any queue items are removed from the front Items are ordered by key value so that the item with the lowest key (or in some implementations the highest key) is always at the front. 38

39. Priority Queue 39

40. Priority Queue Demerging Queues - is the process of creating two or more queues from a single queue. - used to give priority for some groups of data 40

41. Priority Queue Merging Queues - is the process of creating a priority queue from two or more queues. - the ordinary dequeue implementation can be used to delete data in the newly created priority queue. 41

42. Priority Queue Merging Queues It is also possible to merge two or more priority queues. 42

43. 5. Application of Queues i . Print server- maintains a queue of print jobs ii. Disk Driver- maintains a queue of disk input/output requests iii. Task scheduler in multiprocessing system- maintains priority queues of processes iv. Telephone calls in a busy environment –maintains a queue of telephone calls v. Simulation of waiting line- maintains a queue of persons 43

44. The end 44