数据结构队列Queues.docx

1、数据结构队列QueuesQueuesImportant points to remember about a Queue:Queue FIFO First-In-First-Out DSA Queue is a Data Structure where you can insert from one end called “REAR” and delete from the other end called “FRONT”.Implementation of a Queue: a) As an array static DSi) Linear Queue uses Linear arrayii

2、) Circular Queue uses Circular arrayb) As a Linked List dynamic DSa) Implementation of a queue:As an arrayWhen the Queue is empty:Front = -1Rear = -1When the Queue has only one item:Front = 0Rear = 0When the Queue has more than one item:Front =0Rear 01. Queue Overflow: Trying to Insert an element in

3、 a queue when the queue is FULL.This condition should not arise. To avoid this error condition, always check for the position of REAR before inserting a new value in the queue. If REAR = max-1 (the last index position of the array) - this means the REAR has reached the maximum size of the array and

4、there is no more space for the new data.2. Queue Underflow: Trying to delete an item from an empty queue.In order to avoid this error situation always check for Front= -1 before trying to delete any value.Algorithm for inserting data in a Linear Queue (as an array):1. If rear=max-1 /max is the maxim

5、um size of the array and we check with max-1 if rear is pointing to the last position in the arrayDisplay “queue full”Exit2. If Front = Rear = -1 /Q is emptya.front = front+1b.Go to step 33. Rear=Rear+1/ data is inserted at the rear4. Queue rear =newdataAlgorithm for deleting data from a linear queu

6、e (as an array): 1. if front = -1/ there is no data in the queueDisplay “queue empty”Exit2. if front = rear front = rear =-13. delete the value at queuefront4. front=front+1Note : Always remember : In a Queue For every Insert: Rear = Rear +1After every Delete : Front = Front + 1The values are never

7、decremented in the case of an insert or a delete in a queueImplementation of a queue as a circular queue ( CQ):For the empty CQ :Front =-1Rear =-1For the CQ with only one data:Front = RearFor the CQ to be full:Condition 1: Front =0 and Rear =max-1ORCondition 2:Front = rear +1 Algorithm for inserting

8、 data in a Queue (as a circular queue/array):1. If (Front =0 AND Rear = Max-1) OR front=rear+1display “queue full”exit2. if front = -1 / Q is emptyfront=0rear=0goto step5/ insert the 1st data in the CQ3. if rear =max-1 set rear = 0goto step54. rear = rear+15. Queue rear = newdataAlgorithm for deleti

9、ng data in a Queue (as a circular queue/array):1. If Front = -1 / no data in the Qdisplay “queue empty”exit2. If front = rear / there is only one data in the CQueuefront =-1rear=-1exit3. if Front = max-1 / deleting the data from the last index position of the circular arrayfront=0exit4. front=front+

10、1Implementation of a QUEUE as a linked list :If the queue is empty : front = rear =nullIf there is only one node : front =rearQueue Overflow: This condition cannot arise in a Linked List as there is no size limit.Exception : Memory runs out there is no enough space in the memory to store the data Qu

11、eue Underflow: to avoid this situation always check for Front=Null (which means the list is empty)Algorithm for inserting a new data in a queue which is a Linked list/ Linked Queue: The newnode will always be inserted in the end of the linked list as a last node!1. create newnode2. newnode.data=data

12、3. newnode.next=null4. if front =null / if the queue is empty front = newnode rear =newnode5. rear.next=newnode6. rear=newnodeAlgorithm for deleting a data from the queue as a Linked list/Linked Queue: always begins from the 1st node of the list1. if front = null / the queue is emptydisplay “ queue empty”exit2. if front = rear / there is only one nodefront = rear = nullexit3. current = front4. front=current.next5. release current