👋 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.