Queue Class

If you are programming with .Net, there is a queue class already implemented for you. If you have ever endured a “white board” programming interview, however, you may have discovered that it helps to have implementations already committed to memory for queues, trees, lists, stacks, and tables (among other things). There is a unique opportunity here to take ownership of your success, at the lowest level, and bring your own best work to the table. Sure, you could look up a queue implementation online (like the one illustrated in this post), memorize it, and use it for an interview question or even incorporate it into a program; but your chances of success will be much higher if you develop and test your own queue class.

In the interest of brevity (and the minimization of keystrokes or whiteboard characters), I have used shorthand code in the following example.

This queue class is far from optimal. It assumes an ideal processing environment in which the cost of allocating/deallocating memory is low and can be called repeatedly. A far better implementation would either have a fixed number of possible elements or an increment by which the element count can grow (other than 1 for each enqueue and -1 for each dequeue, as in this example).

Content of Queue.h:

#define O void // for Object pointers (O*)
#define Z NULL // shorthand for NULL
 
class E // represents a queue Element
{
public:
    O* m_pO; // pointer to an Object
    E* m_pN; // pointer to the Next element
 
    E(O* pO) // Element constructor
    {
        m_pO = pO;
        m_pN = Z;
    };
};
 
class Q // represents a Queue
{
public:
    E* m_pF; // pointer to the Front element
    E* m_pB; // pointer to the Back element
 
    Q() // Queue constructor
    {
        m_pF = Z;
        m_pB = Z;
    };
 
    ~Q() // Queue destructor
    {
        while (m_pF) // while the front element is not NULL,
        {
            DQ(); // dequeue elements
        }
    };
 
    E* NQ(O* pO) // Enqueue function
    {
        if (!pO) // if the object pointer is NULL,
        {
            return Z; // do not enqueue
        }
 
        E* pE = new E(pO); // create a new element
 
        if (pE) // if the element was allocated,
        {
            if (m_pB) // if the back element is not NULL,
            {
                m_pB->m_pN = pE; // uptate the next pointer of the back element
            }
 
            m_pB = pE; // place the new element at the back of the queue
 
            if (!m_pF) // if the front element is NULL,
            {
                m_pF = m_pB; // set the front element equal to the back element
            }
        }
 
        return pE; // return the new element pointer
    };
 
    O* DQ() // Dequeue function
    {
        E* pE = m_pF; // get the element at the front of the queue
 
        if (pE) // if the element is not NULL,
        {
            m_pF = m_pF->m_pN; // point the front element at the next element
 
            if (!m_pF) // if the front element is NULL,
            {
                m_pB = Z; // set the back element to NULL
            }
 
            O* pO = pE->m_pO; // get the object pointer from the element
 
            delete pE; // delete the element
 
            return pO; // return the object pointer
        }
        else // if the element is NULL,
        {
            return Z; // return NULL, as the queue is empty
        }
    };
};

Content of a test program (windows console application):

#define WIN32_LEAN_AND_MEAN
#define WINVER 0x0400
#define _WIN32_WINNT 0x0400
#define _CRTDBG_MAP_ALLOC
 
#include 
#include 
#include 
#include "Queue.h"
 
#define I 7
 
_TCHAR szA[] = _T("alpha");
_TCHAR szB[] = _T("bravo");
_TCHAR szC[] = _T("charlie");
_TCHAR szD[] = _T("delta");
_TCHAR szE[] = _T("echo");
_TCHAR szF[] = _T("foxtrot");
_TCHAR szG[] = _T("golf");
 
_TCHAR* items[I] = { szA, szB, szC, szD, szE, szF, szG };
 
int _tmain(int argc, _TCHAR* argv[])
{
        Q q;
    int i = 0;
    _TCHAR* szOut = NULL;
 
    //
    // verify output items match input items
    //
 
    // fill the queue:
    for (i = 0; i < I; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify output items match input items; enqueue\r\n"));
            return 0;
        }
    }
    // test the queue contents:
    for (i = 0; (NULL != (szOut = (_TCHAR*)q.DQ())); i++)
    {
        if (_tcscmp(szOut, items[i]) != 0)
        {
            _tcprintf(_T("Fail: verify output items match input items; content\r\n"));
            return 0;
        }
    }
    // test the item count:
    if (i != I)
    {
        _tcprintf(_T("Fail: verify output items match input items; count\r\n"));
        return 0;
    }
    // write pass message:
    _tcprintf(_T("Pass: verify output items match input items\r\n"));
 
    //
    // verify empty queue
    //
 
    // the queue should now be empty:
    if (NULL != q.DQ())
    {
        _tcprintf(_T("Fail: verify empty queue\r\n"));
        return 0;
    }
    // write pass message:
    _tcprintf(_T("Pass: verify empty queue\r\n"));
 
    //
    // verify enqueue after partial dequeue
    //
 
    // fill the queue with 3 items:
    for (i = 0; i < 3; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; enqueue\r\n"));
            return 0;
        }
    }

    // dequeue 2 items:
    for (i = 0; i < 2; i++)
    {
        if (NULL == q.DQ())
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; dequeue\r\n"));
            return 0;
        }
    }

    // add 4 more items to the queue:
    for (i = 0; i < 4; i++)
    {
        if (NULL == q.NQ((O*)items[i]))
        {
            _tcprintf(_T("Fail: verify enqueue after partial dequeue; enqueue\r\n"));
            return 0;
        }
    }
    // write pass message:
    _tcprintf(_T("Pass: verify enqueue after partial dequeue\r\n"));
 
    // queue now contains 5 items;
    // the queue destructor should clean these up;
    // otherwise, memory leaks will be detected below:
    q.~Q();
 
    // trigger memory leak detection:
    if (_CrtDumpMemoryLeaks())
    {
        _tcprintf(_T("Fail: verify queue destructor\r\n"));
    }
    else
    {
        _tcprintf(_T("Pass: verify queue destructor\r\n"));
    }
    return 0;
}

Example output:

Pass: verify output items match input items
Pass: verify empty queue
Pass: verify enqueue after partial dequeue
Pass: verify queue destructor

I strongly encourage all programmers, regardless of experience level, to implement and test classes similar to, but more optimal than, this. Use them in actual product code, and skip taking dependencies on pre-fabricated container classes. Run some comparative performance testing. See if you can create something better, faster, and smaller! Dare to go native!