Is there a way to reduce the memory use of this queue?

Question

In liberal C:

/* i'm using this */

struct QueueItem
    {
    QueueItem* next;
    void* data;
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    }

/*
    +---+    +---+
    |0 0|    |* *|  len 1
    +---+    +|-|+
              v v
     len     +---+
      0      |d 0|
             +---+

    +---+
    |* *---------...---+
    +|--+              |  len n
     v                 v
    +---+  +---+      +---+
    |a *-->|b *--...->|z 0|
    +---+  +---+      +---+
*/

This gives O(1) for all push/pop/peek and O(n) traversal, but uses 2+2n memory. A naive array version give a minimum of 2+n (about optimal), but is usually worse, and sometimes causes modifications to take longer (for reallocation).

struct Queue
    {
    size_t len;
    size_t head;
    void (*data)[];
    }

/*
    +-----+
    |* * *-----~~~-+
    +|-|--+        |
     v +-+         |
    +----v-----~~~-v+
    |0 0 a b c . . z|
    +----------~~~--+
*/

It looks like there is no way to improve memory usage with sacrificing preformance, but i wanted to at least put this out there in case anyone knows a way around this.

Edit (because i cant have code in comments):

struct QueueItem
{
    QueueItem* next;
    size_t len;
    void (*data)[];
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    size_t start;
    size_t end; //edit: need to know where to push data. edit: not per-item
    }

/*
    +-----+
    |* * *------------------------------+
    +|-|--+                             |
     v +---+        (2x longer)         v (much longer)
    +------v----+  +-----------+       +---------------+
    |@ 0 0 a b *-->|@ c . . h *-->...->|@ . . . x y z 0|
    +-----------+  +-----------+       +---------------+
*/

Answer 1

First, I think you neglect the cost of allocating the QueueItems. So the allocation costs between your two approaches is the same. (Someone more knowledgeable about memory allocation, please speak up if I'm wrong.)

You can do this to alleviate the wasted space for popped/unfilled items in the array. Make a hybrid of the list and array. Let each list node contain an array of size K.

struct QueueItem
    {
    QueueItem* next;
    void (*data)[K];
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    size_t head;
    size_t end;
    }

Now your performance is dictated by the size you choose for the array. The smaller it is, the less wasted space you have. The larger it is, the less your QueueItem overhead costs you as a percentage of overall space. If you knew, say, that your queue will usually be of size N, then you might choose K to be N/10. In that case, the total memory cost is N/K + 4 + N. The maximum amount of space you can waste in the arrays on unused elements is 2*K - 2.

Usage patterns will dictate actual performance. But if you can anticipate your usage pattern, you can choose a K that works well. There might even be a way to adaptively choose K differently for each node to get even better performance, but I think that's beyond me right now.

Answer 2

If Your queue has a maximum capacity and You only manipulate its front or tail, I would use a Circular Array. The following image is from the linked site and illustrates the idea behind circular arrays:

To quote:

• Rear of the queue is somewhere clockwise from the front
• To enqueue an element, we move rear one position clockwise and write the element in that position
• To dequeue, we simply move front one position clockwise
• Queue migrates in a clockwise direction as we enqueue and dequeue emptiness and fullness to be checked carefully.

With this kind of data structure You obviously can't insert elements between two sequent elements already stored and You can't surpass a certain maximum capacity - I hope it suits Your needs.