CS203(Data Structures and Objects)

the question

OBJECTIVES: To understand the concept of Queue data structure - logical and application level understanding, and basic supported operations. Understand the requirement and concept of a circular array for queue implementation. Queue Like the stack, the queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (called an en-queue operation) and removed from the front (called a de-queue operation). Queues operate like standing in line at a movie theatre ticket counter 1. If nobody cheats, then newcomers go to the back of the line. The person at the front of the line is the next to be served. Thus, queues release their elements in order of arrival. Accountants have used queues since long before the existence of computers. They call a queue a "FIFO" list, which stands for "First-In, First-Out." insert remove The rear of the queue is accessed whenever a new element is added to the queue (we will refer this end as tail), and the front of the queue is accessed whenever an element is deleted from the queue (this end will be referred as head). As in a stack, the middle elements of the queue are inaccessible, even if the queue elements are stored in an array. Queue: A data structure in which the elements are added at one end, called the rear, and deleted from the other end, called the front; a First in First out (FIFO) data structure. Queue operations are similar to stack operations. The following operations are needed to properly manage a queue: From the definition of queues, we see that the two key operations are insert and delete. We call the insert operation insertQueue and the delete operation removeQueue. Because elements can be neither deleted from an empty queue nor added to a full queue, we need two more operations to successfully implement the insertQueue and removeQueue operations: isEmpty (checks whether the queue is empty) and is full (checks whether a queue is full). We also need an operation, initQueue, to initialize the queue to an empty state. A typical implantation of Queue data structure should support following operations: initQueue - Initializes the queue to an empty state. 1sEmpty - Determines whether the queue is empty. If the queue is empty, it returns the value true; otherwise, it returns the value false. isFull - Determines whether the queue is full. If the queue is full, it returns the value true; otherwise, it returns the value false. getFront - Returns the front, that is, the first element of the queue. Prior to this operation, the queue must exist and must not be empty. .getEnd - Returns the last element of the queue. Prior to this operation, the queue must exist and must not be empty. insertQueue - Adds a new element to the rear of the queue. Prior to this operation, the queue must exist and must not be full. removeQueue - Removes the front element from the queue. Prior to this operation, the queue must exist and must not be empty. As in the case of a stack, a queue can be stored in an array or in a linked structure. We will consider Array based implementation at the moment. The main issue with this implementation is deciding how to keep track of the front and rear ends of the queue. Regardless of the implementation approach, because elements are added at one end and removed from the other end, we need two markers to keep track of the front and rear of the queue. We name them as queuehead and queueTail. Let's see a simple realization of a queue by means of an array, queueArr, with capacity N, for storing its elements. In particular, let queueArr[@] be the front of the queue and have the queue grow from there. This is not an efficient solution, however, for it requires that we move all the elements forward one array cell each time we perform a de-queue operation. Such an implementation would therefore require e(n) time to perform the de-queue function, where n is the current number of elements in the queue. If we want to achieve constant time for each queue function, we need a different approach. A far more efficient implementation can be obtained by relaxing the requirement that all elements of the queue must be in the first n positions of the array. We will still require that the queue be stored be in contiguous array positions, but the contents of the queue will be permitted to drift within the array. Now, both the en-queue and the de-queue operations can be performed in e(1) time because no other elements in the queue need be moved. The following abstract class queuexDT defines these operations as an ADT for storing integers: class queue ADT { private: int maxQueueSize; //variable to store the maximum queue size Int queueLen; //variable to store the number of elements in the queue Int queueHead; //variable to point to the first element of the queue int queue Tail; //variable to point to the last element of the queue int queueArr; //marker to the array to store queue elements public: queue ADT(inte); bool isEmpty(); /Function to determine whether the queue is empty. Postcondition: Returns true if the queue is empty, otherwise returns false. bool isFull(); /*Function to determine whether the queue is full. Postcondition: Returns true if the queue is full, otherdse returns false. void initQueue(); /* Function to initialize the queue to an empty state. Postcondition: The queue is enpty. int get Front(); /* Function to return the first element of the queue. Precondition: The queue exists and is not empty. Postcondition: If the queue is empty, the program terminates; otherdse, the first element of the queue is returned. int getEnd(); /* Function to return the last element of the queue. Precondition: The queue exists and is not empty. Postcondition: If the queue is empty, the program terminates; otherwise, the last element of the queue is returned. / void insertQueue(int queue Element); / Function to add queue Element to the queue. Precondition: The queue exists and is not full. Postcondition: The queue is changed and queueElement is added to the queue." void removeQueue(); Function to remove the first element of the queue. Precondition: The queue exists and is not empty. Postcondition: The queue is changed and the first element is removed from the queue. }; Figure - 1: queueADT class declaration. When and How do we manipulate queuehead and queueTail - Before writing the algorithms to implement the queue operations, we need to decide how to use queueHead and queue Tail to access the queue elements. How do queuehead and queue Tail indicate that the queue is empty or full? Suppose that queuehead gives the index of the first element of the queue, and queueTail gives the index of the last element of the queue. To add an element to the queue, first we advance queueTail to the next array position and then add the element to the position that queuetail is pointing to. To delete an element from the queue, first we retrieve the element that queuehead is pointing to and then advance queuehlead to the next element of the queue. Thus, queueread changes after each de-queue operation and queuetail changes after each en-queue operation. Let us see what happens when queueHead changes after a de-queue operation and queue Tail changes after an en-queue operation. Assume that the array queueArr to hold the queue elements is of size 100. Initially, the queue is empty. After the en-queue operation (insertQueue) operation with a value 'A', the list looks like: 10 11 12 196 197 198 1 queado Queueil with subsequent en-queue operations to insert 'B and C, the queuearr looks like this: 101 121 196 197 198 1991 A queueteado queue-2 Now, with a de-queue operation (removeQueue), the queueArr is updated as following: 101 !!! 12 196 197 198) Goretead1 2 Now, with another de-queue, the queuearr is updated as following: 196 197 198 199 1011121 Quechead2 Queue Now the flexible ending of the contents in the queuert, when elements are removed from the queue, the front index increases (queueHead), and rear index (queueTail) index increases with new element inserted in the queueArr. Over time, the entire queue will drift toward the higher-numbered positions in the array. Once an element is inserted into the highest- numbered position in the array, the queue has run out of space. This happens despite the fact that there might be free positions at the low end of the array where elements have previously been removed from the queue. One of the solutions for this drifting problem can be slide all of the queue elements towards the first array position when the queue overflows to the rear (that is, queue Tail points to the last array position), we can check the value of the index queuehead. If the value of queueHead indicates that there is room in the front of the array, then when queueTail gets to the last array position, we can slide all of the queue elements toward the first array position. This solution is good if the queue size is very small; otherwise, the program might execute more slowly. The "drifting queue" problem can also be solved by pretending that the array is circular and so allow the queue to continue directly from the highest-numbered position in the array to the lowest-numbered position. 101 111 121 196 197 198 1991 198) 1991 to) Figure-2: Circular Array for Queue Implementation This is easily implemented through use of the modulus operator (denoted by % in C++). In this way, positions in the array are numbered from 0 through maxQueueSize -1, and position maxqueuesize - 1 is defined to immediately precede position (which is equivalent to position maxQueue Size % naXQueueSize). Now we have the following queue: (01 111 121 196) 1971 198) 1991 X queuehead = 98 queue Tail 99 After the en-queue operation with a value 'Z', the queue is updated as follows 101 111 121 196 197 198 1991 2 x Y queue Head 98 queue Tailo Updation in queuehead and queueTail in case of circular array- Because the array containing the queue is circular, we can use the following statement to advance queueTail whenever a new element in added in the queue to the next array position: queueTail - (queueTail + 1) % maxQueueSize; If queuetail