Sebastian Gomez

Apr 16, 2023

Updated: Jun 25, 2026

Data Structures in Go: Deque

Deques, or double ended queues, are versatile data structures that let us insert and remove elements from both the front and the back. In this post we will explore the main features of this structure, its history, and a few examples of how it is used in computing problems.

A note on the name. Throughout this post we use deque (short for "double ended queue"). Watch out for a very common mistake: "dequeue" is not the structure but the operation of removing an element from a queue. The structure is called a deque, and the type we implement is called Deque.

What is a deque

A deque is a type of data structure that lets you insert and remove elements from both the front and the back. This makes it similar to a queue or a stack, but with the extra flexibility of adding or removing elements at either end. That is why it is so useful in many algorithms and situations where we need efficient insertion and removal at both ends.

A bit of history

The concept of the deque became popular in the algorithms literature in the mid 20th century, as the first linear data structures started to be formalized. Donald Knuth describes and analyzes it in The Art of Computer Programming, where it appears as a natural generalization of the queue and the stack.

Since then, the deque has been widely used across many areas of computing, from systems programming to graph algorithms and real time data processing.

Code example in Go

Let's look at an implementation of a deque in Go. To keep it clear and correct, we will back it with a slice. Each operation relies on Go's native slice functions, so it is easy to read and, above all, it runs with no surprises.

Note. The original code in this post tried to mix a fixed size circular buffer with a slice that grew via append. Those two models do not fit together and the program ended with an index out of range panic. Here we pick a single model, backing the deque with a slice, which is simpler and always consistent.

package main

import (
	"errors"
	"fmt"
)

// Deque is a double ended queue backed by a slice.
type Deque struct {
	items []int
}

// NewDeque creates a new empty deque and returns a pointer to it.
func NewDeque() *Deque {
	return &Deque{items: make([]int, 0)}
}

// Size returns the number of elements in the deque.
func (d *Deque) Size() int {
	return len(d.items)
}

// IsEmpty reports whether the deque has no elements.
func (d *Deque) IsEmpty() bool {
	return len(d.items) == 0
}

// PushFront inserts an element at the front of the deque.
func (d *Deque) PushFront(item int) {
	d.items = append([]int{item}, d.items...)
}

// PushBack inserts an element at the back of the deque.
func (d *Deque) PushBack(item int) {
	d.items = append(d.items, item)
}

// PopFront removes and returns the element at the front.
func (d *Deque) PopFront() (int, error) {
	if d.IsEmpty() {
		return 0, errors.New("the deque is empty")
	}
	item := d.items[0]
	d.items = d.items[1:]
	return item, nil
}

// PopBack removes and returns the element at the back.
func (d *Deque) PopBack() (int, error) {
	if d.IsEmpty() {
		return 0, errors.New("the deque is empty")
	}
	last := len(d.items) - 1
	item := d.items[last]
	d.items = d.items[:last]
	return item, nil
}

func main() {
	deque := NewDeque()

	// Insert elements at the front and at the back of the deque.
	deque.PushFront(1)
	deque.PushBack(2)
	deque.PushBack(3)
	deque.PushFront(0)

	// Print the elements in the deque.
	fmt.Println("Elements in the deque:")
	n := deque.Size()
	for i := 0; i < n; i++ {
		item, err := deque.PopFront()
		if err != nil {
			break
		}
		fmt.Println(item)
	}
}

Notice an important detail in main. Before iterating we take a snapshot of the size with n:= deque.Size(). If we used deque.Size() directly in the for condition, each PopFront would shrink the size inside the loop and we would only walk through half of the elements. Reading n once spares us that classic bug.

If you run the program, the output will be:

Elements in the deque:
0
1
2
3

A note on performance. With this slice backed implementation, PushFront and PopFront shift elements, so they are O(n). That is perfectly fine for learning and for small volumes. If you need all four operations in amortized O(1), the usual approach is a circular buffer with head and tail indices and growth by doubling, or a doubly linked list with the standard library's container/list.

Use cases for deques

Deques are useful in a wide variety of computing problems. Here are some of the most common uses:

• LRU cache: we can implement a fixed size cache where, once the limit is reached, the least recently used elements are removed from one end while new ones are added at the other.
• Sliding window processing: in problems like the sliding window maximum, a monotonic deque lets us keep candidates and discard the stale ones in amortized constant time.
• Graph and tree traversals: a deque can act as a queue in a breadth first search (BFS) or as a stack in a depth first search (DFS), using one end or the other as needed.
• Text editing and undo or redo: we can model a history of operations where elements are inserted and removed at both ends.

These are just a few examples; the versatility of deques makes them applicable to many other computing problems.

Conclusion

In short, a deque is a useful and versatile data structure that we can use in many computing problems. We hope this introduction gave you a good idea of what deques are and how to implement them in Go. If you have questions or comments, do not hesitate to leave them below.

Exercises to practice

Here are some exercises so you can practice the Deque structure in Go. To make it a good modern Go challenge, I suggest implementing them with generics, so that your deque works with any type (Deque[T any]) instead of being tied to int. When you are done, send your solution as a Pull request to this repository: Go Para Principiantes.

1. Implement a function NewDeque[T any]() that creates a new empty deque and returns a pointer to it.
2. Implement a method Size() int that returns the number of elements in the deque.
3. Implement a method IsEmpty() bool that returns true if the deque is empty and false otherwise.
4. Implement a method PushFront(value T) that adds an element to the front of the deque.
5. Implement a method PushBack(value T) that adds an element to the back of the deque.
6. Implement a method PopFront() (T, error) that removes and returns the front element. If the deque is empty, return an error.
7. Implement a method PopBack() (T, error) that removes and returns the back element. If the deque is empty, return an error.
8. Implement a method Front() (T, error) that returns the front element without removing it. If the deque is empty, return an error.
9. Implement a method Back() (T, error) that returns the back element without removing it. If the deque is empty, return an error.
10. Write a program that uses all the functions above to perform various operations on deques, such as adding and removing elements, checking whether it is empty, and getting the size.

Hint. Generics arrived in Go 1.18. If you declare type Deque[T any] struct { items []T }, all the methods from the example above adapt with almost no changes; just replace int with the type parameter T.

3-point summary

1. A deque is a double ended queue that lets you insert and remove elements at both ends; do not confuse it with "dequeue", which is the operation of removing from a queue.
2. The simplest and always correct implementation in Go is to back it with a slice; for amortized O(1) at both ends, prefer a circular buffer or container/list.
3. Deques shine in LRU caches, sliding windows, graph traversals (BFS and DFS), and edit histories.

That's all. I hope this post is useful to you and that you can apply it to a project you have in mind. Leave me a comment if it helped, if you want to add an opinion, or if you have any questions. And remember, if you liked it, you can also share it using the social links below. Good luck, and keep coding.