# 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:

Abstract Data Type (ADT) | Data Structure (DT) |
---|---|

Stack | Dynamic Array, Linked List |

Map | Hash map/table, Tree map |

Transportation | Car, Bus, Airplane |

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**

Action | Complexity |
---|---|

Push() | O(1) |

Pop() | O(1) |

Peek() | O(1) |

Search() | O(n) |

**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!