Week 14 - Queue Revised.pptx.pdf

QUEUE WEEK 14 What is a Queue? The queue is a basic data structure just like a stack. In contrast to stack that uses the LIFO approach, queue uses the FIFO (first in, first out) approach. With this approach, the first item that is added to the queue is the first item to be removed from the que...

QUEUE WEEK 14 What is a Queue? The queue is a basic data structure just like a stack. In contrast to stack that uses the LIFO approach, queue uses the FIFO (first in, first out) approach. With this approach, the first item that is added to the queue is the first item to be removed from the queue. Just like Stack, the queue is also a linear data structure. In a real-world analogy, we can imagine a bus queue where the passengers wait for the bus in a queue or a line. The first passenger in the line enters the bus first as that passenger happens to be the one who had come first. Queue Sample Applications Typical uses of queues are in simulations and operating systems. Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur. Computer systems must often provide a “holding area” for messages between two processes, two programs, or even two systems. This holding area is usually called a “buffer” and is often implemented as a queue. Serving requests of a single shared resource (printer, disk, CPU), transferring data asynchronously (data not necessarily received at same rate as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets. Call center phone systems will use a queue to hold people in line until a service representative is free. Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox - add songs to the end, play from the front of the list. When programming a real-time system that can be interrupted (e.g., by a mouse click or wireless connection), it is necessary to attend to the interrupts immediately, before proceeding with the current activity. If the interrupts should be handles in the same order they arrive, then a FIFO queue is the appropriate data structure. Queue Illustration In software terms, the queue can be viewed as a set or collection of elements as shown below. The elements are arranged linearly. queue We have two ends i.e. “front” and “rear” of the queue. When the queue is empty, then both the pointers are set to -1. The “rear” end pointer is the place from where the elements are inserted in the queue. The operation of adding /inserting elements in the queue is called “enqueue”. Queue Illustration The “front” end pointer is the place from where the elements are removed from the queue. The operation to remove/delete elements from the queue is called “dequeue”. When the rear pointer value is size-1, then we say that the queue is full. When the front is null, then the queue is empty. Queue Basic Operation Basic Operations The queue data structure includes the following operations: EnQueue: Adds an item to the queue. Addition of an item to the queue is always done at the rear of the queue. DeQueue: Removes an item from the queue. An item is removed or de-queued always from the front of the queue. isEmpty: Checks if the queue is empty. isFull: Checks if the queue is full. peek: Gets an element at the front of the queue without removing it. Enqueue (adds element) Enqueue In this process, the following steps are performed: 1. Check if the queue is full. 2. If full, produce overflow error and exit. 3. Else, increment ‘rear’. 4. Add an element to the location pointed by ‘rear’. 5. Return success. Dequeue (deletes element) Dequeue Dequeue operation consists of the following steps: 1. Check if the queue is empty. 2. If empty, display an underflow error and exit. 3. Else, the access element is pointed out by ‘front’. 4. Increment the ‘front’ to point to the next accessible data. 5. Return success. Detailed Illustration Enqueue Operation Illustration Enqueue Operation Illustration Enqueue Operation Illustration Dequeue Operation Illustration Enqueue and Dequeue Sample Code Implementation (Enqueue) // Enqueue operation to add an element void enqueue(int element) { if (isFull()) { cout