A queue is a first-in, first-out (FIFO) data structure used to store elements until they can be processed. Elements are added to the rear of the queue and removed from the front. In a simple array implementation, empty spaces cannot be reused, causing overflow issues. Circular queues address this by connecting the front and rear of the array, allowing elements to wrap around. Common applications of queues include scheduling algorithms, printing/resource sharing, and buffering/paging.
A queue is a first-in, first-out (FIFO) data structure used to store elements until they can be processed. Elements are added to the rear of the queue and removed from the front. In a simple array implementation, empty spaces cannot be reused, causing overflow issues. Circular queues address this by connecting the front and rear of the array, allowing elements to wrap around. Common applications of queues include scheduling algorithms, printing/resource sharing, and buffering/paging.
A queue is a first-in, first-out (FIFO) data structure used to store elements until they can be processed. Elements are added to the rear of the queue and removed from the front. In a simple array implementation, empty spaces cannot be reused, causing overflow issues. Circular queues address this by connecting the front and rear of the array, allowing elements to wrap around. Common applications of queues include scheduling algorithms, printing/resource sharing, and buffering/paging.
A queue is a first-in, first-out (FIFO) data structure used to store elements until they can be processed. Elements are added to the rear of the queue and removed from the front. In a simple array implementation, empty spaces cannot be reused, causing overflow issues. Circular queues address this by connecting the front and rear of the array, allowing elements to wrap around. Common applications of queues include scheduling algorithms, printing/resource sharing, and buffering/paging.
A Queue is a data structure in which insertion of elements is done only in the BACK (rear) end and deletion of data is done only in the FRONT. So, Queue is First In First Out(FIFO) structure. Two pointers FRONT and REAR are used to point to the first and last elements of the queue.
Following operations can be performed on a queue.
1. ENQUEUE: Adds dds an object to the rear of the queue if the queue is not full. Following are the steps of Enqueue operation. i. Check ck whether queue is full. If full, abort by displaying QUEUE OVERFLOW ii. Increment rear by one iii. Place the element in the position pointed by rear. 2. DEQUEUE: Removes and returns an element from the front of the queue if it is not empty. Following are re the steps of Dequeue operation. i. Check whether queue is empty empty. If empty, abort by displaying QUEUE UNDERFLOW ii. Store the element pointed by front in a temporary variable. iii. Increment front by one iv. Return eturn value stored in temporary variable. Example. Let a queue Q store the elements 1, 2, and 3, where 1 is at the front of the queue. This is shown in following Figure, Steps 11-3, 3, below. If Q has finite capacity, then we can detect that Q is full. Dequeueing of the values 1, 2, and 3 is shown in Figure 2.4.3, Steps 4-6, 6, which yields an empty queue. Note how the values that were first enqueued come out the front of the queue first. That is why a queue implements a FIFO buffer.
Prepared for II/IV B.Tech CSE, RVR&JC CE
2. What is the disadvantage of simple queue? How to address it?
In array implementation of simple queue, new elements are always inserted from the rear and if the last location of queue(rear) holds an element, even though the space is available at the beginning of queue, no elements will be inserted. The queue will be treated as overflow. One way to handle this problem is to fill the empty locations, at the beginning of the queue due to delete operations, by shifting the following elements to beginning of the queue. Thus, the space will be available at the rear end and new elements can be inserted at the end. This approach requires that the entire queue be moved up one position in the array every time an element is deleted from queue, which makes DEQUEUE operation expensive. The best solution to this problem is to use ci circular queue. For example consider the following queue with size 3. After invoking ENQUEUE(6), ENQUEUE(9), ENQUEUE(3), the resulting queue is as shown below.
After invoking DEQUEUE( ), queue is
Prepared for II/IV B.Tech CSE, RVR&JC CE
After invoking DEQUEUE( ) second time, queue is
At this stage queue whose capacity is 3 has only one element in it having room for 2 more elements. But, insertion of new element is not possible since rear is already pointing to the last position in the array. 3. Explain circular queue concept. Circular ar queues are particular implementations of queues. It is a data structure that uses a single, fixedfixed size array as if it were connected end end-to-end. This structure lends itself easily to store data elements. elements
Following operations can be performed on a circular queue.
ENQUEUE i. Check whether queue is full. If full, abort by displaying QUEUE OVERFLOW ii. Increment rear by one. iii. if rear is greater than or equal to MAXIMUM SIZE of the queue set it to 0. iv. Place thee element in the position pointed by rear. DEQUEUE
Prepared for II/IV B.Tech CSE, RVR&JC CE
i. Check whether queue is empty. If empty, abort by displaying QUEUE UNDERFLOW
ii. Store the element pointed by front in a temporary variable. iii. Increment front by one iv. If front is greater than or equal to MAXIMUM SIZE of the queue set it to 0. iv. return value stored in temporary variable. Following figure shows ENQUEUE and DEQUEUE operation by means of an example.
4. Mention the applications of queues
Simple queues are used for implementing Round Robin scheduling technique
