CSE 2341 Object Oriented Programming with C Note Set 20 1 Overview Queue Data Structure 2 The Queue queue data structure that stores and retrieves items in a first in first out manner Elements are added to the rear and removed from the front 3 Queue Think of a line of people waiting to check out front rear 4 Applications of Queue Operating systems use queues to keep track of processes that are executing and in which order they are allowed to use the processor Printing queues Communications 5 2 Types Static queues Fixed size Implemented as Arrays Dynamic queues ability to grow and shrink as needed Implemented as Linked lists 6 Basic Queue Operations enqueue x causes a value to be stored in the queue Empty Queue Front Rear enqueue 5 5 enqueue 10 Front 5 enqueue 7 5 10 Rear 10 7 7 Basic Queue Operations dequeue causes a value to be removed from the queue 5 dequeue 10 7 10 dequeue 7 8 Problem With static queue Every dequeue operation requires the elements behind it to move forward very expensive Can overcome by allowing both front and rear indices to move but possible to run out of room in the array Over come by using a circular array OR dynamic queue 9 DynamicQueue class DynIntQueue private struct queueNode int val queueNode next queueNode front queueNode rear public See handout Head 3 Front 4 5 Null Rear 10 Fini 11
View Full Document
Unlocking...