What is the best data structure to implement a queue? [closed]

Question

I only need the operations enque and dequeue.

Answer 1

From a theoretical standpoint, a singly-linked list with both a head and a tail. Remove from the front, append to the tail. There you have the theoretical O(1) constant-time complexity (even for worst-case) with less storage than a doubly-linked list.

From a practical standpoint, a growable array-based contiguous structure can perform better using circular indexing. The hardware excels at dealing with contiguous memory due to the spatial locality (cache lines that fit multiple adjacent elements, e.g.). Those have a worse algorithmic complexity with only amortized constant time and a worst-case linear-time complexity (though it's so infrequent that it generally doesn't matter very much).

Also from a practical standpoint, an unrolled list could work well (basically arrays of multiple elements stored in nodes that are linked together, giving you the locality of reference + guaranteed constant-time enqueues and dequeues).

"Best" is really hard to say here since it depends on your needs.

For example, the singly-linked list with a tail has the weakness of allocation/deallocation overhead per node and the lost locality of reference, unless you back that with an efficient, contiguous allocator that helps mitigate these weaknesses. It also pays a memory overhead of a list pointer/ref per element (plus potentially some more due to the separate allocations per node). As pointed out in the comments, linked lists are generally nowhere near as good as they sound because they don't line up quite as well (at least without a lot of help from an allocator) with the actual nature of the hardware.

The circular array has a weakness where it needs excess capacity to reduce the number of reallocations (or else that worst-case linear time complexity is going to kick in more frequently) and copies (though they could be shallow in some cases). Also since it's just one big contiguous memory block, if you're working with enormous data sets, you could get out of memory errors even on a machine with virtual addressing (out of memory doesn't necessarily mean all memory has been used up in such cases, it means that a contiguous set of unused pages matching the requested size wasn't found).

The unrolled list mitigates the list pointer and node allocation overhead but stores some excess capacity in nodes which could be quite wasteful if you're, say, using an unrolled list with the capacity to store 64 elements per node and you're just storing 3 elements in your queue.

Answer 2

You could use an array (continuous spaces in memory) You could also use a linked list (not necessarily continous)

Array and its fancier derivatives (ArrayList, vector, etc) may be more complicated. They aren't as efficient because if you start adding too many elements, you may run out of continous memory space and you will have to copy everything in your queue over to a new block of memory.

A linked list to me seems pretty efficient as long as you keep track of the front and back (head and tail, whatever you want to call it).

This may help: https://www.cs.bu.edu/teaching/c/queue/linked-list/types.html