Video:

Implementing a Priority Queue in Go

April 2, 2021

Course Instructor: Elliot Forbes

Hey Gophers! My name is Elliot and I'm the creator of TutorialEdge and I've been working with Go systems for roughly 5 years now. Feel free to reach out to me on twitter - @Elliot_F

👋 Welcome Gophers, in this tutorial we are going to be looking at how you implement a Priority Queue data structure in Go. We’ll be taking what we learned in the previous few videos of this course one step further and updating our Enqueue and Dequeue methods so that they follow the Priority Queue specifications!

Implementing a Priority Queue in Go

With the high level overview out of the way, let’s look at how we can implement our own version of a Priority Queue in Go:

package main

type PriorityQueue struct {
  High []int 
  Low []int
}

We’ll be effectively using 2 arrays within our PriorityQueue struct to store the varying priority items.

Dequeue

With this in place, let’s look at how we can implement the dequeue function and how it will differ from our standard Queue implementation.

// Dequeue - returns the first element from our queue
func (q *PriorityQueue) Dequeue() (int, error) {
	// if the length of the high priority != 0
	// return the first element from the high priority queue
	// otherwise if the length of the low priority != 0
	// return the first element from the low priority queue

	if len(q.High) != 0 {
		var firstElement int
		firstElement, q.High = q.High[0], q.High[1:]
		return firstElement, nil
	}

	if len(q.Low) != 0 {
		var firstElement int
		firstElement, q.Low = q.Low[0], q.Low[1:]
		return firstElement, nil
	}

	return 0, errors.New("empty queue")
}

So, in this func, we effectively need to check the High priority slice and if that contains an element, then we return the first element from there. If that is empty, then we move on to the Low priority queue and start dequeue elements from that slice.

Enqueue

We also need to make some modifications to our Enqueue function and ensure that it can handle this differing priorities:

// Enqueue - add an element of type int to the end of our queue
func (q *PriorityQueue) Enqueue(elem int, highPriority bool) {
	if highPriority {
		q.High = append(q.High, elem)
	} else {
		q.Low = append(q.Low, elem)
	}
}

Perfect, we now have a mechanism that allows us to Enqueue and Dequeue from either the high or low queues within our Priority queue object.

Peek, Length and IsEmpty

Let’s finish off our PriorityQueue implementation by modifying the final methods we brought forward from our Queue implementation:

// Length - returns the length of our queue
func (q *PriorityQueue) Length() int {
	return len(q.High) + len(q.Low)
}

// Peek - returns the first element from our queue without updating queue
func (q *PriorityQueue) Peek() (int, error) {
	if len(q.High) != 0 {
		return q.High[0], nil
	}
	if len(q.Low) != 0 {
		return q.Low[0], nil
	}
	return 0, errors.New("empty queue")
}

// IsEmpty - return true if queue is empty
func (q *PriorityQueue) IsEmpty() bool {
	return q.Length() == 0
}

With these changes in place, we now have a fully functioning Priority queue implementation that we can use!

package main

import (
	"errors"
	"fmt"
)

// PriorityQueue - our representation of a queue data structure
type PriorityQueue struct {
	High []int
	Low  []int
}

// Enqueue - add an element of type int to the end of our queue
func (q *PriorityQueue) Enqueue(elem int, highPriority bool) {
	if highPriority {
		q.High = append(q.High, elem)
	} else {
		q.Low = append(q.Low, elem)
	}
}

// Dequeue - returns the first element from our queue
func (q *PriorityQueue) Dequeue() (int, error) {
	// if the length of the high priority != 0
	// return the first element from the high priority queue
	// otherwise if the length of the low priority != 0
	// return the first element from the low priority queue

	if len(q.High) != 0 {
		var firstElement int
		firstElement, q.High = q.High[0], q.High[1:]
		return firstElement, nil
	}

	if len(q.Low) != 0 {
		var firstElement int
		firstElement, q.Low = q.Low[0], q.Low[1:]
		return firstElement, nil
	}

	return 0, errors.New("empty queue")
}

// Length - returns the length of our queue
func (q *PriorityQueue) Length() int {
	return len(q.High) + len(q.Low)
}

// Peek - returns the first element from our queue without updating queue
func (q *PriorityQueue) Peek() (int, error) {
	if len(q.High) != 0 {
		return q.High[0], nil
	}
	if len(q.Low) != 0 {
		return q.Low[0], nil
	}
	return 0, errors.New("empty queue")
}

// IsEmpty - return true if queue is empty
func (q *PriorityQueue) IsEmpty() bool {
	return q.Length() == 0
}

func main() {
	fmt.Println("Queues Section")

	queue := PriorityQueue{}

	fmt.Println(queue)
	queue.Enqueue(1, true)
	fmt.Println(queue)
	queue.Enqueue(10, false)
	fmt.Println(queue)

	elem, _ := queue.Dequeue()
	fmt.Println(elem)
	fmt.Println(queue)

	queue.Enqueue(2, true)
	fmt.Println(queue)

	elem, _ = queue.Dequeue()
	fmt.Println(elem)
	fmt.Println(queue)

	elem, _ = queue.Dequeue()
	fmt.Println(elem)
	fmt.Println(queue)

}

Conclusion

Awesome, so in this tutorial, we have effectively managed to implement our own version of a Priority Queue in Go. In the next video of this course, we’ll be taking a look at the Stack data structure in-depth.