Tangible Computing
15. Queues



15.1 What is a Queue?

A queue is a collection of items that is a First-In-First-Out (FIFO) data structure. This means that whenever an element is added to the queue, it is added to the end of the queue. When removing an element from the list, only the first element added to the list can be removed (aka the first one in must be the first one out). The queue data structure is a natural analogy to real-life queues.

You might ask yourself: "Why do I care about queues? If it is just an array, why not use an array"? The main reason to use a queue, and other data structures like stacks (which are Last-In-First-Out data structures), is that you do not always need the indexing complexity of an array. For many situations, you might simply need to be able to remove the oldest element and to add a new element.

Imagine that you care about scheduling jobs for a processor. You want the job that was submitted first to be processed first, as it should have priority over jobs submitted later, however, you do not want to keep track of indices of jobs. With a queue, you can simply say "Add this job to the list" and "Give me the next job", without dealing with array indexing. Moreover, we will also see that we can implement this simplified list functionality more efficiently without using arrays.

15.2 Implementing a queue in C using arrays

There are several ways to implement a queue: we say a queue is an abstract data type. An abstract data type (or ADT) is defined by the operations that may be performed on it and by constraints on the effects and costs of those operations. A queue needs to have an add method to add a new item to the tail, and and a remove method that removes and returns the oldest element in the queue (at the head). Ideally these operations should be O(1).

We will start by using arrays to implement an integer queue.

code/Queues/array/queue.h

    /*
        Queue of int, implemented by a circular buffer in array
    */
     
    #ifndef _queue_h
    #define _queue_h
     
    /* queue Abstract Data Type
     
     list points to an array that contains the elements in queue
     
     length stores the number of items currently in the queue
     
     max_length stores the total space allocated for the queue list
     
     head_index stores the index of the current head of the list,
            which changes as items are removed from the list
     
     Invariant:  The head of the queue starts at position list[head_index],
        and goes up to position list[head_index + length -1].  In the
        event that head_index + length -1 > max_length-1, the list wraps
        around to position 0.
     
        Thus the current items in the queue are at positions
            head_index, head_index+1, ..., max_length-1, 
                0, ..., (length-1) % max_length
    */
    typedef struct {
        int *list;
        int length;
        int max_length;
        int head_index;
    } queue;
     
    void initializeQueue(queue *q, int size_hint);
    void addElement(queue *q, int val);
    int removeElement(queue *q);
     
    #endif


The struct queue contains all the information we will need for maintaing the FIFO data structure. In the below code, we see how to add and remove elements from the queue, which are the only two required operations on the abstract data type. We also need a function to increase the size of the list in the queue, if we add more elements than we originally allocated in the queue.


code/Queues/array/queue.c

    /* Implementation of Queue ADT using circular list in an array */
    #include "queue.h"
    #include <stdlib.h>
    #include <assert.h>
     
    /* 
        Take a declared empty queue structure and initialize it.
     
        Warning: Do not call on an existing queue.  Will get a 
        memory leak.
    */
    void initializeQueue(queue *q, int size_hint) {
            assert(q != 0);
     
            q->max_length = size_hint;
            q->length = 0;
            q->head_index = 0;
            q->list = malloc(q->max_length*sizeof(int));
            assert(q->list != 0);
        }
     
    /* internal method to increase size of queue */
    void increaseSize(queue *q, int increase) {
        int new_max_length = q->max_length + increase;
     
        int * bigger_list = malloc(new_max_length * sizeof(int));
        assert(bigger_list != 0);
     
        for (int i = 0; i < q->max_length; i++) {
            bigger_list[i] = q->list[i];
            }
     
        free(q->list);
        q->list = bigger_list;
        q->max_length = new_max_length;
        }
     
     
    /*
        Add the element val to the tail of the queue q
    */
    void addElement(queue *q, int val) {
        if (q->length == q->max_length) {
            /* double the current length of the queue */
            increaseSize(q, q->max_length);
            }
     
        int new_index = (q->head_index + q->length) % q->max_length;
        q->length++;
     
        q->list[new_index] = val;
        }
     
    /*
        Remove and return the element at the head of queue q
         
        Pre-condition: q->length > 0
    */
    int removeElement(queue *q) {
        assert(q->length > 0);
            
        // Obtain the current head of the list
        int current_head_item = q->list[q->head_index];
     
        q->length--;
     
        /* 
            Since the head has been removed, shift the head index to
            the next position.  If we are at the end of the list, 
            then we wrap around to the beginning.
        */
        if (q->length == 0) {
            /* empty queues start at position 0 */
            q->head_index = 0; 
        } else { 
            q->head_index = (q->head_index + 1) % q->max_length; 
            }
     
        return current_head_item;
        }


