1 Queues – Chapter 3 A queue is a data structure in which all additions are made at one end called the rear of the queue and all deletions are made from.

Similar presentations

Presentation on theme: "1 Queues – Chapter 3 A queue is a data structure in which all additions are made at one end called the rear of the queue and all deletions are made from."— Presentation transcript:

1
1 Queues – Chapter 3 A queue is a data structure in which all additions are made at one end called the rear of the queue and all deletions are made from the other end called the front of the queue Alternatively, in a queue the element deleted is the one that stayed in the queue the longest. This is also called first-in-first-out (FIFO) Classical example of queues is a queue of people waiting to pay bills.

2
2 Queue Concept and Example A queue has a Front and a Rear The insert operation is often called Enqueue The delete operation is often called Dequeue Front of the queue Next person to be served Rear of the queue Next person will join the queue from the rear Queue of people waiting to pay bills

3
3 Queue ADT A queue is a data structure in which all additions are made at one end called the rear of the queue and all deletions are made from the other end called the front of the queue Common queue operations: –Enqueue(item) – Add the item to the end of the Q –Dequeue() – Remove & return the item at the front –isEmpty() – Return true if the Q is empty –isFull() – Return true if the Q is full

4
4 How do we implement queue ADT? 2 ways to implement a queue –Using an array –Using a linked list

5
5 Array Implementation of Queues: Operations Use an array int Q[N] front points to the front element of the queue, i.e., holds the index of the array Q that contains the front of the queue rear points to next slot after the last element in the queue noItems contains the current number of items in the queue. An empty queue is one where noItems = 0 A full queue is one where noItems = N

13
13 Array Implementation of Queues: Last Word We can implement a queue of at most “N-1” elements with an array int Q[N] and 2 variables: int front, int rear Think about how you would define –An empty queue –A full queue Q front = 3 8 6 15 rear = 2 A Full Queue 2 4 7 Q front = 3 rear = 3 An Empty Queue Front and rear are equal to each other in an empty queue There is one empty space between rear and front in a full queue

20
20 Applications of Queues File servers: Users needing access to their files on a shared file server machine are given access on a FIFO basis Printer Queue: Jobs submitted to a printer are printed in order of arrival Phone calls made to customer service hotlines are usually placed in a queue Expected wait-time of real-life queues such as customers on phone lines may be too hard to solve analytically use queue for simulating real-life queues