[Queue] [Chris Gerber, Harvard University] This is CS50, CS50.TV] One useful data structure for storing an ordered collection of elements is a queue. It is used when the elements need to be removed in the same order as they were added. This concept is referred to as FIFO, which is an acronym for first in, first out. To help visualize this, it may be useful to picture a checkout line at a store. As people arrive, they wait at the back of the line. The cashier then takes turns serving the customers at the front, who then exit the line one at a time. In computer science, we refer to the front of the queue as the head and the back as the tail. An example of when we might use this in an application is a waitlist for class enrollments. As seats become available in the class, the person at the head of the waiting list is provided the opportunity to enroll in the class. A queue can be constructed using any collection that stores data in order, such as an array or a linked list. Along with the collection to store the items in the queue, we also need a method to add items at the end of the queue, which is called enqueuing, and another to remove an item from the head of the queue, which is called dequeuing. It is often useful to include another method to return the current length of the queue as well as a method to check if the queue is empty. Let's look at how we might implement a queue of integers in C, using an array for the collection of elements. First, we create a structure called queue to hold our variables. We will use a fixed-size 0 index array of integers to store the elements. We will also include a variable called head that stores the index of the element that is currently at the head of the queue. A third variable, called length, will be used to keep track of the number of elements in the array. As an alternative, you could consider using a variable called tail to point to the last field element in the array. Before we write any more code, let's try out our design. Let's start with an empty array of length 0, with the head set to 0. Now let's enqueue 4 values--6, 2, 3, and 1. The length will now be 4, and the head will stay at 0. What happens if we dequeue a value? We will reduce the length to 3, set the head to 1, and return the value 6. That code might look like this. Here we have the dequeue function, which takes a pointer to the queue--q--and a pointer to the element, which is a type int. First we check the length of the queue to make sure it's more than 0, to ensure that there is an element to be dequeued. Then we look in the elements array, at the position head, and set the value of element to be the value at that position. Then we change the head to be the next index % the capacity. We then reduce the length of the queue by 1. Finally, we return true to indicate that the dequeue was successful. If we dequeue again, the length will become 2, the head will also become 2, and the return value will be 2. What happens if we enqueue another value such as a 7? As we were at the end of the queue, we will need to wrap around and store the value in element 0 of the array. Mathematically, this can be represented by adding the length to the index of the head and performing a modulus using the queue capacity. Here that is 2+2, which is 4 % 4, which is 0. Translating this idea to code we have this function. Here we see the enqueue function, which takes a pointer to the queue--q-- and takes the element to be enqueued, which is an integer. We next check to make sure that the capacity of the queue is still greater than the current length of the queue. Next, we store the element in the elements array at the index which is determined by the head + length % the capacity of the queue. We then increase the queue length by 1, and then return true to indicate that the enqueue function was successful. In addition to the two functions we've mentioned, there are two additional functions. First is the isempty function, which takes a pointer to the queue and verifies that the length is 0. The second is the length function, which also takes a pointer to the queue and returns the current length from the struct. This short overview has demonstrated one possible implementation of a queue. One of the limitations to this implementation is that the queue has a fixed maximum size. If we try to add more elements than the queue can hold, we may need to ignore the request and drop the element, or we may prefer to return some type of error. Using a linked list rather than an array would make it easier to dynamically size the queue. However, since we don't have direct access to the elements of a linked list, if we don't keep track of the tail, we would have to scan the entire linked list to get to the end each time. We could also consider using an array of another data type, such as structs, to create queues of more complex elements. Thinking back to our example of a class waitlist, these structures could represent the individual students. My name is Chris Gerber, and this is CS50. [CS50.TV] And returns-- >>One more time. And return true to indicate that--the queue was successful. --% the capacity of the queue-- It's going to be fun in edit. [Laughter]