Here is a test program for the queue ADT we just implemented.

code/Queues/array/testq.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "queue.h"
     
    /*
        print the contents of a queue from head to tail going left 
        to right.
     
        NOTE:  This code is fragile as it inspects the internal 
        representation of the queue.
     
    */
    void printf_queue(queue *q) {
        int pos = q->head_index;
        for (int i=0; i < q->length; i++) {
            printf("%d ", q->list[pos]);
            pos = (pos + 1) % q->max_length;
            }
    }
     
    int main(int argc, char *argv[]) {
        /* test harness */
        int tests_passed = 0;
        int tests_failed = 0;
     
        /* create a queue instance and initialize it */ 
        queue q_instance;
     
        /* create a handle to the queue so that we can manipulate it
        without having to put the & in front all the time */
     
        queue *qp = &q_instance;
     
        printf("Initializing queue\n");
        initializeQueue(qp, 20);
     
        /* how do we see if queue was propery initialized? */
        
        /* add and remove one element */
        int e1 = 42;
        
        addElement(qp, e1);
        printf("Test 1: ");
        printf_queue(qp);
        printf("\n");
     
        /* length should have gone up by one */
     
        if ( qp->length != 1 ) {
            printf("Test 1 failed, length %d should be 1\n", 
                qp->length);
            tests_failed++;
            }
        else {
            printf("Test 1 passed.\n");
            tests_passed++;
            }
        
     
        printf("Test 2: ");
        int e2 = removeElement(qp);
        printf_queue(qp);
        printf("\n");
     
        if ( qp->length != 0 ) {
            printf("Test 2.1 failed, length %d should be 0\n", 
                qp->length);
            tests_failed++;
            }
        else {
            printf("Test 2.1 passed.\n");
            tests_passed++;
            }
        
        if ( e1 != e2 ) {
            printf("Test 2.2 failed, e2 %d should equal e1 %d\n", 
                e2, e1);
            tests_failed++;
            }
        else {
            printf("Test 2.2 passed.\n");
            tests_passed++;
            }
     
        printf("Test 3: ");
        for (int i=1; i <= 10; i++) {
            addElement(qp, i);
            }
        printf_queue(qp);
        printf("\n");
        for (int i=1; i<= 10; i++) {
            e1 = removeElement(qp);
            if ( qp->length != 10-i ) {
                printf("Test 3.1 failed, length %d should be %d\n",
                    qp->length, 10-i);
                tests_failed++;
                }
            else {
                tests_passed++;
                }
            if ( e1 != i ) {
                printf("Test 3.2 failed, element %d should be %d\n",
                    e1, i);
                tests_failed++;
                }
            else {
                tests_passed++;
                }
            }
     
        
        /* a fatal test */
        if ( 0 ) {
            printf("Test 4: remove on empty queue\n");
            e2 = removeElement(qp);
            tests_failed++;
            }
     
        printf("Tests Passed: %d\n", tests_passed);
        printf("Tests Failed: %d\n", tests_failed);
        }


and its associated Makefile code/Queues/array/Makefile

    CFLAGS = -std=gnu99 -Wall -Werror
     
    all : testq
     
    # the queue implementation depends on the header also
    queue.o : queue.c queue.h
     
    # testq also depends on the queue library
    testq : testq.c queue.o 
            $(CC) $(CFLAGS) testq.c queue.o -o testq
     
    clean :
            rm -f queue.o testq


Exercise: We should not be inspecting the struct to determine the length of the queue. Add a length function for the ADT that returns the length of the queue.

