Data Structure Series - Queues

First In, First Out

Data Structure Series - Queues

This article is part of the Data Structures using Go series and it is about implementing a Queue in Go.

The first step will be to define the operations which can be performed and below is the list for the same.

Push: Inserts an element to the end of the queue.

Pop: Removes the element from the front of the queue. Panics if there is no element to pop.

Front: Returns the element in the front of the queue. Panics if there is no element to return.

Utility method:

IsEmpty: Returns a boolean denoting whether the queue is empty of not.

Note: The example taken is of a queue of int data type

To start with the implementation, defining an interface will help with a clean and extendable approach.

type IQueue interface {
    Push(val int)
    Pop()
    Front() int
    IsEmpty() bool
}

The next step is to define the struct with the required fields.

type Queue struct {
    elems []int
}

To actually make the Queue struct an implementation of the interface, we have to add required methods for the operations mentioned in the beginning.

We start with defining the Push method.

func (q *Queue) Push(val int) {
    q.elems = append(q.elems, val)
}

Next, we define the Pop method.

func (q *Queue) Pop() {
    if q.IsEmpty() {
        // panic in case of invalid pop
        panic("Cannot remove element from empty queue")
    }
    q.elems = q.elems[1:]
}

Following it is to define the Front method which will return the element at the Front of the queue.

func (q *Queue) Front() int {
    if q.IsEmpty() {
        // panics in case there is no front element to return
        panic("cannot reference front element of empty queue")
    }
    return q.elems[0]
}

In the end, we define the IsEmpty method.

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

With defining all the methods to the struct, it is now an implementation of the interface IQueue and provides the basic operations of the queue and now a function can be defined to return an instance of the struct with the initializations.

func NewQueue() IQueue {
    return &Queue{
        elems: make([]int, 0), // empty slice of type int
    }
}

Example:

func main() {
    q := NewQueue()
    q.Push(1)
    q.Push(2)
    fmt.Println(q.Front()) // prints 1
    q.Pop()
    fmt.Println(q.Front()) // prints 2
}

As a next step, feel free to try out this question on leetcode.com .