priority_queue_with_linked_list.go

package main

import (
	"fmt"
)

type QueueNode struct {
	value    interface{}
	priority int
	next     *QueueNode
}

type PriorityQueue struct {
	head    *QueueNode
	maxSize int
	size    int
}

//...
func main() {
	pq := PriorityQueue{}
	pq.SetMaxSize(10)
	pq.Enqueue(1, 5)
	pq.Enqueue(5, 2)
	pq.Enqueue(6, 3)
	pq.Enqueue(10, 1)
	pq.Enqueue(8, 2)

	pq.Display()              //Returns [10,5,8,6,1]
	fmt.Println(pq.Dequeue()) //Returns {10 1 0xc000096040}
	fmt.Println(pq.Dequeue()) //Returns {5 2 0xc0000960a0}
	fmt.Println(pq.Dequeue()) //Returns {8 2 0xc000096060}
	fmt.Println(pq.Peek())    //Returns {6 3 0xc000096020}
	pq.Display()              //Displays [6,1]
}

// Sets the max-size of the priority queue
func (p *PriorityQueue) SetMaxSize(maxSize int) {
	p.maxSize = maxSize
}

// Checks if the priority queue is empty
func (p *PriorityQueue) IsEmpty() bool {
	return p.size == 0
}

// Enqueue operation, add a new element to the priority queue
func (p *PriorityQueue) Enqueue(el interface{}, priority int) {
	if p.size == p.maxSize {
		panic("Queue is full.")
	}
	newQueueNode := &QueueNode{}
	newQueueNode.value = el
	newQueueNode.priority = priority

	if p.IsEmpty() {
		p.head = newQueueNode
		p.size++
		return
	}

	ptr := p.head
	// Traverse through the linked-list to search for the correct position of the new element based on the priority
	if priority < p.head.priority {
		// Special case: If priority of the incoming element is less than that of the head node
		p.head = newQueueNode
		p.head.next = ptr
		p.size++
	} else {
		for i := 0; i < p.size && ptr.next != nil; i++ {
			if ptr.next.priority <= priority {
				ptr = ptr.next
				fmt.Println(ptr.value)
			}
		}

		temp := ptr.next
		ptr.next, newQueueNode.next = newQueueNode, temp
		p.size++
	}
}

// Dequeue operation
func (p *PriorityQueue) Dequeue() QueueNode {
	if p.IsEmpty() {
		panic("Queue is empty.")
	}
	// Dequeued element is the head node
	dequeued := *p.head
	// Un-link the head node from the linked-list
	if p.head.next != nil {
		p.head = p.head.next
	} else {
		p.head = nil
	}
	p.size--
	return dequeued
}

// Peek operation
func (p *PriorityQueue) Peek() QueueNode {
	if p.IsEmpty() {
		panic("Queue is empty.")
	}
	// Return the head node
	return *p.head
}

// Display operation
func (p *PriorityQueue) Display() {
	if p.IsEmpty() {
		panic("Queue is empty.")
	}

	arr := make([]interface{}, p.size)
	ptr := p.head
	for i := 0; i < p.size && ptr != nil; i++ {
		arr[i] = ptr.value
		ptr = ptr.next
	}

	fmt.Println("Priority Queue: ", arr)
}