Exercise: The test program printing function is fragile, as it needs to inspect and traverse the internal representation of the queue. Write a getElement function that gets the element at a given index in the queue, where 0 is the head of the queue, and length(q)-1 is the tail.

Exercise: Write a function that jumps into a specific index in the queue and removes the node that is at that position.

15.3 Implementing a queue in C using linked lists

Another way to implement a queue is to use the idea of linked lists. A linked list is a set of cells or nodes that are linked together using pointers to each other. Whenever we want to add a node to the linked list, we simply link it with the last pointer. With this implementation we do not have to worry about increasing the size of the array, because we can add as many nodes to the end of the linked list as we want. This implementation is important when we have limited memory size (such as on the Arduino) because we do not have to allocate extra space for every queue just in case it might get large.


As an example, imagine we have k different queues in a grocery store (for the deli, for the bakery, for the cashier, etc.). The length of the queues will be changing quite dynamically, with the largest queue at the deli at one point and then maybe another time at the cash. Instead of having to equally allocate some maximum amount of memory for each queue, memory can dynamically be allocated by using a linked list of only the current number of elements in each queue. In this way, the memory is allocated to the queue that needs it at any given time.

Now the question is: how do we link the nodes together with pointers to make the linked list?

code/Queues/linked/queue.h

    /*
        Queue of int, implemented by a linked list
    */
    #ifndef _queue_h
    #define _queue_h
     
    /*
        A linked list contains nodes which hold the information for 
        that node (val) and the pointer to the next node in the 
        list (next).
     
        When next is 0 (null pointer) there is no following cell.
    */
    typedef struct node {
        int val;
        struct node *next;
    } node;
     
    /*
        The queue is implemented by keeping a pointer to the head 
        node of a linked list.  To make adding nodes to the queue 
        efficient, we also have a pointer to the tail node of the 
        list.
     
        A queue is manipulated by passing around a pointer to its 
        queue struct.
    */
    typedef struct {
        node *head;
        node *tail;
        int length;
    } queue;
     
    void initializeQueue(queue *q, int size_hint);
    int length(queue *q);
    void addElement(queue *q, int val);
    int removeElement(queue *q);
    int getElement(queue *q, int index);
     
    #endif


code/Queues/linked/queue.c

    /*
        Implementation of queue Abstract Data Type (ADT)
    */
     
    #include <stdlib.h>
    #include <stdio.h>
    #include <assert.h>
    #include "queue.h"
     
    /* 
        Take a declared empty queue structure and initialize it.
     
        Warning: Do not call on an existing queue.  Will get a 
        memory leak.
    */
     
    void initializeQueue(queue *q, int size_hint) {
        q->head = 0;
        q->tail = 0;
        q->length = 0;
    }
     
    /*
        Get the current length of the queue
    */
    int length(queue *q) {
        return q->length;
        }
     
    /*
        Add the element val to the tail of the queue q
    */
     
    void addElement(queue *q, int val) {
        node * n = (node *) malloc(sizeof(node));
     
        // make sure malloc worked
        assert(n != 0);
     
        // initialze the new node to contain the value and have no next
        n->val = val;
        n->next = 0;
     
        // if there is stuff in the queue, add new node to end
        // if an empty queue, need to set up head.
        if (q->length != 0) {
                q->tail->next = n;
        } else {
                q->head = n;
        }
     
        // new node is at the tail
        q->tail = n;
        q->length++;
        }
     
    /*
        Get the element of the queue at position index,
        where the head of the queue is position 0, and the
        tail is at position length(q)-1
    */
    int getElement(queue *q, int index) {
        assert(0 <= index && index < q->length);
        return 0;
        }
        
    /*
        Remove and return the element at the head of queue q
     
        Pre-condition: q->length > 0
    */
     
    int removeElement(queue *q) {
        assert(q->length > 0);
        
        // get the value at the head
        int rval = q->head->val;
     
        // new head is the next one
        node *new_head = q->head->next;
     
        /* Now we can free the old head so that we don't leave unused 
           memory allocated
        */
        free(q->head);
     
        q->length--;
     
        // Now we can set the head to new_head
        q->head = new_head;
     
        // if queue is empty, we need to set tail also.
        if (q->length == 0) {
            q->tail = 0;
            }
     
        return rval;
        }


