Queues

Notes

A queue is a data structure that is similar in spirit to a fair line. As you can see in this photo, the first dog in line can expect to be the first to pee on the tree.

Similarly, with queues, the first element inserted will be the first element retrieved. We'll refer to this pattern of insertion and retrieval as "first-in, first-out," or FIFO for short.

A queue's enqueue function places a new element at a queue's "tail" end, while dequeue retrieves the element at a queue's "head" (i.e., front). ***Be aware that you may see variations on the names of these functions in different textbooks as they aren't as standardized as push and pop are for stacks.***

Like stacks (and unlike arrays), queues typically don't allow access to elements in the middle.

This is one way to define a queue for char*s.

head is the index of the queue's head element. We'll adjust it as we dequeue elements.

Why would we need to keep track of the head of our queue? Why not simply consider the element at strings[0] to be the head and the element at strings[size - 1] to be the tail?

This would require us to shift all of the elements from strings[1] to strings[size - 1] down by one position every time we call dequeue, which is a big waste of time especially if we've got a long queue!

CAPACITY is a constant and strings is a statically-sized array of char*s that you'll use for storing the char* elements.

size stores the number of elements currently in the queue. You'll need to adjust it appropriately so that you can track the location of the "tail" of the queue.

Why is this design suboptimal? It imposes a limit on the size of the queue.

To enqueue an element, first make sure that the array isn't full by comparing size to CAPACITY.

If size < CAPACITY, store the element in the next available open slot, which should be at index [(head + size) % CAPACITY].

Don't forget to increment size!

To dequeue an element, first make sure that there are elements in the array by comparing size to 0.

If size > 0, the element at the head of the list is the one you'll want to dequeue.

Don't forget to reposition head and decrement size!

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Enqueue and Dequeue

Implement enqueue and dequeue functions for this queue.

jharvard@run.cs50.net (~): ./a.out
Enqueueing 10 strings...done!
Making sure that the queue size is indeed 10...good!
Making sure that enqueue() now returns false...good!
Dequeueing everything...done!
Making sure that dequeue() returned values in FIFO order...good!
Making sure that the queue is now empty...good!
Making sure that dequeue() now returns NULL...good!
Making sure that the head wraps around appropriately...good!

********
Success!
********

Try out some pseudocode here!
/*************************************************************************
 * queue.c
 *
 * Implements a simple queue structure for char*s.
 ************************************************************************/

// for strdup() in the testing code
#define _XOPEN_SOURCE 500

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// the capacity of the queue
#define CAPACITY 10

// a queue
typedef struct
{
    // the index of the first element in the queue
    int head;

    // storage for the elements in the queue
    char* strings[CAPACITY];

    // the size of the queue
    int size;
}
queue;

// declare a queue (as a global variable)
queue q;

/**
 * Puts a new element into the queue into the "end" of the data structure
 * so that it will be retrived after the other elements already in the
 * queue.
 */
bool enqueue(char* str)
{
    // TODO
}

/**
 * Retrieves ("dequeues") the first element in the queue, following the
 * the "first-in, first-out" (FIFO) ordering of the data structure.
 * Reduces the size of the queue and adjusts the head to the next element.
 */
char* dequeue(void)
{
    // TODO
}

/**
 * Implements some simple test code for our queue
 */
int main(void)
{
    // initialize the queue
    q.head = 0;
    q.size = 0;

    printf("Enqueueing %i strings...", CAPACITY);
    for (int i = 0; i < CAPACITY; i++)
    {
        char str[12];
        sprintf(str, "%i", i);
        enqueue(strdup(str));
    }
    printf("done!\n");

    printf("Making sure that the queue size is indeed %i...", CAPACITY);
    assert(q.size == CAPACITY);
    printf("good!\n");

    printf("Making sure that enqueue() now returns false...");
    assert(!enqueue("too much!"));
    printf("good!\n");

    printf("Dequeueing everything...");
    char* str_array[CAPACITY];
    for (int i = 0; i < CAPACITY; i++)
    {
        str_array[i] = dequeue();
    }
    printf("done!\n");

    printf("Making sure that dequeue() returned values in FIFO order...");
    for (int i = 0; i < CAPACITY; i++)
    {
        char str[12];
        sprintf(str, "%i", i);
        assert(strcmp(str_array[i], str) == 0);
        free(str_array[i]);
    }
    printf("good!\n");

    printf("Making sure that the queue is now empty...");
    assert(q.size == 0);
    printf("good!\n");

    printf("Making sure that dequeue() now returns NULL...");
    assert(dequeue() == NULL);
    printf("good!\n");

    printf("Making sure that the head wraps around appropriately...");
    for (int i = 0; i < CAPACITY; i++)
    {
        assert(enqueue("cs50!"));
    }

    // to make sure that they adjust the head pointer appropriately, we'll
    // enqueue and dequeue a bunch of times to make sure they don't just
    // walk off the end of the char* strings[] array
    for (int i = 0; i < CAPACITY * 10; i++)
    {
        for (int j = 0; j < CAPACITY / 2; j++)
        {
            assert(dequeue());
        }
        for (int j = 0; j < CAPACITY / 2; j++)
        {
            assert(enqueue("cs50!"));
        }
    }
    printf("good!\n");

    printf("\n********\nSuccess!\n********\n");

    return 0;
}

Videos

study50 video thumbnail

Monday, Week 6

An introduction to data structures