CPU Scheduling : Various CPU scheduling algorithms make use of this data structure to implement multiprocessing.This means that for storing n elements, the space required is O(n). Space RequiredĪ queue only takes the space used to store the elements of the data type specified. There is no interaction needed with the rest of the elements. Similar to insertion, deleting an element is only possible from the front of the queue. Inserting an element is only possible at the rear. Similarly, searching an element will involve continuously shifting the front element off the queue until the required element is found. Queue Complexity AccessĪn arbitrary element in a queue can only be accessed by continuously shifting the front element. If there exist two elements with the same priority, then the order of which the element was inserted is considered. There can be different criteria’s for the priority queue to assign priorities.Īn element with the highest priority gets processed first. This priority determines which elements are to be deleted and processed first. Priority QueueĪ priority queue assigns a priority to each element in the queue. There is no shifting involved and the whole queue can be used for storing all the elements. This is an efficient implementation for a queue that has fixed maximum size. Circular Queue (Circular Buffer)Ī circular queue uses a single, fixed-size buffer as if it were connected end-to-end like a circle.Ĭburnett, derivative work: Pluke A double-ended queue allows for insertion and deletion from both ends. In a standard queue, insertion can only be done from the back and deletion only from the front. Printf("\nDeleted item is: %d", queue) Ī queue can have some variations which make it useful in certain situations: Double-Ended queue (Deque) Then check whether both front and rear are equal ( front = rear ), if it TRUE, then set both front and rear to ‘-1’ ( front = rear = -1).Then display the queue as the deleted element. If it is NOT EMPTY, then increment the front value by one ( front++ ).If it is EMPTY, then display an error and terminate the function.If it is NOT FULL, then increment the rear value by one ( rear++ ) and set queue = value.If it is FULL, then display an error and terminate the function.Check whether the queue is FULL ( rear = SIZE - 1).Int front = -1, rear = -1 Enqueue Operation Define two integer variables front and rear and initialize both with ‘-1’.Create a one dimensional array with the above defined SIZE.For simplicity, we will create a queue with an array. if(rear = SIZE-1)Ī queue can be created using both an array or through a linked list. This prevents any error if more space cannot be allocated for the next item. The overflow condition checks if the queue is full (or more memory is available) before enqueueing any element. The underflow condition checks if there exists any item before popping from the queue. We must implement check conditions to see if we are not adding or deleting elements more than it can maximum support. Overflow and Underflow ConditionsĪ queue may have a limited space depending on the implementation. The rear pointer always points to the position where an element would be enqueued next. The front pointer always points to the position where an element would be dequeued next. These pointers update continuously and keep a check on the overflow and underflow conditions. To efficiently add or remove data from the queue, two special pointers are used which keep track of the first and last element in the queue. The element always gets removed from the front of the queue. The Dequeue is used to remove an element from the queue. The element always gets added to the end of the current queue items. The Enqueue is used to add an element to the queue. The two primary operations in a queue are the enqueue and the dequeue operation: Enqueue Operation The first person to enter leaves first.Ī ticket counter can be an example where the people standing in the queue get their tickets one by one and leave the queue. A person may join the queue from the end and may leave tit from the front. Queues can be visualised like a real-life queue of people.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |