24/10/20181Data Structure:QueueLECTURE 3Queue Overview Queue ADT Basic operations of queue Enqueuing, dequeuing etc. Implementation of queue Array Linked list24/10/20182Queue ADT Like a stack, a queue is also a list. However, with a queue,insertion is done at one end, while deletion is performed atthe other end. Accessing the elements of queues follows a First In, First … Continue reading “Data Structure: Queue | My Assignment Tutor”
24/10/20181Data Structure:QueueLECTURE 3Queue Overview Queue ADT Basic operations of queue Enqueuing, dequeuing etc. Implementation of queue Array Linked list24/10/20182Queue ADT Like a stack, a queue is also a list. However, with a queue,insertion is done at one end, while deletion is performed atthe other end. Accessing the elements of queues follows a First In, First Out(FIFO) order. Like customers standing in a check-out line in a store, the firstcustomer in is the first customer served.The Queue ADT Another form of restricted list Insertion is done at one end, whereas deletion is performed at the other end Basic operations: enqueue: insert an element at the rear of the list dequeue: delete the element at the front of the list Size: count the number of elements in the queue. Clear: to clear all the elements First-in First-out (FIFO) list24/10/20183Enqueue and Dequeue Primary queue operations: Enqueue and Dequeue Like check-out lines in a store, a queue has a front and a rear. Enqueue Insert an element at the rear of the queue Dequeue Remove an element from the front of the queueInsert(Enqueue)Remove(Dequeue) front rearImplementation of Queue Just as stacks can be implemented as arrays or linked lists, so withqueues. Dynamic queues have the same advantages over static queues asdynamic stacks have over static stacks24/10/20184Queue Implementation of Array There are several different algorithms to implementEnqueue and Dequeue Naïve way When enqueuing, the front index is always fixed and the rearindex moves forward in the array.frontrearEnqueue(3)3frontrearEnqueue(6)3 6frontrearEnqueue(9)3 6 9Queue Implementation of Array Naïve way When enqueuing, the front index is always fixed and the rearindex moves forward in the array. When dequeuing, the element at the front the queue isremoved. Move all the elements after it by one position.(Inefficient!!!)Dequeue()frontrear6 9Dequeue() Dequeue()frontrear9rear = -1front24/10/20185Queue Implementation of Array Better way When an item is enqueued, make the rear index move forward. When an item is dequeued, the front index moves by oneelement towards the back of the queue (thus removing the frontitem, so no copying to neighboring elements is needed).XXXXOOOOO (rear)OXXXXOOOO (after 1 dequeue, and 1 enqueue)OOXXXXXOO (after another dequeue, and 2 enqueues)OOOOXXXXX (after 2 more dequeues, and 2 enqueues)(front)The problem here is that the rear index cannot move beyond thelast element in the array.Implementation using Circular Array Using a circular array When an element moves past the end of a circular array, it wrapsaround to the beginning, e.g. OOOOO7963 4OOOO7963 (after Enqueue(4)) After Enqueue(4), the rear index moves from 3 to 4.24/10/20186Empty or Full? Empty queue if (queue.Front > queue.Rear)Console.WriteLine(“Queue is empty”);Full queue. if (queue.Rear == queue.items.Length-1)24/10/20187Queue Implementation of Fixed Arraypublic struct Queue // data structure for Queue{ public int Front;public int Rear;public int[] items;}public class QueueStructure{ Queue queue = new Queue();public QueueStructure(int value) // use of constructor{queue.items = new int[value]; // creating an array of given size.queue.Front = 0;queue.Rear = -1;}. . .Queue Class Attributes of Queue front/rear: front/rear index counter: number of elements in the queue maxSize: capacity of the queue Operations of Queue IsEmpty: return true if queue is empty, return false otherwise IsFull: return true if queue is full, return false otherwise Enqueue: add an element to the rear of queue Dequeue: delete the element at the front of queue Display: print all the data of Queue. Size: Display the number of elements in the queue Clear: Clear all the elements in the Array.The whole program on this isprovided separately on yourMoodle24/10/20188Operations of Queuepublic void Enqueue(){if (queue.Rear ==queue.items.Length‐1){Console.WriteLine(“Queue is full and itemscannot be added..”); }else{Console.Write(“Enter anumber to be added in Queue : “);queue.Rear++;queue.items[queue.Rear] =Convert.ToInt32(Console.ReadLine());Console.WriteLine(“Enqueuedone/ Job added to the queue..”);}Display();}public int Dequeue(){if (queue.Front > queue.Rear)Console.WriteLine(“Queue is empty”);elseConsole.WriteLine(“The first job in queuetaken out:{0}”, queue.items[queue.Front]);queue.Front++;Display();return ‐1;}Enqueue()OperationDequeue()OperationClear() OperationSize() Operationpublic void Clear(){Console.WriteLine(“The whole jobsis getting cleared in the Queue”);if (queue.Rear
