A queue is a FIFO (first-in, first-out) container. The two main operations are:
- Enqueue / Push — add to the back.
- Dequeue / Pop — remove from the front.
Two implementations and why we pick one
| Backing structure | Push | Pop | Notes |
|---|---|---|---|
append + s = s[1:] |
O(1) | O(1) | Memory leak: backing array never shrinks. |
append + slice copy |
O(1) | O(n) | Simple, slow. |
| Linked list | O(1) | O(1) | Per-node allocation, GC pressure. |
| Ring (circular) buffer | O(1) amortized | O(1) | Cache-friendly, what we use. |
A ring buffer is a fixed-size array indexed modulo its length, with head
and tail cursors and a count n. When it gets full, we double the
backing array and re-linearize the elements.
buf: [_ _ a b c _ _ _]
head=2, tail=5, n=3, cap=8
After Push(d), Push(e), Push(f):
buf: [_ _ a b c d e f]
head=2, tail=0, n=6
Complexity
| Op | Time |
|---|---|
| Push | Amortized O(1) |
| Pop | O(1) |
| Len | O(1) |
| Peek | O(1) |
Real-world uses
- BFS over graphs and trees.
- Producer / consumer pipelines.
- Task / job queues, message queues.
- Rate limiting (token bucket / leaky bucket conceptually).
Run the tests
go test ./part2-dsa/ds/queue