I’ve recently started playing around with Go again so I decided to try implementing a few basic data structures to get a better feel for the language. To kick things off I kept it super simple by starting with stacks and queues.

Stacks

A stack is a collection of items that maintains a last in, first out ordering (LIFO) and exposes two operations — push and pop. In other words, popping an item off the stack will return the item that was most recently pushed onto the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

package stack

type Stack struct {
	data interface{}
	top  *Stack
	next *Stack
}

func (s *Stack) Push(v interface{}) {
	n := &Stack{data: v}
	n.next = s.top
	s.top = n
}

func (s *Stack) Pop() interface{} {
	t := s.top
	s.top = t.next
	return t.data
}

There are a few ways to implement a stack, but code above use a linked list to represent the nodes. Each node has a data property, which is used to store the items push onto the stack. They also have next and top properties that are pointers to other nodes in the stack. top is used by the root node to determine which item is currently at the top of the stack. next is used to link each of the nodes to each other so the rest of the items can be promoted to top once their parents have been popped.

To push items on to a stack we need to create a new node with the item’s value, assign its next property to be the node which is currently on top of the stack, and finally make this new node the top. To pop an item from a stack we first store a reference to the current top. We then make its next property the new top and then return its data.

You can see this in action with the tests below. We push a range of integers onto a stack and then test they pop off in reverse order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

package stack

import "testing"

func TestStack(t *testing.T) {
	tests := []int{1, 2, 3, 4, 5}
	s := Stack{}

	for _, i := range tests {
		s.Push(i)
	}

	for index, _ := range tests {
		top := s.Pop()
		expected := tests[len(tests)-(index+1)]

		if top != expected {
			t.Error(top, "should equal", expected)
		}
	}
}

Queues

A queue is also a collection of items, but it maintains the oppostite ordering from a stack: first in, first out (FIFO). Queues support enqueue and dequeue, which add and remove items from the queue respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package queue

type Queue struct {
	data  interface{}
	front *Queue
	back  *Queue
}

func (q *Queue) Enqueue(v interface{}) {
	n := &Queue{data: v}

	if q.front == nil {
		q.front = n
		q.back = n
	} else {
		q.back.front = n
		q.back = n
	}
}

func (q *Queue) Dequeue() interface{} {
	f := q.front
	q.front = f.front
	return f.data
}

I’ve opted to implement a queue using linked lists, but again other options will also work. Each queue node has a data property that is used to store the queued item, a front pointer to the current head of the queue, and a back pointer to the item that’s at the end of the queue.

To add an item to the queue we call enqueue, which creates a new node and then either adds it to the front and the back of the queue if it’s the only item, otherwise it adds it adds it to the back of the queue making sure to link it to the previous back node.

To remove an item we call dequeue. This stores a list to the current front node and sets its front node as the new head of the queue. Finally, it returns the data property of the node we removed from the queue.

Again, we can test this by adding items onto the queue and checking they come out in the expected order — this time the same order they were added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

package queue

import "testing"

func TestQueue(t *testing.T) {
	q := Queue{}
	tests := []int{1, 2, 3, 4, 5}

	for _, i := range tests {
		q.Enqueue(i)
	}

	for _, i := range tests {
		actual := q.Dequeue()
		expected := i

		if actual != expected {
			t.Error(actual, "should equal", expected)
		}
	}
}

Conclusion

These implementations are far from complete. They don’t support many useful operations like peek, which allows you to see which item is next without actually removing it. There are also a few obvious edge cases that aren’t handled — e.g. calling dequeue on an empty queue. However, I found this a pretty useful exercise to get a better feel for go.