Data Structures and Algorithms Chapter 5: Queues,College of Electronic and Information Engineering Chongqing University of Science and Technology Instructor: Xiong Qian Spring 2013,Chapter 5,Objectives,Upon completion you will be able to: Explain the design, use, and operation of a queue Implement a queue using a linked list structure Understand the operation of the queue ADT Write application programs using the queue ADT Explain categorizing data and queue simulation,Queues,highlights,5-1 Queue Operations 5-2 Queue Linked List Design 5-3 Queue ADTlinked list implementation 5-4 Queue ADTarray implementation 5-5 Queuing Theory 5-6 Queue Applications,The queue concept,A queue is a linear list in which data can be inserted at one end, called the rear, and deleted from the other end, called the front. These restrictions ensure that the data are processed through the queue in the order in which they are received It is a first in-first out (FIFO) data structure.,5-1 Queue Operations,This section discusses the four basic queue operations. Using diagrammatic figures, it shows how each of them work. It concludes with a comprehensive example that demonstrates each operation. Enqueue Dequeue Queue Front Queue Rear Queue Example,Enqueue: Inserts an element at the rear of the queue.,plum,kiwi,front,rear,Enqueue,plum,grape,front,rear,kiwi,grape,data,Queue,Operation,Queue,Dequeue: Deletes an element at the front of the queue.,kiwi,front,rear,Dequeue,plum,grape,front,rear,kiwi,plum,data,Queue,Operation,Queue,grape,Queue Front: Examines the element at the front of the queue.,It returns the data at the front of the queue without changing the contents of the queue. If there are no data in the queue, then the queue is in an underflow state.,plum,grape,front,rear,kiwi,Queue,plum,grape,front,rear,kiwi,Queue,Queue front,plum,data,Operation,Queue Rear: Examines the element at the rear of the queue.,plum,grape,front,rear,kiwi,Queue,plum,grape,front,rear,kiwi,Queue,Queue rear,rear,data,Operation,As with queue front, if there are no data in the queue, the queue is in an underflow state.,Queue example,Data structure: For the linked list implementation of a queue, we use two types of structures: a head and a node. Queue head: The queue head contains the two pointers and a count of the queue. Queue data node: The queue data node contains the user data and a link field pointing to the next node .,5-2 Queue Linked List Design,Queue data structure,Queue Algorithms Create queue Enqueue Dequeue Queue Front Queue Rear Empty Queue Full Queue Queue Count Destroy Queue,Basic queue functions,continued,Create queue: set the metadata pointers to null and the count to 0.,Enqueue: Three conditions need to be considered: 1.insert into an empty queue. 2. Insertion into a queue with data. 3. Insertion into a queue when there is no memory left.,Before,After,Insert into queue with data,Algorithm enque(queue,dataIn) If (queue full) 1 return false End if Allocate (newPtr) newPtr-data = dataIn newPtr-next = null pointer If (queue.count zero) / inserting into null queue 1 queue.front = newPtr Else / insert with data 1 queue.rear-next = newPtr End if Queue.rear = newPtr Queue.count = queue.count + 1 Return true End enqueue,There are four ways to test whether the queue is null 1.Front null 2.Rear null 3.Count 0 4.Empty queue,Dequeue: 1. ensure that the queue contains data. 2. Pass the data back through the parameter list and then set the front pointer to the next item in the queue. 3. If the queue is now empty, set the rear pointer to null.,0,front,rear,count,deleteLoc,(recycled),Before,After,Delete only item in queue,Before,plum,next,data,1,front,rear,count,kiwi,next,data,(recycled),deleteLoc,After,Algorithm dequeue (queue, item) If (queue.count is 0) 1 return false End if Item = queue.front-data deleteLoc = queue.front If (queue.count 1) / deleting only item in the queue 1 queue.rear = null pointer End if Queue.front = queue.front-next Queue.count = queue.count 1 Recycle (deleteLoc) Return true End dequeue,Queue front: the logic of retrieving data is the same to that of dequeue except that the data are not deleted from the queue.,Algorithm queueFront (queue,dataOut) If (queue.count is 0) 1 return false End if dataOut = queue.front-data Return true End queueFront,To implement queue rear, copy this algorithm but change the queue front to the queue rear.,Empty Queue: it returns true if the queue is empty and false if the queue contains data.,Algorithm emptyQueue (queue) Return (queue.count equal 0) End emptyQueue,Full Queue: By allocating a node and then releasing the memory we can determine whether there is room for at least one more node.,Algorithm fullQueue (queue) Allocate (tempPtr) If (allocate successful) 1 recycle (tempPtr) 2 return false Else 1 return true End if End fullQueue,Queue Count: it returns the number of elements currently in the queue by returning the count