A stack is a container that supports retrieval by last-in, first-out (LIFO)
order. The *get* and *put* operations for stacks are usually called *push* and
*pop*, other operations may include *peek* and *isEmpty*. A full description of
stacks can be found online here.

*Stacks are simple to implement and very efficient. For this reason, stacks are
probably the right container to use when retrieval order doesn’t matter [Ski08]*

A stack can be easily implemented in Go using slices.

## stack of integers

```
// stack of integers
package stack
type Stack []int
// IsEmpty: check if stack is empty
func (s *Stack) IsEmpty() bool {
return len(*s) == 0
}
// Push a new integer onto the stack
func (s *Stack) Push(x int) {
*s = append(*s, x)
}
// Pop: remove and return top element of stack, return false if stack is empty
func (s *Stack) Pop() (int, bool) {
if s.IsEmpty() {
return 0, false
}
i := len(*s) - 1
x := (*s)[i]
*s = (*s)[:i]
return x, true
}
// Peek: return top element of stack, return false if stack is empty
func (s *Stack) Peek() (int, bool) {
if s.IsEmpty() {
return 0, false
}
i := len(*s) - 1
x := (*s)[i]
return x, true
}
```

We can then use our stack of integers like this

```
func fn() {
var stack Stack
stack.Push(1)
stack.Push(2)
stack.Push(3)
x := stack.Peek() // x = 3
x = stack.Pop() // x = 3
x = stack.Peek() // x = 2
}
```

It is trivial to replace integers with any other type (string, struct, etc).

## stack of anything

One downside to the above method is that a new stack needs to be written for each data type. An alternative is to use the empty interface to allow stacks of anything.

```
// All types satisfy the empty interface, so we can store anything here.
type Stack []interface{}
```

Then any time we pop or peek at an item from the stack we use a type assertion.

```
var stack Stack
stack.Push("this")
item := stack.Pop()
fmt.Printf("%s\n", item.(string))
```

This comes with the usual warnings that using the empty type interface reduces the ability of the compiler to catch type errors, one of the benefits of using a strongly typed language.

Full source code is available here.

Also Douglas Hall has done a nice stack implementation using linked lists instead of slices. You can find his gist here.

#### Bibliography:

[Ski08] - **The Algorithm Design Manual**, Steven S. Skiena

[CLRS09] - **Introduction to Algorithms**, Thomas H.Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein

[Mor] - **Open Data Structures**, Pat Morin, Edition 0.1