gq_util - Generalized Queue (GQ) Utilities

The GQ_UTIL package implements double-ended queues (deques).

In a normal queue, items are added at the rear of the queue and removed from the front, thus producing first-in, first-out (FIFO) behavior. In a double-ended queue, an application can add and remove items at both ends, front and rear, of the queue. As a result, a deque can also be used as a regular FIFO queue or as a last-in, first-out (LIFO) stack. (And since the GQ_UTIL package allows items to be inserted in or retrieved/removed from the middle of its queues, a GQ_UTIL queue can also be used as a list!)

The GQ_UTIL package does not have built-in support for:

• input-restricted deques (addition at one end, removal at either end)
• output-restricted deques (addition at either end, removal at one end)

Applications requiring such deques are responsible for enforcing these constraints on the deques; i.e., don't perform operations that violate the constraints.

The items in a queue are simple void * pointers. If items point to dynamically allocated objects, the application must deallocate them at the appropriate time (which may be outside the lifetime of the queue if references to the objects are stored elsewhere).

Terminology

A GQ_UTIL generalized queue is a sequence of items.

In a GQ_UTIL queue with N items, the items are numbered 1..N, where item 1 is at the front of the queue and item N is at the rear.

As opposed to item numbering, positions in the queue are 0..N, where position i falls in between items i and i+1. When adding an item to a queue, positions have the following meanings (and note that this package allows items to be inserted in the middle of the queue):

Some shortcut positions:

Items nominally are removed from a queue by position, although the meanings of position and item number are effectively the same:

Operations

There are 3 operations on a queue (bulleted "functions" are macros, #defined in the header file, that call the base function):

1. Add an item to the queue.

   • gqAdd() - adds/inserts an item at an arbitrary position
   • gqAddFront() - inserts an item at the beginning of the queue.
   • gqAddRear() - adds an item to the end of the queue.
   • gqPush() - stack-oriented shorthand for gqAddFront().

2. Examine an item in the queue.

   • gqGet() - gets the item at an arbitrary position.
   • gqGetFront() - gets the item at the beginning of the queue.
   • gqGetRear() - gets the item at the end of the queue.
   • gqTop() - stack-oriented shorthand for gqGetFront().

3. Remove an item from the queue.

   • gqRemove() - removes the item at an arbitrary position.
   • gqRemoveFront() - removes the item at the beginning.
   • gqRemoveRear() - removes the item at the end.
   • gqPop() - stack-oriented shorthand for gqRemoveFront().

Example

The following example shows a GQ_UTIL queue being exercised as a double-ended queue, a regular queue, and a stack:

    #include  <stdio.h>				-- Standard I/O definitions.
    #include  <stdlib.h>			-- C Library definitions.
    #include  "gq_util.h"			-- General queue utilities.

    main (int argc, char *argv[])
    {
        GeneralQ  queue ;
        size_t  i ;

        gqCreate (5, &queue) ;			-- Create a 5-slot queue.

        ----

        printf ("Double-ended queue:\n") ;

        gqAddFront (queue, "A") ;		-- Add 6 string items.
        gqAddRear (queue, "B") ;		-- "AB"
        gqAddFront (queue, "C") ;		-- "CAB"
        gqAddRear (queue, "D") ;		-- "CABD"
        gqAddFront (queue, "E") ;		-- "ECABD"
        gqAddRear (queue, "F") ;		-- Too many items; drop "E".

        while (gqCount (queue) > 0) {		-- Print contents of queue.
            printf ("%s", (char *) gqRemoveFront (queue)) ;
        }
        printf ("\n") ;				-- Prints "CABDF".

        ----

        printf ("Regular FIFO queue:\n") ;

        gqAddRear (queue, "A") ;		-- Add 6 string items.
        gqAddRear (queue, "B") ;		-- "AB"
        gqAddRear (queue, "C") ;		-- "ABC"
        gqAddRear (queue, "D") ;		-- "ABCD"
        gqAddRear (queue, "E") ;		-- "ABCDE"
        gqAddRear (queue, "F") ;		-- Too many items; drop "A".

        while (gqCount (queue) > 0) {		-- Print contents of queue.
            printf ("%s", (char *) gqRemoveFront (queue)) ;
        }
        printf ("\n") ;				-- Prints "BCDEF".

        ----

        printf ("LIFO stack-like queue:\n") ;

        gqPush (queue, "A") ;			-- Add 6 string items.
        gqPush (queue, "B") ;			-- "BA"
        gqPush (queue, "C") ;			-- "CBA"
        gqPush (queue, "D") ;			-- "DCBA"
        gqPush (queue, "E") ;			-- "EDCBA"
        gqPush (queue, "F") ;			-- Too many items; drop "A".

        while (gqCount (queue) > 0) {		-- Print contents of queue.
            printf ("%s", (char *) gqPop (queue)) ;
        }
        printf ("\n") ;				-- Prints "FEDCB".

        gqDestroy (queue) ;			-- Delete the queue.

        exit (0) ;

    }

Public Procedures

gqAdd() - adds an item to a queue.

gqCount() - returns the number of items in a queue.

gqCreate() - creates a queue.

gqDestroy() - destroys a queue.

gqErase() - empties a queue.

gqGet() - retrieves an item from a queue.

gqRemove() - removes an item from a queue.

Public Procedures (defined as macros)

gqAddFront() - adds an item at the front of a queue.

gqGetFront() - retrieves the item at the front of a queue.

gqRemoveFront() - removes the item at the front of a queue.

gqAddRear() - adds an item at the rear of a queue.

gqGetRear() - retrieves the item at the rear of a queue.

gqRemoveRear() - removes the item at the rear of a queue.

gqPush() - adds an item at the front of a "stack" queue.

gqPop() - removes the item at the front of a "stack" queue.

gqTop() - gets the item at the front of a "stack" queue.

Source Files

gq_util.c

gq_util.h

(See libgpl for the complete source, including support routines and build files.)