Queues - Array Implementation - Functions


  1. Review:

    Recall, we decided to implement a queue as a fixed-sized array. The data types that we created for the queue where organized (in the queue module) as follows:

    queue.h                         queue.c
    -------                         -------
                                    #include "queue.h"
    
    typedef char queueElementT;     #define MAX_QUEUE_SIZE  100
    
    typedef struct queueCDT         typedef struct queueCDT {
            *queueADT;                queueElementT contents[MAX_QUEUE_SIZE];
                                      int front;
                                      int count;
                                    } queueCDT;
    

    In other words, things that need to be part of the interface go in queue.h and things that are hidden as part of the implementation go in queue.c.

    Again, here is an example of how people will use queues:

    #include "queue.h"
    
    ...
    
    queueADT q1, q2;
    char ch;
    
    q1 = QueueCreate();
    q2 = QueueCreate();
    
    QueueEnter(q1, 'a');
    QueueEnter(q2, 'b');
    ch = QueueDelete(q1);
    
    QueueDestroy(q1);
    QueueDestroy(q2);
    

    You should be able to answer the following questions:

  2. QueueCreate() function:

    Here are the functions we need to implement...

    For general queue operations:
    • QueueEnter()
    • QueueDelete()
    • QueueIsEmpty()

    Because we are programming in C (setup/cleanup):
    • QueueCreate()
    • QueueDestroy()

    Because of our implementation (fixed-size implementation):
    • QueueIsFull()

    Let's start with the function QueueCreate(), which creates a queue.

    Note that our use of the queueADT (a pointer) with queue functions differs from how we might use it if it was a struct. Notably,

    (Remember that from the queue user's end, a queue is a pointer, not a structure.)

    Now, let's think about the QueueCreate() function.

    1. Since a queueADT only gives us a pointer, how will QueueCreate() create the queueCDT?
    2. Once we have a queueCDT, what do we need to do to its fields: contents, front and count?
    3. How does the reference to the new queueCDT get out of the function QueueCreate() so that it can be used?

    Our solution becomes:

    queueADT QueueCreate(void)
    {
      queueADT queue;
    
      queue = (queueADT)malloc(sizeof(queueCDT));
    
      if (queue == NULL) {
        fprintf(stderr, "Insufficient Memory for new Queue.\n");
        exit(ERROR_MEMORY);  /* Exit program, returning error code. */
      }
    
      queue->front = 0;
      queue->count = 0;
    
      return queue;
    }
    

    Here are the functions we have left:

    return-type QueueDestroy(parameters);
    return-type QueueEnter(parameters);
    return-type QueueDelete(parameters);
    return-type QueueIsEmpty(parameters);
    return-type QueueIsFull(parameters);
    

    We want to be consistent in how we use a queue with queue functions. QueueCreate() is an exception since it must return a queueADT....

    queueADT QueueCreate(void);
    

    Nonetheless, since most functions will require some way to refer to the queue that they are to operate on, what should these functions take?

    Answer: They should take queueADTs.

  3. QueueDestroy() function:

    QueueDestroy() is a function that must deallocate any memory used by the queue. Since a queue is kept track of with a queueCDT, this means any memory used directly or indirectly by the CDT.

    Recall that a queueCDT is the following:

    typedef struct queueCDT {
      queueElementT contents[MAX_QUEUE_SIZE];
      int front;
      int count;
    } queueCDT;
    

    What about the parts of the CDT?


    Note: The CDT was dynamically-allocated, but doing so automatically gave us all the fields in the CDT. That's why we don't say the fields were dynamically-allocated.

    In conclusion, all QueueDestroy() has to do is free the structure which is the CDT, giving:

    void QueueDestroy(queueADT queue)
    {
      free(queue);
    }
    

  4. QueueEnter() function:

    Now, let's think about what QueueEnter() must do. In general, it must add an element to the rear of the queue.

    However, because of the specifics of our implementation, it must be able to deal with wrapping around the array, in other words, the end of the array may not be the end of the queue, as in the following case:

    queue
    -----------------   -----   -----
    | e | b | c | d |   | 1 |   | 4 |
    -----------------   -----   -----
      0   1   2   3     front   count
    contents
    

    where the contents of the queue are b, c, d, e (from front to rear).

    Here is a general outline of what QueueEnter() must do:

    1. Make sure there is room in the array.
    2. Calculate the index of where the new element will go and place the element there.
    3. Increment the count.

    Our solution is the following:

    void QueueEnter(queueADT queue,
                    queueElementT element)
    {
      int newElementIndex;
    
      if (queue->count >= MAX_QUEUE_SIZE) {
        fprintf(stderr, "QueueEnter on Full Queue.\n");
        exit(ERROR_QUEUE);  /* Exit program, returning error code. */
      }
    
      /*
       * Calculate index at which to put
       * next element.
       */
      newElementIndex = (queue->front
                        + queue->count)
                        % MAX_QUEUE_SIZE;
      queue->contents[newElementIndex] = element;
    
      queue->count++;
    }
    

  5. QueueDelete() function:

    Now, let's think about what QueueDelete() must do. In general, it must remove an element from the front of the queue.

    Again, our implementation requires us to deal with wrapping around the array. During deletion, the rear does not move, but the front does. Thus, we have to worry about wrapping the front in cases like the following:

    queue
    -----------------   -----   -----
    | j | k |   | i |   | 3 |   | 3 |
    -----------------   -----   -----
      0   1   2   3     front   count
    contents
    

    Here, when we remove the value 'i', the front should go from the end of the array and wrap around to the first position 0 (zero).

    An outline for the function might be:

    1. Make sure there is at least one element to remove.
    2. Make a note of where the element to be removed is or what its value is.
    3. Move the front.
    4. Decrement the count.
    5. Return the removed element.

    Here is our implementation of the function:

    queueElementT QueueDelete(queueADT queue)
    {
      queueElementT oldElement;
    
      if (queue->count <= 0) {
        fprintf(stderr, "QueueDelete on Empty Queue.\n");
        exit(ERROR_QUEUE);  /* Exit program, returning error code. */
      }
    
      /* Save the element so we can return it. */
      oldElement = queue->contents[queue->front];
    
      /*
       * Advance the index of the front,
       * making sure it wraps around the
       * array properly.
       */
      queue->front++;
      queue->front %= MAX_QUEUE_SIZE;
    
      queue->count--;
    
      return oldElement;
    }
    

  6. QueueIsEmpty() and QueueIsFull() functions:

    QueueIsEmpty() and QueueIsFull() simply have to return whether the queue has no elements or whether the queue's array has no more slots for elements (respectively). Their implementation is left up to the reader.

  7. Completed code:

    We've written the code for queue.h and queue.c, plus a sample testing program queuetest.c and a Makefile.

    The program demonstrates how each of the queue functions would be used. What should be the output of the program given that a queue provides FIFO ordering?

  8. Something harder:

    For those who want something more challenging, let's make our implementation more difficult. Suppose we want to implement the queue using an array that grows when it is full and someone adds something to it.

    First, what changes to the types for a queue will be necessary?

    Answer: Only queueCDT need change. The array must be changed to a pointer and we have to add a field telling us how big the array currently is, as in:

    typedef struct queueCDT {
      queueElementT *contents;
      int curSize;
      int front;
      int count;
    } queueCDT;
    

    Next, how will the function QueueEnter() be different? Let's start by looking at how the outline for the function changes:

    New outline for QueueEnter():

    1. Make sure there is room in the array.

      If not...

      1. Allocate a new array.*
      2. Copy all the old elements into it.
      3. Remove the old array, make the new array the current one.
      4. Update where the front is, plus any other fields that need to be updated.

    2. Calculate the index of where the new element will go and place the element there.
    3. Increment the count.

    * What size should the re-allocated array be?

    One choice would be to make it just big enough to hold the new element; however, a more efficient choice (requiring less re-allocation in the future) would be to make it bigger (e.g., twice its current size).


BU CAS CS - Queues - Array Implementation - Functions
Copyright © 1993-2000 by Robert I. Pitts <rip at bu dot edu>. All Rights Reserved.