Here is a test program for the queue ADT we just implemented.

code/Queues/linked/testq.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "queue.h"
     
    /*
        print the contents of a queue from head to tail going left 
        to right.
     
        NOTE:  This code is fragile as it inspects the internal 
        representation of the queue.
     
        What we really want is:
        for (int i=0; i < length(q); i++) {
            printf("%d ", getElement(q, i));
            }
    */
    void printf_queue(queue *q) {
        node * cur = q->head;
        while( cur != 0 ) {
            printf("%d ", cur->val);
            cur = cur->next;
            }
        }
     
     
    int main(int argc, char *argv[]) {
        /* test harness */
        int tests_passed = 0;
        int tests_failed = 0;
     
        /* create a queue instance and initialize it */ 
        queue q_instance;
     
        /* create a handle to the queue so that we can manipulate it
        without having to put the & in front all the time */
     
        queue *qp = &q_instance;
     
        printf("Initializing queue\n");
        initializeQueue(qp, 20);
     
        /* how do we see if queue was propery initialized? */
        
        /* add and remove one element */
        int e1 = 42;
        
        addElement(qp, e1);
        printf("Test 1: ");
        printf_queue(qp);
        printf("\n");
     
        /* length should have gone up by one */
     
        if ( qp->length != 1 ) {
            printf("Test 1 failed, length %d should be 1\n", 
                qp->length);
            tests_failed++;
            }
        else {
            printf("Test 1 passed.\n");
            tests_passed++;
            }
        
     
        printf("Test 2: ");
        int e2 = removeElement(qp);
        printf_queue(qp);
        printf("\n");
     
        if ( qp->length != 0 ) {
            printf("Test 2.1 failed, length %d should be 0\n", 
                qp->length);
            tests_failed++;
            }
        else {
            printf("Test 2.1 passed.\n");
            tests_passed++;
            }
        
        if ( e1 != e2 ) {
            printf("Test 2.2 failed, e2 %d should equal e1 %d\n", 
                e2, e1);
            tests_failed++;
            }
        else {
            printf("Test 2.2 passed.\n");
            tests_passed++;
            }
     
        printf("Test 3: ");
        for (int i=1; i <= 10; i++) {
            addElement(qp, i);
            }
        printf_queue(qp);
        printf("\n");
        for (int i=1; i<= 10; i++) {
            e1 = removeElement(qp);
            if ( qp->length != 10-i ) {
                printf("Test 3.1 failed, length %d should be %d\n",
                    qp->length, 10-i);
                tests_failed++;
                }
            else {
                tests_passed++;
                }
            if ( e1 != i ) {
                printf("Test 3.2 failed, element %d should be %d\n",
                    e1, i);
                tests_failed++;
                }
            else {
                tests_passed++;
                }
            }
     
        
        /* a fatal test */
        if ( 0 ) {
            printf("Test 4: remove on empty queue\n");
            e2 = removeElement(qp);
            tests_failed++;
            }
     
        printf("Tests Passed: %d\n", tests_passed);
        printf("Tests Failed: %d\n", tests_failed);
        }
