A noted exception to this is Python, which does allow you to directly extend an array. Unfortunately, most programming languages (like Java) do not simply let you double the size of the array. If we started with an array of size 4, the doubleCapacity operation will result in an array of size 8 with the contents of our original array stored in it. The doubleCapacity operation doubles the size of the array holding our queue. Once again, this is a constant time function. Therefore, we can simply use an else statement to capture the last case in line 7. Notice that the conditions that are checked in lines 3 and 5 ensure that start must be greater than end. Return capacity of MYQUEUE – START + END (7) For the dequeue operation, our precondition is that the queue must not already be empty, which is detected by the isEmpty function in line 1. However, before we can do that, we need to validate our precondition. It simply takes the first item from the start of the queue and returns it. Like enqueue, we have already seen the dequeue operation. The enqueue function does not return a value.īecause there are no loops in the enqueue function, the function operates in constant time regardless of the size of the array or the number of items in it. If start = 1, then we know the queue is empty, so we set start = 0. Next, we check for the condition of an empty queue. Then we increment end, using the modulo operator to wrap end to point to the beginning of the array if warranted. Once our precondition is validated, we simply increment and store the item into the array at index end. In this module we assume the caller must provide a capacity value, which must be greater than 0. Or, we could allow the user to pass in a positive integer to set the size. We could just use a default size for the array. Since we are using an array for our queue, we will need to know how big to make the array in our constructor. As we discussed above, the attributes include the myQueue array and the start and end variables that hold indexes into myQueue. The main responsibility of the constructor is to initialize all the attributes in the queue class. But first, let’s talk about the constructor for the queue class and what it must do to properly set up a queue object. We will discuss each of these operations. size-returns the number of items in the queue.isFull-returns true if our queue array is full, and.isEmpty-returns true if there are no items in the queue,.peek-returns the item at the start of the queue without removing it,.dequeue-removes and returns the item at the start of the queue,. enqueue-places an item on the end of the queue,.However, there are several others that make the queue data structure much easier to use: We have already seen the pseudocode for the two key operations for queues: enqueue and dequeue.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |