A Queue Data Structure is a fundamental concept .pptx

A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order.

1. Queues ADT

2. Slide courtesy: Dr. Zahid Halim

3. Queues “A Queue is a special kind of list, where items are inserted at one end ( the rear ) And deleted at the other end ( the front ) ” Other Name: First In First Out (FIFO) Difference from Stack: Insertion go at the end of the list, rather than the beginning of the list.

4. Common Operations on Queues (Queue ADT) MAKENULL(Q): Makes Queue Q be an empty list. FRONT (Q ): Returns the first element on Queue Q. ENQUEUE( x , Q ): Inserts element x at the end of Queue Q. DEQUEUE( Q ): Deletes the first element of Q. EMPTY( Q ): Returns true if and only if Q is an empty queue. Example: Line of customers in a bank

5. Applications of Queues Operating system multi-user/multitasking environments, where several users or task may be requesting the same resource simultaneously. Communication Software queues to hold information received over networks and dial up connections. (Information can be transmitted faster than it can be processed, so is placed in a queue waiting to be processed) Some other?

6. Implementation Static Queue is implemented by an array, and size of queue remains fix Dynamic A queue can be implemented as a linked list , and expand or shrink with each enqueue or dequeue operation.

7. A pointer Implementation of Queues Keep two pointers: FRONT: A pointer to the first element of the queue. REAR: A pointer to the last element of the queue. x y . z Front Rear

8. A pointer Implementation of Queues Q.front Q.Rear MAKENULL(Q) Q.front Q.Rear ENQUEUE(x,Q) . x NULL

9. Q.front Q.Rear ENQUEUE(y,Q) x . y Q.front Q.Rear DEQUEUE(Q) . y A pointer Implementation of Queues