Exercises:

  1. Write a function that returns the element at index in the queue, and deletes it from inside the queue. Do it for both implementations. The signature of the function should be:
    int deleteElement(queue *q, int index)

  2. What changes have to be made to the implementation if you remove node *tail field from the queue struct in the linked list queue implementation?

    How does this change the big-O of the addElement function?

  • Both implementations use malloc, which means that there is potential for memory leaks. Where can these occur? How would you fix them.

    15.4 A Queue Implementation That is More Modular

    One of the problems with ADTs is that different ADTs often share similar function names, for example addElement could apply to a queue or an operation on large integers. To distinguish between ADTs one usually adopts some naming convention. A typical one is to prefix the function or procedure with something like q_ to indicate that it belongs to the qeue ADT. Note this is one of the issues that is solved by adopting an object-oriented style of programming.

    Here is a revised version of the interface that uses this convention. Note how the queue now is declared as a pointer to a struct, so queue variables really are handles to the queue instance.

    code/Queues/interface/queue.h

        /*
            Queue of int, implemented by a linked list
         
            Names are prefixed with q_ to indicate methods that belong to the
            queue ADT.
        */
        #ifndef _queue_h
        #define _queue_h
         
        /*
            A linked list contains nodes which hold the information for 
            that node (val) and the pointer to the next node in the 
            list (next).
         
            When next is 0 (null pointer) there is no following cell.
        */
        typedef struct q_node_t {
            int val;
            struct q_node_t *next;
        } q_node_t;
         
        /*
            The queue is implemented by keeping a pointer to the head 
            node of a linked list.  To make adding nodes to the queue 
            efficient, we also have a pointer to the tail node of the 
            list.
         
            A queue is manipulated by passing around a pointer to its 
            queue struct.
        */
        typedef struct {
            q_node_t *head;
            q_node_t *tail;
            int length;
        } q_instance_t;
         
        /*  
            A queue is a pointer to a queue_instance  
        */
        typedef q_instance_t *queue;
         
        /*
            Constructor: create a queue instance and return a queue 
            (i.e. a pointer to the struct).
        */
         
        queue q_create(int size_hint);
         
        /*
            Destructor: free up the storage used by the queue.
        */
        void q_destroy(queue q);
         
        /*
            Get the current length of the queue
        */
        int q_length(queue q);
         
        /*
            Add the element val to the tail of the queue q
        */
        void q_add(queue q, int val);
         
        /*
            Remove and return the element at the head of queue q
         
            Pre-condition: q_length(q) > 0
        */
        int q_remove(queue q);
         
        /*
            Get the element of the queue at position index,
            where the head of the queue is position 0, and the
            tail is at position q_length(q)-1
        */
        int q_get_item(queue q, int index);
         
        /*
            Return the element at index in the queue, and deletes it from inside 
            the queue. 
        */
        int q_delete_item(queue q, int index);
         
        #endif


    Note the other change in the interface that replaces initializeQueue with a function q_create that creates a queue and returns a handle to it. This way you cannot get an uninitialized queue. Also, there is a q_destroy that frees up all the storage associated with the queue. q_create is called a constructor and q_destroy is called a destructor

    Of course we need to revise the implementation. NOTE that some part sof the implementation are missing, the ones marked with /* non-functional stub code */

    code/Queues/interface/queue.c

        /*
            Implementation of queue Abstract Data Type (ADT)
        */
         
        #include <stdlib.h>
        #include <stdio.h>
        #include <assert.h>
        #include "queue.h"
         
        /*
            Constructor: create a queue instance and return a queue
            (i.e. a pointer to the struct).
        */
         
        queue q_create(int size_hint) {
            queue q = (q_instance_t *) malloc(sizeof(q_instance_t));
            assert(q != 0);
         
            q->head = 0;
            q->tail = 0;
            q->length = 0;
         
            return q;
        }
         
        /*
            Destructor: free up the storage used by the queue.
        */
        void q_destroy(queue q) {
            /* get rid of all the elements in the queue */
            while ( q_length(q) > 0 ) {
                q_remove(q);
                }
            free(q);
            }
         
        /*
            Get the current length of the queue
        */
        int q_length(queue q) {
            return q->length;
            }
         
        /*
            Add the element val to the tail of the queue q
        */
         
        void q_add(queue q, int val) {
            q_node_t * n = (q_node_t *) malloc(sizeof(q_node_t));
         
            // make sure malloc worked
            assert(n != 0);
         
            // initialze the new node to contain the value and have no next
            n->val = val;
            n->next = 0;
         
            // if there is stuff in the queue, add new node to end
            // if an empty queue, need to set up head.
            if (q->length != 0) {
                    q->tail->next = n;
            } else {
                    q->head = n;
            }
         
            // new node is at the tail
            q->tail = n;
            q->length++;
            }
         
        /*
            Remove and return the element at the head of queue q
         
            Pre-condition: q_length(q) > 0
        */
         
        int q_remove(queue q) {
            assert(q->length > 0);
            
            // get the value at the head
            int rval = q->head->val;
         
            // new head is the next one
            q_node_t *new_head = q->head->next;
         
            /* Now we can free the old head so that we don't leave unused 
               memory allocated
            */
            free(q->head);
         
            q->length--;
         
            // Now we can set the head to new_head
            q->head = new_head;
         
            // if queue is empty, we need to set tail also.
            if (q->length == 0) {
                q->tail = 0;
                }
         
            return rval;
            }
         
        /*
            Get the element of the queue at position index,
            where the head of the queue is position 0, and the
            tail is at position length(q)-1
        */
        int q_get_item(queue q, int index) {
            assert(0 <= index && index < q->length);
            /* non-functional stub code */
            return 0;
            }
            
        /*
            Return the element at index in the queue, and deletes it from inside
            the queue.
        */
        int q_delete_item(queue q, int index) {
            assert(0 <= index && index < q->length);
            /* non-functional stub code */
            return 0;
            }
         
         


    And since we have clearly modified the interface we need to redo our test program:

    code/Queues/interface/testq.c

        #include <stdio.h>
        #include <stdlib.h>
        #include "queue.h"
         
        /*
            print the contents of a queue from head to tail going left 
            to right.
        */
        void q_printf(queue q) {
            for (int i=0; i < q_length(q); i++) {
                printf("%d ", q_get_item(q, i));
                }
            }
         
         
        int main(int argc, char *argv[]) {
            /* test harness */
            int tests_passed = 0;
            int tests_failed = 0;
         
            /* create a queue with a size hint */
            printf("Creating queue\n");
            queue qp = q_create(20);
         
            /* how do we see if queue was propery initialized? */
            
            /* add and remove one element */
            int e1 = 42;
            
            q_add(qp, e1);
            printf("Test 1: ");
            q_printf(qp);
            printf("\n");
         
            /* length should have gone up by one */
         
            if ( q_length(qp) != 1 ) {
                printf("Test 1 failed, length %d should be 1\n", 
                    q_length(qp));
                tests_failed++;
                }
            else {
                printf("Test 1 passed.\n");
                tests_passed++;
                }
            
         
            printf("Test 2: ");
            int e2 = q_remove(qp);
            q_printf(qp);
            printf("\n");
         
            if ( q_length(qp) != 0 ) {
                printf("Test 2.1 failed, length %d should be 0\n", 
                    q_length(qp));
                tests_failed++;
                }
            else {
                printf("Test 2.1 passed.\n");
                tests_passed++;
                }
            
            if ( e1 != e2 ) {
                printf("Test 2.2 failed, e2 %d should equal e1 %d\n", 
                    e2, e1);
                tests_failed++;
                }
            else {
                printf("Test 2.2 passed.\n");
                tests_passed++;
                }
         
            printf("Test 3: ");
            for (int i=1; i <= 10; i++) {
                q_add(qp, i);
                }
            q_printf(qp);
            printf("\n");
            for (int i=1; i<= 10; i++) {
                e1 = q_remove(qp);
                if ( q_length(qp) != 10-i ) {
                    printf("Test 3.1 failed, length %d should be %d\n",
                        q_length(qp), 10-i);
                    tests_failed++;
                    }
                else {
                    tests_passed++;
                    }
                if ( e1 != i ) {
                    printf("Test 3.2 failed, element %d should be %d\n",
                        e1, i);
                    tests_failed++;
                    }
                else {
                    tests_passed++;
                    }
                }
         
            
            /* a fatal test */
            if ( 0 ) {
                printf("Test 4: remove on empty queue\n");
                e2 = q_remove(qp);
                tests_failed++;
                }
         
            printf("Tests Passed: %d\n", tests_passed);
            printf("Tests Failed: %d\n", tests_failed);
            }
    Exercises:

    1. Write a function that lets you set the value of the item at position index in the queue.
      void q_set_item(queue q, int index, int new_val)
    15. Queues
    Tangible Computing / Version 3.20 2013-03-25