## LIFO and FIFO structures

LIFO is an abbreviation for “last in, first out”. While FIFO stands for “first in, first out”. And that’s it. The only important thing about these two terms is to keep them in mind when talking about the following data structures.

## Stacks and Queues

In CS, a Stack is a data structure with two main operations: `push` (or add) and `pop` (or remove). A Stack is a LIFO structure, that means that the order in which the elements come off the Stack is last in, first out. You can think of Stacks in CS as stacks of plates in real life. In fact, that’s usually the comparison that’s always used.

On the other side, a Queue is a FIFO data structure. That means that the first element to come in, should also be the first element to come out. Another difference between a Stack and a Queue is that in a Queue the two main operations are: `enqueue` (`push` in a Stack) and `dequeue` (`pop` in a Stack). You can image a queue of people in a supermarket, for example.

## Why we want to build/use Stacks or Queues

Stacks and Queues are two important data structures for two main reasons (at least for me):

• The principles of LIFO and FIFO are used constantly in programming.
• Some cache systems usually are best understood if these two data structures have been understood first.

Of course, there are many more reasons why its worth learning about these two data structures and the LIFO and FIFO principles. And you’re totally free to do a Google search to find them.

## Building a Stack

The first of the two data structures that we’re going to build is the Stack. First, we will define its most basic component: a Node. Then we will define the Stack itself with a struct and finally we will add the neccesary methods.

In this post the implementation of the Stack will be extremely similar to the implementation of a Doubly Linked List. You can read more about them here.

### Defining a Node

Our implementation of a Node will be very simple and will have:

• A value.
• A pointer to the previous Node.
• A pointer to the next Node.

``````type Node struct {
value int
pre   *Node
next  *Node
}
``````

### Creating our Stack

Our Stack then will be something like:

``````type Stack struct {
first  *Node // First element on the stack.
last   *Node // Last element on the stack.
length int   // Length of the stack.
}
``````

### Push

Now, we’re going to implement the `push` operation:

``````func (s *Stack) Push(n *Node) {
if s.length == 0 {
s.first = n
s.last = n
s.length++
return
}

last := s.last

s.last = n
s.last.pre = last
last.next = n
s.length++
}
``````

### Pop

Now it’s the turn to implement the `pop` method:

``````func (s *Stack) Pop() *Node {
if s.length == 0 {
return nil
}

if s.length == 1 {
node := s.first
s.first = nil
s.length--
return node
}

node := s.last
preLast := s.last.pre
s.last = preLast
preLast.next = nil
s.length--

return node
}
``````

### Peek

If you want, you can also implemente a method called `peek` which only work is to return the first Node in the stack without removing it.

``````func (s *Stack) Peek() *Node {
return s.first
}
``````

### Our final code

``````package main

import "fmt"

type Node struct {
value int
pre   *Node
next  *Node
}

type Stack struct {
first  *Node
last   *Node
length int
}

func (s *Stack) Push(n *Node) {
if s.length == 0 {
s.first = n
s.last = n
s.length++
return
}

last := s.last

s.last = n
s.last.pre = last
last.next = n
s.length++
}

func (s *Stack) Pop() *Node {
if s.length == 0 {
return nil
}

if s.length == 1 {
node := s.first
s.first = nil
s.length--
return node
}

node := s.last
preLast := s.last.pre
s.last = preLast
preLast.next = nil
s.length--

return node
}

func (s *Stack) Peek() *Node {
return s.first
}

func main() {
stack := &Stack{}
firstNode := &Node{value: 1}
secondNode := &Node{value: 2}
thirdNode := &Node{value: 3}

stack.Push(firstNode)
stack.Push(secondNode)
stack.Push(thirdNode)

fmt.Println(stack.Peek())

stack.Pop()
fmt.Println(stack.Peek())

stack.Pop()
fmt.Println(stack.Peek())

stack.Pop()
fmt.Println(stack.Peek())
}
``````

## Building a Queue

Now it’s the turn of the Queue. As with the Stack, the first thing we’re going to define is the Node. Then we will define the Queue itself with a struc and add the neccessary methods.

In this case the implementation of the Queue will be extremely similar to the implementation of a Linked List. You can read more about them here.

### Defining a Node

Our Node will have a value (in this case an `integer`) and a pointer to the next Node if any.

``````type Node struct {
value int
next  *Node
}
``````

### Creating our Queue

Our Queue then, will be something like:

``````type Queue struct {
first  *Node
last   *Node
length int
}
``````

### Enqueue

Now we’re going to add to our Queue the `enqueue` method. Which, if you don’t remember, is equivalent to the `push` method on a Stack.

``````func (q *Queue) Enqueue(n *Node) {
if q.length == 0 {
q.first = n
q.last = n
q.length++
return
}

last := q.last
last.next = n
q.last = n
q.length++
return
}
``````

### Dequeue

Time to implement the `dequeue` method. That again, if you don’t remember, is equivalent to the `pop` method of a Stack.

``````func (q *Queue) Dequeue() *Node {
if q.length == 0 {
return nil
}

node := q.first
q.first = node.next
q.length--
return node
}
``````

### Peek

Finally, our `peek` method:

``````func (q *Queue) Peek() *Node {
return q.first
}
``````

### Our final code

``````package main

import "fmt"

type Node struct {
value int
next  *Node
}

type Queue struct {
first  *Node
last   *Node
length int
}

func (q *Queue) Enqueue(n *Node) {
if q.length == 0 {
q.first = n
q.last = n
q.length++
return
}

last := q.last
last.next = n
q.last = n
q.length++
return
}

func (q *Queue) Dequeue() *Node {
if q.length == 0 {
return nil
}

node := q.first
q.first = node.next
q.length--
return node
}

func (q *Queue) Peek() *Node {
return q.first
}

func main() {
queue := &Queue{}
firstNode := &Node{value: 1}
secondNode := &Node{value: 2}
thirdNode := &Node{value: 3}

queue.Enqueue(firstNode)
queue.Enqueue(secondNode)
queue.Enqueue(thirdNode)

fmt.Println(queue.Peek())

fmt.Println(queue.Dequeue())
fmt.Println(queue.Peek())

fmt.Println(queue.Dequeue())
fmt.Println(queue.Peek())

fmt.Println(queue.Dequeue())
fmt.Println(queue.Peek())
}
``````

### Go Playground

You can add a `lookup` method to both the Stack and the Queue. Or implement them with Slices instead of Linked Lists or Doubly Linked Lists.