Data Structures: 2. Queues

Mar 20, 2022

Introduction #

Queues, in there simplest form, are like stacks, except that the first element in is the first element out, or FIFO (First In First Out). It’s a bit like a stack of plates were you alway put on the top of the stack but if you remove a plate you take it from the bottom.

As noted for stacks, we are using any type instead of a specific type like string or int. This means we don’t have to write different stacks for different types.

Solution #

package main

import "fmt"

type Queue struct {
    queue []any
}

func (q *Queue) IsEmpty() bool {
    return len(q.queue) == 0
}

func (q *Queue) SizeOf() int {
    return len(q.queue)
}

func (q *Queue) Push(v any) {
    q.queue = append(q.queue, v)
}

func (q *Queue) Peek() (v any, err error) {

    if q.IsEmpty() {
        return "", fmt.Errorf("Queue is empty")
    }

    v = q.queue[0]

    return v, nil
}

func (q *Queue) Pop() (v any, err error) {

    if q.IsEmpty() {
        return "", fmt.Errorf("Queue is empty")
    }

    v = q.queue[0]
    q.queue = q.queue[1:len(q.queue)]

    return v, nil
}

func main() {
    q := &Queue{
        queue: make([]any, 0),
    }

    fmt.Printf("Initial size of Queue: %d\n", q.SizeOf())
    fmt.Printf("Queue is empty?: %v\n", q.IsEmpty())
    fmt.Println("Push three items ('One', 'Two', 'Three') onto the queue")

    q.Push("One")
    q.Push("Two")
    q.Push("Three")

    fmt.Printf("Size after pushing three elements: %d\n", q.SizeOf())
    fmt.Printf("Queue is empty?: %v\n", q.IsEmpty())

    if head, err := q.Peek(); err == nil {
        fmt.Printf("Peek: Current head element: %v\n", head)
    }

    fmt.Println("Now pop the three elements")

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    fmt.Println("Queue should now be empty, so another pop should not work")

    if _, err := q.Pop(); err != nil {
        fmt.Printf("Pop: %s\n", err)
    }

    fmt.Printf("Size of Queue: %d\n", q.SizeOf())
    fmt.Printf("Queue is empty?: %v\n", q.IsEmpty())

    fmt.Println("Now push another three entires onto the queue (1, 2, 3)")

    q.Push(1)
    q.Push(2)
    q.Push(3)

    fmt.Printf("Size after pushing three elements: %d\n", q.SizeOf())
    fmt.Printf("Queue is empty?: %v\n", q.IsEmpty())

    if head, err := q.Peek(); err == nil {
        fmt.Printf("Peek: Current head element: %v\n", head)
    }

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := q.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    fmt.Println("Queue should now be empty, so another pop should not work")

    if _, err := q.Pop(); err != nil {
        fmt.Printf("Pop: %s\n", err)
    }

    fmt.Printf("Size of queue: %d\n", q.SizeOf())
    fmt.Printf("Queue is empty?: %v\n", q.IsEmpty())
}

Testing #

Initial size of Queue: 0
Queue is empty?: true
Push three items ('One', 'Two', 'Three') onto the queue
Size after pushing three elements: 3
Queue is empty?: false
Peek: Current head element: One
Now pop the three elements
Pop: One
Pop: Two
Pop: Three
Queue should now be empty, so another pop should not work
Pop: Queue is empty
Size of Queue: 0
Queue is empty?: true
Now push another three entires onto the queue (1, 2, 3)
Size after pushing three elements: 3
Queue is empty?: false
Peek: Current head element: 1
Pop: 1
Pop: 2
Pop: 3
Queue should now be empty, so another pop should not work
Pop: Queue is empty
Size of queue: 0
Queue is empty?: true