How to Build a Queue Using Buffered Channels in Go

In this post, we'll look at how to implement a queue using a buffered channel. For those less familiar, a channel in Go is a way to send and receive data across concurrent goroutines.

The difference between a buffered and non-buffered channels is, that for unbuffered channels, send and receives block until the other side is ready - making communication more synchronous in nature. For buffered channels, sending and receiving can be done more asynchronously - with blocking only happening when attempting to send when a channel is full or reading when a channel is empty.

Design

Let's start with a basic interface for our queue - just two methods for enqueuing and dequeuing values.

type Queue interface {
	Enqueue(val int) error
	Dequeue() (int, error)
}

Implementation

To start off we need to specify a maximum buffer size we want for the queue. For our example, let's keep it relatively small so we can see what happens when it gets full and how we need to adjust our code to handle some edge cases.

A naive approach would look like this:

type BQueue struct {
	channel chan int
}

func NewQueue(capacity int) Queue {
	return &BQueue{
		channel: make(chan int, capacity),
	}
}

func (q *BQueue) Enqueue(val int) error {
	q.channel <- val
	return nil
}

func (q *BQueue) Dequeue() (int, error) {
	return <-q.channel, nil
}

What we're doing here is sending a value to the channel when Enqueue is called and receiving a value that we'll return when Dequeue is called.

Test

In our main function, we'll add a couple of values to our queue, read one, and then fill it up past capacity to see how it reacts.

func main() {

	queue := NewQueue(2)

	fmt.Println(queue.Enqueue(1))
	fmt.Println(queue.Enqueue(2))
	fmt.Println(queue.Dequeue())
    
	fmt.Println(queue.Enqueue(3))
	fmt.Println(queue.Enqueue(4))
}

By running the above, it results in this:

<nil>
<nil>
1 <nil>
<nil>
fatal error: all goroutines are asleep - deadlock!

The reason this happens is because buffered channels will block when the buffer is full.

This also happens when the buffered channel is empty. When we run the following code, we'll end up in a deadlock as well:

func main() {

	queue := NewQueue(2)

	fmt.Println(queue.Dequeue())
}

This results in:

fatal error: all goroutines are asleep - deadlock!

Patch

To patch our implementation so that channel reads and writes become non-blocking and don't result in a deadlock, all we have to do is use a select statement with a default case.

A select will wait until one of its cases can run. So, if we update our Enqueue function to this:

func (q *BQueue) Enqueue(val int) error {
	select {
	case q.channel <- val:
		return nil
	default:
		return ErrQueueFull
	}
}

What this will do is attempt to enqueue a value to our queue and, if it can't, it will return an error.

We need to do the same thing for our Dequeue function:

func (q *BQueue) Dequeue() (int, error) {
	select {
	case val := <- q.channel:
		return val, nil
	default:
		return 0, ErrQueueEmpty
	}
}

All we're doing is attempting to read a value from the channel. If that fails, the only case that can run is the default case and so if the channel is empty, it will return an error instead of waiting for a value to become available.

The updated implementation looks like this:

var (
	ErrQueueEmpty = errors.New("queue empty")
   	ErrQueueFull  = errors.New("queue full")
)

type BQueue struct {
	channel chan int
}

func NewQueue(capacity int) Queue {
	return &BQueue{
		channel: make(chan int, capacity),
	}
}

func (q *BQueue) Enqueue(val int) error {
	select {
	case q.channel <- val:
		return nil
	default:
		return ErrQueueFull
	}
}

func (q *BQueue) Dequeue() (int, error) {
	select {
	case val := <- q.channel:
		return val, nil
	default:
		return 0, ErrQueueEmpty
	}
}

Now, when we run our function:

func main() {

	queue := NewQueue(2)

	fmt.Println(queue.Dequeue())

	fmt.Println(queue.Enqueue(1))
	fmt.Println(queue.Enqueue(2))
	fmt.Println(queue.Enqueue(3))

	fmt.Println(queue.Dequeue())
	fmt.Println(queue.Dequeue())
	fmt.Println(queue.Dequeue())
}

We'll see this in the output:

0 queue empty
<nil>
<nil>
queue full
1 <nil>
2 <nil>
0 queue empty

And that's it! I hope this has helped you develop a better understanding of how buffered channels work.