A queue is first-in-first-out: the earliest value pushed is the first one out. Go has no built-in Queue type; Enqueue appends to the end, Dequeue removes from the front.
The rule
First in, first out
Values come out in the order they went in.
- Enqueue: add a value to the back.
- Dequeue: take the front value off and hand it back.
- Peek: look at the front value without removing it.
A queue is first-in-first-out: Enqueue adds to the back, Dequeue removes from the front. Try it below.
Purpose
Hold values until the one that has waited longest can be handled.
Input
Values enqueued at the back of a []int, one at a time.
Output
The value that has been waiting longest, handed back by Dequeue.
Constraints
- Dequeuing an empty queue has to be guarded.
- Only the front and the back are reachable.
- Reslicing the front away keeps the whole backing array alive, which is the leak this page covers.
Dequeue reads and removes index 0 by re-slicing past it. This works, but the discarded element isn't actually freed: the underlying array still holds a reference to it.
type Queue []int
func (q *Queue) Enqueue(v int) {
*q = append(*q, v)
}
func (q *Queue) Dequeue() (int, bool) {
if len(*q) == 0 {
return 0, false
}
v := (*q)[0]
*q = (*q)[1:]
return v, true
}Enqueuing 1, 2, 3 and dequeuing once removes 1 from the front, leaving [2 3]. Unlike a stack, the value that comes out is the oldest one in, not the newest.
var q Queue
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
v, _ := q.Dequeue()
fmt.Println(v)
fmt.Println(q)Queue operations
| Operation | Behavior |
|---|---|
Enqueue(v) | Appends v to the end of the slice, the back of the queue. |
Dequeue() | Removes and returns the first element. ok is false if the queue is empty. |
len(q) | Number of elements currently queued. |
list.New() | Leak-free alternative: a container/list doubly linked list. |
The slice-backed queue's memory leak
(*q)[1:] only moves the slice header forward; the backing array underneath keeps growing and never shrinks, so a long-running slice-backed queue leaks memory. container/list, a doubly linked list, drops a node immediately on Remove with no leftover backing array. Reach for it once a queue's lifetime is long enough for the leak to matter.
import "container/list"
q := list.New()
q.PushBack(1)
q.PushBack(2)
front := q.Front()
fmt.Println(front.Value)
q.Remove(front)The whole program main.go Show
package main
import "fmt"
type Queue []int
func (q *Queue) Enqueue(v int) { *q = append(*q, v) }
func (q *Queue) Dequeue() (int, bool) {
if len(*q) == 0 {
return 0, false
}
v := (*q)[0]
*q = (*q)[1:]
return v, true
}
func main() {
var q Queue
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
v, _ := q.Dequeue()
fmt.Println(v)
fmt.Println(q)
}The linked-list version dequeues the same 1 first, but each removed node is freed independently instead of lingering in a shared backing array.
$ go run queue.go
1
[2 3]