Welcome!

This page is the main page for Queues

Subsections of Queues

What is a Queue?

A queue (pronounced like the letter “q”) data structure organizes data in a First In, First Out (FIFO) order: the first piece of data put into the queue is the first piece of data available to remove from the queue. A queue functions just like the line you would get into to go into a ballgame, movie, or concert: the person that arrives first is the first to get into the venue.

Students in a Queue Students in a Queue ^[https://commons.wikimedia.org/w/index.php?title=Special:CiteThisPage&page=File%3AReichstag_queue_2.JPG&id=379395710&wpFormIdentifier=titleform]

You might be thinking that this sounds a lot like the stack structure we studied a few modules back, with the exception that the stack was a Last in, First Out (LIFO) structure. If so, you are correct. The real difference between a stack and a queue is how we take data out of the data structure. In a stack, we put data onto the top of the stack and removed it from the top as well. With a queue, we put data onto the end (or rear) of the queue and remove it from the start (or front) of the queue.

Queues in the Real World

YouTube Video

The name for queues comes the word in British English used to describe a line of people. Instead of forming lines to wait for some service, British form queues. Thus, when we think of queues, often the first picture to come to mind is a group of people standing in a line. Of course, this is exactly how a computer queue operates as well. The first person in line gets served first. If I get into line before you do, then I will be served before you do.

Railway Cars Railway Cars ^[File:BNSF GE Dash-9 C44-9W Kennewick - Wishram WA.jpg. (2019, July 1). Wikimedia Commons, the free media repository. Retrieved 19:30, March 30, 2020 from https://commons.wikimedia.org/w/index.php?title=File:BNSF_GE_Dash-9_C44-9W_Kennewick_-_Wishram_WA.jpg&oldid=356754103.]

Of course, there are other examples of queues besides lines of people. You can think of a train as a long line of railway cars. They are all connected and move together as the train engine pulls them. A line of cars waiting to go through a toll booth or to cross a border is another good example of a queue. The first car in line will be the first car to get through the toll booth. In the picture below, there are actually several lines.

Cars Cars ^[File:El Paso Ysleta Port of Entry.jpg. (2018, April 9). Wikimedia Commons, the free media repository. Retrieved 19:30, March 30, 2020 from https://commons.wikimedia.org/w/index.php?title=File:El_Paso_Ysleta_Port_of_Entry.jpg&oldid=296388002.]

Queues in Code

YouTube Video

How do we implement queues in code? Like we did with stacks, we will use an array, which is an easily understandable way to implement queues. We will store data directly in the array and use special start and end variables to keep track of the start of the queue and the end of the queue.

The following figure shows how we might implement a queue with an array. First, we define our array myQueue to be an array that can hold 10 numbers, with an index of 0 to 9. Then we create a start variable to keep track of the index at the start of the queue and an end variable to keep track of the end of the array.

Empty Queue Empty Queue

Notice that since we have not put any items into the queue, we initialize start to be -1. Although this is not a legal index into the array, we can use it like we did with stacks to recognize when we have not yet put anything into the queue. As we will see, this also makes manipulating items in the array much simpler. However, to make our use of the array more efficient, -1 will not always indicate that the queue is empty. We will allow the queue to wrap around the array from the start index to the end index. We’ll see an example of this behavior later.

When we want to enqueue an item into the queue, we follow the simple procedure as shown below. Of course, since our array has a fixed size, we need to make sure that we don’t try to put an item in a full array. Thus, the precondition is that the array cannot be full. Enforcing this precondition is the function of the if statement at line 1. If the array is already full, then we’ll throw an exception in line 2 and let the caller handle the situation. Next, we store item at the end location and then compute the new value of end in line 4. Line 4 uses the modulo operator % to return the remainder of the division of $(\text{end} + 1) / \text{length of myQueue}$. In our example, this is helpful when we get to the end of our ten-element array. If end == 9 before enqueue was called, the function would store item in myQueue[9] and then line 4 would cause end to be $(9 +1) % 10$ or $10 % 10$ which is simply $0$, essentially wrapping the queue around the end of the array and continuing it at the beginning of the array.

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

Given our initial configuration above, if we performed an enqueue(7) function call, the result would look like the following.

Queue with 1 Element Queue with 1 Element

Notice that the value 7 was stored at myQueue[0] in line 3, end was updated to 1 in line 4, and start was set to 0 in line 7. Now, let’s assume we continue to perform enqueue operations until myQueue is almost filled as shown below.

Queue with 9 Elements Queue with 9 Elements

If at this point, we enqueue another number, say -35, the modulo operator in line 4 would help us wrap the end of the list around the array and back to the beginning as expected. The result of this function call is shown below.

Queue with 10 Elements Queue with 10 Elements

Now we have a problem! The array is full of numbers and if we try to enqueue another number, the enqueue function will raise an exception in line 2. However, this example also gives us insight into what the isFull condition should be. Notice that both start, and end are pointing at the same array index. You may want to think about this a little, but you should be able to convince yourself that whenever start == end we will be in a situation like the one above where the array is full, and we cannot safely enqueue another number.

To rectify our situation, we need to have a function to take things out of the queue. We call this function dequeue, which returns the item at the beginning of the queue (pointed at by start) and updates the value of start to point to the next location in the queue. The pseudocode for the dequeue is shown below.

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

Line 1 checks if the queue is empty and raises an exception in line 2 if it is. Otherwise, we copy the item at the start location into item at line 3 and then increment the value of start by 1, using the modulo operator to wrap to the beginning of the array if needed in line 4. However, if we dequeue the last item in the queue, we will actually run into the same situation that we ran into in the enqueue when we filled the array, start == end. Since we need to differentiate between being full or empty (it’s kind of important!), we reset the start and end values back to their initial state when we dequeue the last item in the queue. That is, we set start = -1 and end = 0. This way, we will always be able to tell the difference between the queue being empty or full. Finally, we return the item to the calling function in line 8.

Basic Operations

YouTube Video

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:

  1. start == -1—the queue is empty, and size = 0,
  2. start == end—the queue is full, and size equals the capacity of the array,
  3. start < end—size = end – start, and
  4. 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

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:

  1. Create a new array with twice the capacity of the existing array,
  2. Copy the contents of original array into the new array,
  3. Update the start and end variables to point at the correct elements, then
  4. 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".

Queue Containing Wildcats Queue Containing 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.

Using Operations

The following table shows an example of how to use the above operations to create and manipulate a queue. It assumes the steps are performed sequentially and the result of the operation is shown.

Step Operation Effect
1 Constructor Creates an empty queue of capacity 3. Empty Queue Empty Queue
2 isFull() Returns false since start is not equal to end Empty Queue Empty Queue
3 isEmpty() Returns true since start is equal to -1. Empty Queue Empty Queue
4 enqueue(1) Places item 1 onto queue at the end and increments end by 1. Queue with 1 Element Queue with 1 Element
5 enqueue(2) Places item 2 onto queue at the end and increments end by 1. Queue with 2 Elements Queue with 2 Elements
6 enqueue(3) Places item 3 onto queue at the end and sets end to end+1 modulo the size of the array (3). The result of the operation is 0, thus end is set to 0. Queue with 3 Elements Queue with 3 Elements
7 peek() Returns the item 1 on the start of the queue but does not remove the item from the queue. start and end are unaffected by peek. Queue with 3 Elements Queue with 3 Elements
8 isFull() Returns true since start is equal to end Queue with 3 Elements Queue with 3 Elements
9 dequeue() Returns the item 1 from the start of the queue. start is incremented by 1, effectively removing 1 from the queue. Queue with 2 Elements Queue with 2 Elements
10 dequeue() Returns the item 2 from the start of the queue. start is incremented by 1, effectively removing 2 from the queue. Queue with 1 Element Queue with 1 Element
11 enqueue(4) Places item 4 onto queue at the end and increments end. Queue with 2 Elements Queue with 2 Elements
12 dequeue() Returns the item 3 from the start of the queue. start is set to start+1 modulo the size of the array (3). The result of the operation is 0, thus start is set to 0. Queue with 1 Elements Queue with 1 Elements
13 dequeue() Returns the item 4 from the start of the queue. start is incremented by 1, and since start == end, they are both reset to -1 and 0 respectively. Queue with 0 Elements Queue with 0 Elements
14 isEmpty() Returns true since start is equal to -1. Queue with 0 Elements Queue with 0 Elements

Using a Queue

YouTube Video

Queues are useful in many applications. Classic real-world software which uses queues includes the scheduling of tasks, sharing of resources, and processing of messages in the proper order. A common need is to schedule tasks to be executed based on their priority. This type of scheduling can be done in a computer or on an assembly line floor, but the basic concept is the same.

Let’s assume that we are putting windshields onto new cars in a production line. In addition, there are some cars that we want to rush through production faster than others. There are actually three different priorities:

  1. High priority: these cars have been ordered by customers who are waiting for them.
  2. Medium priority: these cars have been ordered as “fleet cars” for specific companies.
  3. Low priority: these cars are cars used to fill dealer inventories.

Ideally, as cars come to the windshield station, we would be able to put their windshields in and send them to the next station before we received the next car. However, this is rarely the case. Since putting on windshields often requires special attention, cars tend to line up to get their windows installed. This is when their priority comes into account. Instead of using a simple queue to line cars up first-come, first-served in FIFO order, we would like to jump high priority cars to the head of the line.

While we could build a sophisticated queueing mechanism that would automatically insert cars in the appropriate order based on priority and then arrival time, we could also use a queue to handle each set of car priorities. A figure illustrating this situation is shown below. As cars come in, they are put in one of three queues: high priority, medium priority, or low priority. When the windshield station completes a car it then takes the next car from the highest priority queue.

Car Windshield Installation Model Car Windshield Installation Model

The interesting part of the problem is the controller at the windshield station that determines which car will be selected to be worked on next. The controller will need to have the following interface:

function receiveCar(car, priority)
 // receives a car from the previous station and places into a specific queue

function bool isEmpty()
 // returns true if there are no more cars in the queue

function getCar() returns car
 // retrieves the next car based on priority

Using this simple interface, we will define a class to act as the windshield station controller. It will receive cars from the previous station and get cars for the windshield station.

We start by defining the internal attributes and constructor for the Controller class as follows, using the Queue functions defined earlier in this module. We first declare three separate queues, one each for high, medium, and low priority cars. Next, we create the constructor for the Controller class. The constructor simply initializes our three queues with varying capacities based on the expected usage of each of the queues. Notice, that the high priority queue has the smallest capacity while the low priority queue has the largest capacity.

class Controller
    declare HIGH as a Queue
    declare MEDIUM as a Queue
    declare LOW as a Queue

    function Controller()
        HIGH = new Queue(4)
        MEDIUM = new Queue(6)
        LOW = new Queue(8)
    end function

Next, we need to define the interface function as defined above. We start with the receiveCar function. There are three cases based on the priority of the car. If we look at the first case for priority == high, we check to see if the high queue is full before calling the enqueue function to place the car into the high queue. If the queue is full, we raise an exception. We follow the exact same logic for the medium and low priority cars as well. Finally, there is a final else that captures the case where the user did not specific either high, medium, or low priority. In this case, an exception is raised.

function receiveCar(CAR, PRIORITY)
    if PRIORITY == high
        if HIGH.isFull()
            raise exception
        else
            HIGH.enqueue(CAR)
        end if
    else PRIORITY == medium
        if MEDIUM.isFull()
            raise exception
        else
            MEDIUM.enqueue(CAR)
        end if
    else PRIORITY == low
        if LOW.isFull()
            raise exception
        else
            LOW.enqueue(CAR)
        end if
    else
        raise exception
    end if
end function

Now we will define the isEmpty function. While we do not include an isFull function due to the ambiguity of what that would mean and how it might be useful, the isEmpty function will be useful for the windshield station to check before they request another call via the getCar function.

As you can see below, the isEmpty function simply returns the logical AND of each of the individual queue’s isEmpty status. Thus, the function will return true if, and only if, each of the high, medium, and low queues are empty.

function isEmpty()
    return HIGH.isEmpty() and MEDIUM.isEmpty() and LOW.isEmpty()
end function

Finally, we are able to define the getCar function. It is similar in structure to the receiveCar function in that it checks each queue individually. In the case of getCar, the key to the priority mechanism we are developing is in the order we check the queues. In this case, we check them in the expected order from high to low. If the high queue is not empty, we get the car from that queue and return it to the calling function. If the high queue is empty, then we check the medium queue. Likewise, if the medium queue is empty, we check the low queue. Finally, if all of the queues are empty, we raise an exception.

function getCar()
    if not HIGH.isEmpty()
        return HIGH.dequeue()
    else not MEDIUM.isEmpty()
        return MEDIUM.dequeue()
    else not LOW.isEmpty()
        return LOW.dequeue()
    else
        raise exception
    end if
end function

Windshield Station Example

The following example shows how the Controller class would work, given specific calls to receiveCar and getCar.

Step Operation Effect
1 Constructor Creates 3 priority queues. Empty Queue Empty Queue
2 getCar() Raises an exception since all three queues will be empty. Empty Queue Empty Queue
3 receiveCar(a, low) Places car a into the low queue. Queue with 1 car Queue with 1 car
4 receiveCar(b, low) Places car b into the low queue. Queue with 2 cars Queue with 2 cars
5 receiveCar(f, high) Places car f into the high queue. Queue with 3 cars Queue with 3 cars
6 receiveCar(d, medium) Places car d into the medium queue. Queue with 4 cars Queue with 4 cars
7 receiveCar(g, high) Raises an exception since the high queue is already full. Queue with 4 cars Queue with 4 cars
8 receiveCar(e, medium) Places car e into the medium queue. Queue with 5 cars Queue with 5 cars
9 getCar() Returns car f from the high queue. Queue with 4 cars Queue with 4 cars
10 getCar() Returns car d from the medium queue. Queue with 3 cars Queue with 3 cars
11 getCar() Returns car e from the medium queue. Queue with 2 cars Queue with 2 cars
12 getCar() Returns car a from the low queue. Queue with 1 car Queue with 1 car
13 getCar() Returns car b from the low queue. Queue with 0 cars Queue with 0 cars
14 getCar() Raises an exception since there are no more cars available in any of the three queues. Queue with 0 cars Queue with 0 cars
15 isEmpty() Returns true since all three queues are empty. Queue with 0 cars Queue with 0 cars

Queues Summary

In this module we looked at the queue data structure. Queues are a “first in first out” data structure that use two main operations, enqueue and dequeue, to put data into the queue and to remove data from the queue. Queues are useful in many applications including the scheduling of tasks, sharing of resources, and processing of messages in the proper order.

5.18.0

Last modified by: Russell Feldhausen Aug 17, 2021