Queue - Array Implementation - Types


  1. Abstract idea of a queue:

    The queue is another data structure. A physical analogy for a queue is a line at a bank. When you go to the bank, customers go to the rear (end) of the line and customers come off of the line (i.e., are serviced) from the front of the line.


    Aside: In fact, other English-speaking countries use this term for a line, e.g., they might say "Queue up!" rather than "Get in a line!"

    Like a stack, a queue usually holds things of the same type. We usually draw queues horizontally. Here's a queue of characters with 3 elements:

    queue
    -------------
    | a | b | c |
    -------------
      ^       ^
      |       |
    front    rear
    

    The main property of a queue is that objects go on the rear and come off of the front of the queue.

    Here are the minimal set of operations we'd need for an abstract queue:

  2. Order produced by a queue:

    Queues are useful because they produce a certain order in which the contents of the queue are used. Let's see what order that is by looking at a queue of characters. Now, what would a particular sequence of Enter and Deletes do to this queue:

    queue
    -------------
    | a | b | c |
    -------------
      ^       ^
      |       |
    front    rear
    

    Now, Enter(queue, 'd')...

    queue
    -----------------
    | a | b | c | d |
    -----------------
      ^           ^
      |           |
    front        rear
    

    Now, ch = Delete(queue)...

    queue           ch
    -------------   -----
    | b | c | d |   | a |
    -------------   -----
      ^       ^
      |       |
    front    rear
    

    You'll notice that the queue enforces a certain order to the use of its contents. Is the ordering of the queue Last thing In is the First thing Out (LIFO) or First Thing In is the First thing Out (FIFO)?

    Answer: Queues produce FIFO order. Remember that stacks produce LIFO order.

  3. Implementing a queue with an array:

    Since a queue usually holds a bunch of items with the same type, we could implement a queue with an array. Let's simplify our array implementation of a queue by using an array of a fixed size, MAX_QUEUE_SIZE.

    What other pieces of data would you need (besides an array) to implement a queue in this way?

    One of the things we'll need to keep track of is the number of elements in the queue, i.e., not all the elements in the array may be holding elements of the queue at any given time.

    So far, the pieces of data we need for our array implementation of the queue are:

    an array
    a count
    

    Will these pieces be sufficient? Let's look at an example to find out...We'll start with a queue with 3 elements:

    queue (made up of 'contents' and 'count')
    -----------------   -----
    | a | b | c |   |   | 3 |
    -----------------   -----
      0   1   2   3     count
    contents
    

    where a is at the front and c is at the rear. Now, we enter a new element with: Enter(queue, 'd')...

    queue (made up of 'contents' and 'count')
    -----------------   -----
    | a | b | c | d |   | 4 |
    -----------------   -----
      0   1   2   3     count
    contents
    

    All seems well. How about if we remove an element with: ch = Delete(queue)?...

    queue (made up of 'contents' and 'count')
    -----------------   -----   -----
    |   | b | c | d |   | 3 |   | a |
    -----------------   -----   -----
      0   1   2   3     count    ch
    contents
    

    Hmmm, we have a problem because the front of the queue is no longer at array position 0. One solution would be to move all the elements down one, giving:

    queue (made up of 'contents' and 'count')
    -----------------   -----
    | b | c | d |   |   | 3 |
    -----------------   -----
      0   1   2   3     count
    contents
    

    We reject that solution though because it is too expensive to move everything down every time we remove an element.

    Instead, can we use an additional piece of information to keep track of the front?

    Answer: Yes! We can use the index of the element at the front, giving:

    queue (made up of 'contents', 'front' and 'count')
    -----------------   -----   -----
    |   | b | c | d |   | 1 |   | 3 |
    -----------------   -----   -----
      0   1   2   3     front   count
    contents
    

    Now, what if we enter another element with: Enter(queue, 'e')? Currently, the rear of the queue holds 'd' and is at the end of the array. Where will we put 'e'?

    We've already said that moving everything down is too expensive. An alternative would be to use the array in a circular fashion. In other words, when we hit the end of the array, we wrap around and use the beginning. Now, with this choice for entering 'e', the fields look like:

    queue (made up of 'contents', 'front' and 'count')
    -----------------   -----   -----
    | e | b | c | d |   | 1 |   | 4 |
    -----------------   -----   -----
      0   1   2   3     front   count
    contents
    

    Finally, how would it look like after: ch = Delete(queue)?

    queue (made up of 'contents', 'front' and 'count')
    -----------------   -----   -----   -----
    | e |   | c | d |   | 2 |   | 3 |   | b |
    -----------------   -----   -----   -----
      0   1   2   3     front   count    ch
    contents
    

  4. Alternative representation:

    As we've seen, one choice for the set of data needed for the queue is:

    an array
    a front index
    a count
    

    There is another possibility...Instead, we could replace the count with the location of the rear, thus using the following pieces of data:

    an array
    a front index
    a rear index
    

    Then, these pieces of data would reflect the state of the queue in the following way...Starting out with a queue with 4 elements...

    queue (made up of 'contents', 'front' and 'rear')
    -----------------   -----   -----
    | a | b | c | d |   | 0 |   | 3 |
    -----------------   -----   -----
      0   1   2   3     front   rear
    contents
    

    Now, remove one with ch = Delete(queue), giving:

    queue (made up of 'contents', 'front' and 'rear')
    -----------------   -----   -----
    |   | b | c | d |   | 1 |   | 3 |
    -----------------   -----   -----
      0   1   2   3     front   rear
    contents
    

    Now, add one with Enter(queue, 'e'), giving:

    queue (made up of 'contents', 'front' and 'rear')
    -----------------   -----   -----
    | e | b | c | d |   | 1 |   | 0 |
    -----------------   -----   -----
      0   1   2   3     front   rear
    contents
    

    Let's decide which data representation to use. Since one representation might make some of the queue functionality conceptually easier to write, we have to look at the functionality we'll need.

    From the generic description of the queue, we know we need, at least:

    • Enter
    • Delete
    • IsEmpty

    However, since we will be writing this is C, we'll also need things to:

    • Create - create a new queue.
    • Destroy - destroy the queue when we are done with it.
    • IsFull - test for fullness since this is a queue with a fixed maximum size.

    Our analysis of the tradeoffs are the following:

    • Using the count will make IsEmpty() and IsFull() easy, although we'll have to make sure the count is updated properly in Enter() and Delete(). We haven't explored how to determine emptiness/fullness with rear or whether doing so presents any challenges.

    • Using the count in Enter() is similar to using rear. In both cases, the front won't move. With the count, we'll have to use count to calculate at which position to add new values, making sure to wrap around the array if necessary. Similarly, with a rear we have to make sure the rear moves properly and wraps around.

    • Using the count in Delete() is not more difficult than using rear. In both cases, the front has to move (and wrap around when necessary).

    Given these differences, we'll choose the representation with a count.

  5. C implementation:

    Now, think about how to actually implement this queue in C. Again, we're implementing a queue of characters.

    Since we put data structures in their own modules, we'll want to create the source files queue.h and queue.c.

    The operations needed for our queue are mainly determined by the operations provided by an abstract queue, namely:

    QueueEnter()
    QueueDelete()
    QueueIsEmpty()
    

    However, as we've seen, we also need additional operations for setup and cleanup since we are implementing the queue in a programming language. In addition, we need to be able to test fullness for this finite queue. We'll introduce these extra operations when we know more about how we will implement the queue.

    Now, before we ponder the details of the queue operations, what must we decide on?

  6. Organization of data types for a queue:

    Our goal is to have a type for a queue, so that people using our queue can define queue variables, and pass them to queue functions. For example, we'd like to do something like the following:

    type-of-a-queue q1, q2;
    char ch;
    
    /* Setup queues. */
    
    QueueEnter(ref-to-q1, 'a');
    QueueEnter(ref-to-q2, 'b');
    
    ch = QueueDelete(ref-to-q1);
    
    /* Cleanup queues. */
    

    However, we'll also want to abstract the type of an element.

    Let's consider the organization of types between our queue module files:

    queue.h				queue.c
    -------				-------
    				#include "queue.h"
    
    type-of-an-element
    
    type-of-a-queue
    

    The interface (.h) for the queue will need to have a type for the queue (for people to define queue variables) and the type of an element (for functional prototypes)...

    However, while people using the queue will need to know the type-of-a-queue, and thus, it will need to be in the header file, we want to hide any of the internals of the type-of-a-queue in the .c file. Thus, the type-of-a-queue is broken up into an abstract and concrete part.

    • The concrete part is a structure with all the pieces of data needed for a queue, which is hidden in the implementation. (Remember that we isolate this type from users of the queue, i.e., they do not need to know that the queue is implemented with an array. Furthermore, isolating the type will prevent them from being able to mess up the queue.)

    • The abstract part that is a pointer to such a structure, which is publicly available to users of a queue.

    Therefore, our goal is to have the following:

    queue.h				queue.c
    -------				-------
    				#include "queue.h"
    
    type-of-an-element
    
    abstract-type-of-a-queue	concrete-type-of-a-queue
    

    We'll get the types from queue.h in queue.c since we always include the header for a module in the implementation (.c) part of the module.

  7. ADTs and CDTs:

    Let's start filling in the types for a queue. First, we want to write a queue that is very generic. The fact that this queue holds a character is only particular to this program. It should be easy to change the type of things held in the queue.

    Let's introduce a type name things held in the queue:

    typedef char queueElementT;
    

    This will go in the header file, since we need it for the queue function prototypes.

    Next, we need something that holds all the information needed to keep track of the queue. We already decided that we will use an array, front index and count.

    What construct will we use to combine these 3 fields into a single type?

    Answer: A struct, which becomes our concrete-type-of-a-queue, struct queueCDT:

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

    and goes in the implementation file. Now, in the header file, we must fill in what the abstract-type-of-a-queue is as follows:

    typedef struct queueCDT *queueADT;
    

    Finally, we have:

    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;
    


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