Queue data structures and operation on data structures

Queue data structures and operation on data structures

• 1.
  By Muskan. S (Embedded Systemand VLSI) QUEUE
• 2.
  2 Queue ⚫ A queueis an ordered collection of items where an item is inserted at one end called the “rear” and an existing item is removed at the other end, called the “front”. ⚫ Queue is also called as FIFO list i.e. First-In First- Out. ⚫ In the queue only two operations are allowed enqueue and dequeue. ⚫ Enqueue means to insert an item into back of the queue. ⚫ Dequeue means removing the front item.The people standing in a railway reservation row are an example of queue. 48 Prof. K. Adisesha
• 3.
  3 Queue ⚫The queue canbe implemented into two ways: ◦ Using arrays (Static implementation) ◦ Using pointer (Dynamic implementation) 49 Prof. K. Adisesha
• 4.
  4 T ypes of Queues ⚫Queuecan be of four types: o Simple Queue o Circular Queue o Priority Queue o De-queue ( Double Ended Queue)
• 5.
  5 Simple Queue ⚫Simple Queue:In simple queue insertion occurs at the rear end of the list and deletion occurs at the front end of the list.
• 6.
  6 Circular Queue ⚫Circular Queue:Acircularqueue is a queue in which all nodes are treated as circular such that the last node follows the first node.
• 7.
  7 Priority Queue ⚫A priorityqueue is a queue that contains items that have some present priority. An element can be inserted or removed from any position depending upon some priority.
• 8.
  8 Dequeue Queue ⚫Dequeue: Itis a queue in which insertion and deletion takes place at the both ends.
• 9.
  9 Operation on Queues ⚫Queue(): It creates a new queue that is empty. ⚫enqueue(item): It adds a new item to the rear of the queue. ⚫dequeue( ): It removes the front item from the queue. ⚫isEmpty( ): It tests to see whether the queue is empty. ⚫size( ): It returns the number of items in the queue.
• 10.
  10 Memory Representation ofa queue using array ⚫ Queue is represented in memory using linear array. ⚫ Let QUEUE is a array, two pointer variables called FRONT and REAR are maintained. ⚫ The pointer variable FRONT contains the location of the element to be removed or deleted. ⚫ The pointer variable REAR contains location of the last element inserted. ⚫ The condition FRONT = NULL indicates that queue is empty. ⚫ The condition REAR = N-1 indicates that queue is full.
• 11.
  11 Queue Insertion Operation(ENQUEUE): ⚫ ALGORITHM: ENQUEUE (QUEUE, REAR, FRONT, ITEM) QUEUE is the array with N elements. FRONT is the pointer that contains the location of the element to be deleted and REAR contains the location of the inserted element. ITEM is the element to be inserted. Step 1: if REAR = N-1 then [Check Overflow] PRINT “QUEUE is Full or Overflow” Exit [End if] Step 2: if FRONT = NULL then [Check Whether Queue is empty] FRONT = -1 REAR = -1 else REAR = REAR + 1 [Increment REAR Pointer] Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position] Step 4: Return
• 12.
  12 Queue Deletion Operation(DEQUEUE) ALGORITHM: DEQUEUE (QUEUE, REAR, FRONT, ITEM) QUEUE is the array with N elements. FRONT is the pointer that contains the location of the element to be deleted and REAR contains the location of the inserted element. ITEM is the element to be inserted. Step 1: if FRONT = NULL then [Check Whether Queue is empty] PRINT “QUEUE is Empty or Underflow” Exit [End if] Step 2: ITEM = QUEUE[FRONT] Step 3: if FRONT = REAR then [if QUEUE has only one element] FRONT = NULL REAR = NULL else FRONT = FRONT + 1 [Increment FRONT pointer] Step 4: Return
• 13.
  13 Application of Queue ⚫Simulation ⚫Variousfeatures of Operating system ⚫Multi-programming platform systems. ⚫Different types of scheduling algorithms ⚫Round robin technique algorithms ⚫Printer server routines ⚫Various application software’s is also based on queue data structure.
• 14.
  THANK YOU