Stack - data type implementation in go

Before we begin looking at the stack, let’s first explain what is the stack:

A stack is an abstract data type that holds an ordered, linear sequence of items.

Stack is a Abstract Data Type. A key difference between abstract data type (ADT) and data structure (DT) is that ADT provides an abstraction for DT. An abstraction provides an interface that does not give any details about how something should be implemented.

Let’s take an example:

This means a stack can be implemented using an array or linked list. We are going to implement our stack in a linked list. The key benefit of using a linked list over an array is that with an array we will need to take care of allocation and size. If an array is full, we will need to extend it and then perform the operation.

Big O for Stack

Where stack is used?

If you are reading this on a browser, probably your browser uses a stack to perform the back-forth operation. Most text editors use stack to perform the history of changes so you can undo them. In programming, it can be used by the runtime to support recursion by keeping track of function calls.

Stack is everywhere :)

Linked List

Before implementing stack, we will need to implement a linked list where we are going to provide an abstraction (a function) that can be called to perform stack operations. The 2 main operations that we will support are:

• Push()
• Pop()

since they are most common.

Ok, so we know that a linked list is a data structure and contains data and pointer to the next node. So, implementation in go:

package main

type LinkedList struct {
	Head *Node
}

type Node struct {
	Data int
	Next *Node
}

The start of the linked list is called Head and the end of the list is called Tail. Every Node contains data (in this case integer) and a pointer to the Next node.

Stack

Now, let’s implement our 2 functions:

Push

func (l *LinkedList) Push(data int) {
	// we are at the head, create
	if l.Head == nil {
		// our head points now to node and next node is nil
		l.Head = &Node{Data: data}
		return
	}

	// create temp variable for our head
	tmp := l.Head
	// our head now points to new node
	l.Head = &Node{Data: data}
	// dont forget about tmp!
	l.Head.Next = tmp
}

Pop

func (l *LinkedList) Pop() int {
	// we dont have anything here
	if l.Head == nil {
		return -1
	}
	// get the data value
	data := l.Head.Data
	// replace head with the next head
	l.Head = l.Head.Next
	return data
}

Let’s do a quick function to check if our head is empty

func (l *LinkedList) IsEmpty() bool {
	return l.Head == nil
}

Now we can provide some example input and observe the result

func main() {
	stack := &LinkedList{}
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)

	for !stack.IsEmpty() {
		fmt.Println(stack.Pop())
	}
}

This will print 3, 2 and 1. We can notice that stack data type follows the LIFO method

LIFO is a method of processing data where the data last received is the first to be sent out after processed

Example case Given an integer, return its binary representation in an array. For example:

• 4, in binary is 100
• 7, in binary is 111
• 22, in binary is 10110

The naive approach to this will be to dive the number with 2, get its remaining, push that value into an array, and finally reverse the array.

func SolutionLinear(in int) []int {
	var out []int
	for in > 0 {
		r := in % 2
		in /= 2
		out = append(out, r)
	}
	for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
		out[i], out[j] = out[j], out[i]
	}
	return out
}

but, with stack, we can do something like:

func SolutionStack(in int) []int {
	var out []int
	stack := &LinkedList{}
	for in > 0 {
		r := in % 2
		in /= 2
		stack.Push(r)
	}
	for !stack.IsEmpty() {
		out = append(out, stack.Pop())
	}
	return out
}

That’s it about the stack data type.

Happy coding!