Home

GEONius.com
7-Nov-2021
E-mail

gq_util - Generalized Queue (GQ) Utilities

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

NOTE: I needed a queue in one of my programs and I was inspired to write this package by the work of Perl Master Kevin Esteb (github), whose C library implements and makes extensive use of deques. One large project I worked on had what I would call a single "unifying" data structure/concept, around which higher-level functions and multiple programs were elegantly implemented. Kevin's deques seemed to me to play that kind of role since he was able to use them in so many different ways in other parts of his library.

(The only unifying concept I can think of in my library is debug/error output, built-in in rough form since the library's earliest days back in the late 1980s. However, credit for that really belongs to Henry F. Ledgard's Programming Proverbs for FORTRAN Programmers, 1975 edition I believe.)

Why didn't I just use Kevin's deques? I'm retired and need the intellectual stimulation. If I were working, I would download and use his library, which provides many other, useful capabilities in addition to 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:

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):

0
Add the new item to the front of the queue, before item 1.

1..N-1
Insert the new item in the middle of the queue. Adding an item at position 1 inserts the new item in between existing items 1 and 2. Adding an item at position 2 adds the item in between items 2 and 3. Adding an item at position N-1 inserts the item before item N, the item at the rear of the queue, thus making the new item the new penultimate item in the queue.

N
Add the new item after the existing item at the rear of the queue.

Some shortcut positions:

-1
Refers to the same position as N; this saves the caller from first having to call gqCount() to locate the end of the queue.

>N
Any number greater than N also refers to position N. This saves the caller from first having to call gqCount() to locate the end of the queue.

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

0 or 1
Remove the front item, item #1, from the queue.

2..N-1
Remove the specified item.

N
Remove the rear item, item #N, from the queue.

-1 or >N
Also remove the rear item from the queue.

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.

  2. Examine an item in the queue.

  3. Remove an item from the queue.

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

Alex Measday  /  E-mail