Mark's BackyardQueue Implementation Approaches: From Constraints to a Decision Tree
AI translation notice: This English version was translated from the original Chinese article with AI assistance. Some nuances may differ from the original.
Recently, while reviewing data structures, I realized that I keep getting it wrong when mapping a logical structure onto its physical counterpart—that is, when picking an implementation. I searched online for guidance, but nothing out there was especially easy to grasp, so I built a decision tree myself. Now I have a rough mental picture, and quite a few ideas have fallen into place.
Key Constraints in the Decision Tree
When drawing this tree, I fixed the following decision dimensions (which are also high-frequency exam topics on the 408):
- Storage method: sequential / linked
- Whether circular: solves both “false overflow” and “access at both ends”
- List type: singly / doubly linked
- Pointer setup: head pointer / tail pointer / both head and tail pointers
- Header node: whether to introduce a sentinel node to simplify boundary cases
The single most important rule of thumb here is:
A non-circular structure must have both a head and a tail pointer; only a circular structure can possibly get by with a single pointer.
Performance Comparison of Each Implementation
| Implementation | Empty check | Full check | Enqueue | Dequeue | Space overhead | Recommendation |
|---|---|---|---|---|---|---|
| Sequential circular queue | front == rear | (rear+1)%M == front | O(1) | O(1) | Low | ⭐⭐⭐ |
| Non-circular singly linked + head & tail (with header node) | front->next == NULL | None | O(1) | O(1) | Medium | ⭐⭐⭐ |
| Non-circular singly linked + head & tail (no header node) | front == NULL | None | O(1) | O(1) | Medium | ⭐⭐ |
| Circular singly linked + tail pointer only ⭐ | rear->next == rear | None | O(1) | O(1) | Lowest | ⭐⭐⭐⭐⭐ |
| Circular doubly linked + tail pointer only | rear->next == rear | None | O(1) | O(1) | High | ⭐⭐⭐ |
| Circular doubly linked + head & tail | front == NULL | None | O(1) | O(1) | Highest | ⭐⭐ |
An Easily Overlooked Detail: The Header Node
A header node exists not to “save time” or “save space,” but to eliminate the special case of an empty queue:
- Linked queue: once the queue is emptied,
rearis liable to dangle, so keeping a header node is safer. - Linked stack: the operations are uniform,
top == NULLis already clear enough, and skipping the header node is simpler. - Circular linked queue: the closed-loop structure handles the boundary cases on its own, so a header node usually isn't needed.
The Physical and Logical Relationship of a Stack
A stack comes in two kinds: the sequential stack (array-based) and the linked stack (singly linked list).
Using a doubly linked list is completely unnecessary—it's overkill. And the best choice for a stack is unique, namely the case below:
- Operations happen at the head of the list
- Only a head pointer
- No header node
- Singly linked
- Non-circular
- Author:Mark Xu
- Copyright:All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating otherwise.