-
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:
Enter (or Insert)
Places an object at the rear of the queue.
Delete (or Remove)
Removes an object from the front of the queue and produces
that object.
IsEmpty
Reports whether the queue is empty or not.
-
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.
-
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
-
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:
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.
-
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?
-
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.
(
-
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;
