We have already seen the pseudocode for the two key operations for queues:
dequeue. However, there are several others that make the queue data structure much easier to use:
- enqueue—places an item on the end of the queue,
- dequeue—removes and returns the item at the start of the queue,
- peek—returns the item at the start of the queue without removing it,
- isEmpty—returns true if there are no items in the queue,
- isFull—returns true if our queue array is full, and
- size—returns the number of items in the queue.
We will discuss each of these operations. But first, let’s talk about the constructor for the
queue class and what it must do to properly set up a
The main responsibility of the constructor is to initialize all the attributes in the
queue class. As we discussed above, the attributes include the
myQueue array and the
end variables that hold indexes into
Since we are using an array for our queue, we will need to know how big to make the array in our constructor. There are two options. We could just use a default size for the array. Or, we could allow the user to pass in a positive integer to set the size. In this module we assume the caller must provide a
capacity value, which must be greater than
function QUEUE (CAPACITY) if CAPACITY is not an integer then (1) throw exception (2) else if CAPACITY <= 0 then (3) throw exception (4) end if MYQUEUE = new array of size capacity (5) START = -1 (6) END = 0 (7) end function
The first thing we do in the code is to check to make sure that
capacity is actually an integer that is greater than
0. Essentially, this is our precondition for the method. If our precondition is not met, we throw an exception. (If we are using a typed language such as Java, we can enforce our precondition by requiring that
capacity be of type
integer instead of explicitly checking it in the code.) Once we’ve validated our precondition, we create a new array of size
capacity for the
myQueue array and set the attribute
We have already discussed the
enqueue operation and seen it in operation above. In the pseudocode below, we see that we must first check to ensure that the queue is not already full. Again, this is our precondition.
function ENQUEUE (item) if ISFULL() then (1) raise exception (2) end if MYQUEUE[END] = ITEM (3) END = (END + 1) % length of MYQUEUE (4) if START == -1 (5) START = 0 (6) end if end function
Once our precondition is validated, we simply increment and store the
item into the array at index
end. Then we increment
end, using the modulo operator to wrap
end to point to the beginning of the array if warranted. Next, we check for the condition of an empty queue. If
start = 1, then we know the queue is empty, so we set
start = 0. The
enqueue function does not return a value.
Because 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.
enqueue, we have already seen the
dequeue operation. It simply takes the first item from the
start of the queue and returns it. However, before we can do that, we need to validate our precondition. 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.
function DEQUEUE () if ISEMPTY() then (1) raise exception (2) end if ITEM = MYQUEUE[START] (3) START = (START + 1) % length of MYQUEUE (4) if START == END (5) START = -1 (6) END = 0 (7) end if return ITEM (8) end function
Once we have validated our precondition, we simply copy the item from the
myQueue[start] in line 3 and increment
start. Again, we use the modulo operator in line 4 to wrap
start back to
0 if it is needed. Next, we check to see if the
myQueue is empty, and, if it is, reset the values of
end back to their initial values. Finally, we return the item to the calling function in line 8. Like the
enqueue operation, the
dequeue function operates in constant time.
peek operation returns the item at the start of the queue, without removing it from the array. Like the
dequeue operation it has the precondition that the queue must not be empty. The pseudocode for the
peek operation is shown below. It is also a constant time operation.
function PEEK() (1) if ISEMPTY() then (2) raise exception (3) else return MYQUEUE[START] (4) end if end function
To allow the calling program to detect when the queue is full, we define an
isFull operation. Notice that code external to the
queue class cannot access the value of
end so it cannot simply check if
start == end on its own. In this case, the operation is very simple as we only need to return the Boolean value of
start == end as shown below. There is no precondition for
isFull operates in constant time.
function ISFULL() return START == END (1) end function
isEmpty operation is very similar to the
isFull operation except that we return the Boolean value of the condition
start == -1 instead of
start == end.
function ISEMPTY() return START == -1 (1) end function
size method returns the number of items in the queue. However, it is not as straightforward as it might sound. Actually, there are several cases that we must consider, based on the fact that both
end can “wrap around” the end of the array:
start == -1—the queue is empty, and
size = 0,
start == end—the queue is full, and
sizeequals the capacity of the array,
start < end—
size = end – start, and
start > end—
size = capacity of array - start + end + 1.
Thus, in our function, we simply need to check four conditions.
function SIZE() if START = -1 (1) return 0 (2) else if START == END (3) return capacity of MYQUEUE (4) else if START < END (5) return END – START (6) else return capacity of MYQUEUE – START + END (7) end if end function
Notice that the conditions that are checked in lines 3 and 5 ensure that
start must be greater than
end. Therefore, we can simply use an
else statement to capture the last case in line 7. Once again, this is a constant time function.
doubleCapacity operation doubles the size of the array holding our queue. If we started with an array of size
doubleCapacity operation will result in an array of size
8 with the contents of our original array stored in it. Unfortunately, most programming languages (like Java) do not simply let you double the size of the array. A noted exception to this is Python, which does allow you to directly extend an array.
In a traditional programming language, the easiest way to accomplish the
doubleCapacity operation is to complete the following steps:
- Create a new array with twice the capacity of the existing array,
- Copy the contents of original array into the new array,
- Update the
endvariables to point at the correct elements, then
- Point the
myQueuearray at the new array.
The pseudocode for the
doubleCapacity operation is shown below.
function DOUBLECAPACITY() NEWQUEUE = new array of MYQUEUE capacity * 2 (1) LENGTH = SIZE() (2) for I = 0 to LENGTH - 1 (3) NEWQUEUE[I] = DEQUEUE() (4) end for START = 0 (5) END = LENGTH (6) MYQUEUE = NEWQUEUE (7) end function
In the function, we create the new array in line 1 and then save the total number of items in the array for use later in line 2. Next, we use a
for loop in lines 3 and 4 to copy the contents from
newQueue. Since the contents of
myQueue are not necessarily stored neatly in the array (i.e., from $0$ to $n$), it is easier for us to use the existing
dequeue functions to get access to each item in the queue in order. Once we have copied the items from
newQueue, we simply need to set the
end variables in line 5 and 6, and then set
myQueue = newQueue in line 7 to complete the process.
doubleCapacity operation is not a constant time operation since copying the contents of the original array into the new array requires us to copy each item via a loop. This requires $N$ steps. Thus, we would say that
doubleCapacity runs in “order $N$” time.
halveCapacity operation is similar to the
doubleCapacity operation except that we now have a precondition. We must make sure that when we reduce the space for storing the queue that we still have enough space to store all the items currently in the queue. For example, if we have 10 items in a queue with a capacity of 16, we can’t successfully perform
halveCapacity. Doing so would only leave us a queue with a capacity of 8 and we would not be able to fit all 10 items in the new queue.
The pseudocode for the
halveCapacity function is shown below, with the precondition being checked in line 2. Once we create
newQueue to be half the capacity of
myQueue in line 4, the remainder of the function is exactly the same as the
doubleCapacity function, since lines 5-10 are just concerned with copying the items from
newQueue and setting the associated variables.
function HALVECAPACITY() if SIZE() > MYQUEUE capacity / 2 then (2) throw exception (3) end if NEWQUEUE = new array of MYQUEUE capacity / 2 (4) LENGTH = SIZE() (5) for I = 0 to LENGTH - 1 (6) NEWQUEUE[I] = DEQUEUE() (7) end for START = 0 (8) END = LENGTH % length of NEWQUEUE (9) MYQUEUE = NEWQUEUE (10) end function
halveCapacity is not a constant time operation since copying the contents of the original array requires us to loop $N$ times. So,
halveCapacity runs in “order $N$” time.
toString function returns a string that concatenates the strings representing all the items stored in an array. In most programming languages, each object class must implement the
toString operation. For instance, in the queue below where each item is a character, if we called
myQueue.toString(), we would expect to be returned the string
Notice that we must read the queue array from
end to get the proper output string.
In the pseudocode below we first create an empty string called
output in line 1. Then, we create a loop in line 2 that counts using
i the number of items in the queue from
0 to the
size of the queue. However, we can’t use this counter
i to directly index into the array, since
end may be almost anywhere in the array. Thus, we use
i to compute
next in line 3, which we will use as our index into the array. Our index
i should begin with
start and finish with the
end value, which can also be computed as
start + size() – 1 modulo the capacity of
myQueue. We then use the index
next in line 4 to select the appropriate element of
myQueue to append to our output string. Once the loop ends, we simply return our
function TOSTRING() OUTPUT = "" (1) for I = 0 to SIZE() - 1 (2) NEXT = (START + I) % MYQUEUE capacity (3) OUTPUT = OUTPUT + MYQUEUE[next].TOSTRING() (4) end for (5) return OUTPUT (6) end function
toString function includes a loop that, at most, looks at each element in
toString executes in order $N$ time.