Basic Operations
We have already seen the pseudocode for the two key operations for queues: enqueue
and 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 queue
object.
Constructor
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 start
and end
variables that hold indexes into myQueue
.
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 0
.
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 start
to -1
and end
to 0
.
Enqueue
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.
Dequeue
Like 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 start
and 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
The 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
isFull
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 start
or 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
and isFull
operates in constant time.
function ISFULL()
return START == END (1)
end function
isEmpty
The 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
This 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 start
and end
can “wrap around” the end of the array:
start == -1
—the queue is empty, andsize = 0
,start == end
—the queue is full, andsize
equals the capacity of the array,start < end
—size = end – start
, andstart > 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
The doubleCapacity
operation doubles the size of the array holding our queue. 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. 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
start
andend
variables to point at the correct elements, then - Point the
myQueue
array 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 myQueue
into 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 size
and dequeue
functions to get access to each item in the queue in order. Once we have copied the items from myQueue
to newQueue
, we simply need to set the start
and end
variables in line 5 and 6, and then set myQueue = newQueue
in line 7 to complete the process.
The 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
The 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 myQueue
to 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
Like the doubleCapacity
operation, 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
The 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 "Wildcats"
.
Notice that we must read the queue array from start
to 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 start
and 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 output
string.
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
The toString
function includes a loop that, at most, looks at each element in myQueue
; therefore, toString
executes in order $N$ time.