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())
}

Go Playground

You check the code in the Go Playground click here.

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 check the code in the Go Playground click here.

Optional steps

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.