Queue Pimping

==============================================================================
C-Scene Issue #3
Queue Pimping
Michael Bacarella
==============================================================================

What is a Queue?

A valid question indeed. A Queue is basically a First In First Out (FIFO) listing of elements that await their turn in an allocated (hopefully) space. Queues are used more often then you might think. Print jobs are queued if something else is currently printing and data received from a device is usually stored up in a queue and wait their turn to be retrieved and used. Not to be confused with a stack, which is Last-in First-Out (simulated by a stack of dishes, and the only way to get to a dish other then the one on top is by removing the ones above it), a queue is usually described as a line at the local DMV, the first person to get on the line is the first person who will be served by the lazy underpaid DMV employee.

Terminology

Queues are sometimes called Ques, and their notation is sometimes used as just Q. (e.g. SQ, RQ, Q_Index) When you add something to the queue, it's known as an en-queue. When you remove something from the queue, it is what we call a de-queue. Simple enough no?

Why would I use a Queue?

Well, here's an example of where I have used a queue before. In a server/client communication algorithm. The user may enter data at any moment in time, and rather then have my program stop what it's doing and service it's needs, I can simply have the data be placed in a queue, and handle it when the time is adequate. Furthermore, if my program can't get to it for a lengthy period of time, the user can still keep entering data into the queue without losing any of it, and this allows you to empty out the queue all at once and send that data onto the server in one blast... provided that this application makes use of multiple threads. :) Still here? Read on!

How do I construct a Queue? (theory)

In theory, the programmer will need to know a few things about the queue.

a large alocated chunk of memory which will hold the data for the queue.
pointer or index to the next available slot in the queue.
pointer or index to the next first occupied slot in the queue.
the ability to en-queue and de-queue data.
the ability to detect if the queue is being overflowed or underflowed.

The large chunk of memory doesn't have to be a large chunk at all, if you happen to be fortunate enough to know how to create linked lists (or a similar data structure) you can occupy only as much memory as you need. A pointer to the next avaliable slot can be an integer/char index variable, or in fact a pointer itself. Same goes for first occupied slot. En-Queuing and De-Queuing will require algorithms of some sort, probably ones that look like this:

EnQueue (data)
{
    get the pointer to the end of the queue
    use the pointer to point to the next slot in the
            chunk of memory you set aside for it
    copy the data to that spot
    increment the pointer to the spot which follows it
}

DeQueue
{
    find the beginning of the queue (use the index variable/pointer luke)
    copy that data to something
    increment the index/pointer
    return whatever you copied to something
}

Now you might see a problem with this. If you've been thinking ahead, you might be wondering, "but if you keep incrementing the variable that points to the first in the line of data, won't it just eventually keep getting larger and larger until you overrun the edge of the boundary?".. well, er, yes. But there's a few things you can do to avoid this. If you're making the queue dynamically, you would have to allocate a chunk of memory for each new element you add and free the chunk of memory that you de-queued. This is usually the best way to implement a queue if you have the time/patience to do so. Another variation is if you plan on reading everything from the queue in one fell swoop, keep resetting the the next-free-slot and first-data-element variables to zero when you've completely emptied the queues.

How do I construct a Queue? (implementation)

This code constructs a queue of size 50. Notice the global variables Q_Start and Q_End as well as the QueueData array. You can probably guess what those are for. The 'main' function will read input from the standard input until one of two things happens.

you hit EOF
the queue is overflowed

The latter won't happen under buffered I/O systems since the program will never know how many keys you have hit until you hit enter/EOF, whence the operating system will finally empty out it's OWN queue and send it all to your program. (See? Queues are everywhere! :)

/* queue.c */
#include <stdio.h>
#define     QUEUE_DEPTH     50

unsigned int     Q_Start;
unsigned int     Q_End;
char    QueuedData[QUEUE_DEPTH];

/* prototypes make compilers happy */
int     EnQueue (char);
char    DeQueue (void);

/* stores data in the queue */
int    EnQueue (char data)
{
    if (Q_End >= QUEUE_DEPTH) {
        fprintf (stderr, "Queue Overflow!");
        return (0);
    }
    QueuedData[Q_End] = data;
    Q_End++;

    /* bounds checking */
    if (Q_End > QUEUE_DEPTH) Q_End = QUEUE_DEPTH;
    return 1;
}

/* returns data from the queue */
char    DeQueue (void)
{
    char    temp;

    if (Q_Start >= QUEUE_DEPTH) {
        return (0);       /* end of queue was reached */
    }
    temp = QueuedData[Q_Start];
    Q_Start++;

    /* bounds checking */
    if (Q_Start > QUEUE_DEPTH) Q_Start = QUEUE_DEPTH;
    return (temp);
}

/* demonstrates the queue */
void    main (void)
{
    char    ch;

    Q_Start = 0;
    Q_End = 0;

    puts ("Enter a string of chars. Signal EOF (Ctrl-Z under DOS) when finished:");

    /* collects chars until EOF is hit or queue is overflowed */
    while ((ch = getchar()) != EOF) {
        if ((EnQueue (ch)) == 0) {
            printf ("\nDumping queue...\n");
            break;
        }
    }
        
    while (ch = DeQueue()) {
        putchar (ch);
    }
    /* at this point, if you wanted to re-use it, you would
       set Q_Start and Q_End to 0 and loop */
}
/* end queue.c */

If I've whet your appetite in any way, and want to see something a little more flexible and awe instilling.. try http://www.psilord.com/defile/queue2.c.

Final Words

Queues are very powerful data structures while being simple in concept and not very durn hard to implement. I find that I'm using them a lot more frequently as of late in my dealings with sockets and graphics programming. They're definitely something worth learning even if you never plan on using them since they appear in the world around us, in computers and elsewhere. (Although it won't help you get to the front of the line at the DMV any more than knowing how the Lottery works will help you win it) I hope this has been of some help. If you have any comments/flames/whatever, please contact me.