Title Queues.pdf ✅

Queue Topics 1. Introduction to Queue 2. Implementation of Queue using Arrays 3. Implementation of Queue using Linked List 4. Details of Inbuilt Queue library in C++, Java & Python 5. Introduction to Deque 6. Details of Inbuilt Deque library in C++, Java & Python 7. Problems & Solutions
Introduction Like Stack, Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out [FIFO] or Last In Last Out [LILO]. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in the order of removing elements/items. In a stack most recently added item is removed/popped; in a queue, we remove/dequeue the least recently added item. Queue primarily supports the following basic operations: 1. Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition. Complexity : O(1) 2. 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. Complexity : O(1) 3. Front: Get the front item from queue. Complexity : O(1) 4. Rear: Get the last item from queue. Complexity : O(1) Applications of Queue Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search. This property of Queue makes it also useful in the following scenarios: 1. When a single resource is shared among multiple consumers, the consumers have to wait in the Queue to access the resource. Examples include: CPU scheduling, Disk Scheduling, etc. 2. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes, the data sits in a Queue, until all the fragments of the data is available and then the data is re-structured. Examples include: IO Buffers, pipes, file IO, packet routing over internet etc.
Implementation There are two ways to implement a queue: ● Using array ● Using linked list Array implementation of Queue in C/C++ For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner #include #include #include // A structure to represent a queue struct Queue { int front, rear, size; unsigned capacity; int* array; }; // Function to create a queue of given capacity. It initializes size of queue as 0 struct Queue* createQueue(unsigned capacity) { struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue)); queue->capacity = capacity; queue->front = queue->size = 0; queue->rear = capacity - 1; // This is important, see the enqueue queue->array = (int*) malloc(queue->capacity * sizeof(int)); return queue; } // Queue is full when size becomes equal to the capacity int isFull(struct Queue* queue) { return (queue->size == queue->capacity); } // Queue is empty when size is 0 int isEmpty(struct Queue* queue) { return (queue->size == 0); }