Make It Real Elite — Week 1: Stack & Queue

“A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.”

Since there are plenty of them, here is what you need to consider as a software engineer: a) What are these data structures?, b) How to use them?, and c) When to use them? Knowing the answers to these 3 key questions it can bring you loads of benefits both cost wise, effort wise and career wise. Remember also to always go back to the roots of the problem you are solving. Depending on it, you should choose the data structure that fits best for your purpose considering if you are writing, reading, sorting or searching in your code.

Here’s the plan for today: I’ll cover two of the basic data structures, namely Stack and Queue.

Stack

What’s a stack?

It’s a LIFO (Last in, first out) structure, similar to arrays but with a few differences enclosed below:

• You don’t have random access to the elements in the stack
• You can only retrieve data from the top
• You can use methods like: push, pop and peek

Stack of plates

Let’s say you work in a restaurant and your responsibility is to wash the dishes. We’ll have the two potential scenarios:

• The push action: your coworker puts a new plate on the top of the stack, and thus its height will be increasing — here it is our push action.
• The pop action: Every time you want to go next with a plate, you can only take it from the top of the stack — and here it is our pop action.

So, with nu further due, that’s why it’s called the LIFO structure: the last plate on the top of your stack (which is added by your coworker) is the first plate to go out of your stack, as long as you are washing continuously.

Usages

Stacks are useful for many things in real life:

• Expression evaluation and syntax parsing: lots of compilers use stacks to parse the expressions syntax.
• Backtracking: Think of Ruby development — every time we call in a method, this is added to the stack. The stack represents a portion of memory where the computer saves the method called, along with its context (e.g. variables). Side note: if we follow each method called and stored in the stack, we can easily trace back or stack trace of our code.
• Algorithms: Many algorithms use a stack as a way to separate, traverse or organize information, for example graph traversal methods that we will see later are based on stacks.
• Interviews: Of course, stacks can be one of those questions during an interview. Good we get to learn more about them.

Go implementation

First of all, there is one thing I’d like to mention. This is my beginning with Go, so feel free to make any comment or feedback. Going back to out Stack, for its implementation in Go we will use nodes, and every node has a value and a pointer/ link to its previous node.

// Node struct
type Node struct {
 value    interface{}
 previous *Node
}
// Getters
// Previous method to return the previous node if exists
func (n *Node) Previous() *Node {
 return n.previous
}
// Value method to return the current node value
func (n *Node) Value() interface{} {
 return n.value
}
// Setters
// SetPrevious method to set the previous node
func (n *Node) SetPrevious(previous *Node) {
 n.previous = previous
}

Now we define our Stack struct with top and length properties, the first one points to the top node and the last one keep the number of nodes(elements) in our stack:

// Stack struct
type Stack struct {
 top    *Node
 length int
}
// Getters
// Length method to return the stack length
func (s *Stack) Length() int {
 return s.length
}

Then all the magic resides in two methods as we seen before, Push and Pop, the Push method receive and interface(interfaces are something that broke my mind but at the end is easy to understand: an interface variable expects to receive anything) value, It creates a new node in the stack containing this value and check some conditions:

Then, the magic happens with the help of both Push & Pop methods. The Push method receives and interfaces (small confession: interfaces almost got me, but in the end, it turned out that, simply put, an interface variable expects to receive any value), and it creates a new node in the stack containing this value. This method checks upon several conditions:

• If the stack is empty which means the top node is nil, we place the node at the top of the stack, easy, right?
• If the stack is not empty we will set the previous attribute from our new node equals to the the current stack top node and then we will made our new node the top node in the stack

For both conditions we increases the stack’s length by one. Let’s check the code to have a clearer vision:

// Push method to add val at the top of the stack
func (s *Stack) Push(val interface{}) {
 n := &Node{value: val}
if s.top == nil {
  s.top = n
 } else {
  n.SetPrevious(s.top)
  s.top = n
 }
s.length = s.length + 1
}

As you can imagine the Pop method will be something similar. However, it won’t receive any parameter, instead it will return an interface value since we’ll retrieve the value store on the top node of the stack. The Pop method checks two conditions:

• If the stack is empty which also means the top node is nil, it returns nil
• If the stack is not empty, we follow the next steps:
  1. We find the current top node
  2. We make the top of the stack equal to the the previous node of the current top
  3. We make the previous property from our last value put out from the task to equal to nil?
  4. And finally we decrease our stack length by one

Looking into the code will make things clear:

// Pop method to remove val at the top of the stack
func (s *Stack) Pop() interface{} {
 if s.top == nil {
  return nil
 }
 currentTop := s.top
 s.top = currentTop.Previous()
 currentTop.SetPrevious(nil)
 s.length = s.length - 1
return currentTop.Value()
}

Queue

What’s Queue?

It’s a FIFO (First in, first out) structure, similar to arrays but with a few differences:

• You don’t have random access to the elements in the queue
• You can only add values in one end and retrieve them from the other

You enqueue and object into the end of the queue and dequeue it from the front. It is a list where the oldest element is accessible.

I know, we don’t really like going to the bank and waste our time waiting in the line. But for the purpose of today’s article, let’s give it a shot as this is an excellent example to explain what a queue means. The bank cashier will be calling one by one, and each time, the next to follow will be the first who has arrived prior to the others.

• The Enqueue action — Imagine a new client arrives to the bank, and him/her places him/herself at the end of the line — here it’s the Enqueue action.
• The Dequeue action — The client who is next to be attended leaves the line to make his/her transaction with the cashier, here it is the Dequeue action.

Usages

• Requests traffic: If you have a website which serves files to thousands of users, you cannot service all requests, you can only handle, let’s say 100 at once. A fair policy would be first-come-first served: take care of all 100, one at a time in the order of arrival. A Queue method would definitely be the most appropriate data structure for this purpose.
• Multitasking OS: The CPU cannot run all jobs at once, so jobs must be batched up and then scheduled according to some policy. A queue might be a suitable option in this case as well.
• Uploading and printing actions: Queues are used in case of printers or for uploading images. The logic behind is that the first one to be entered, is also the first to be processed.

Go Implementation

Similar than for the Stack implementation, we will use a node struct again. However, in this case, each node will save a link to its previous and next node in the queue. Let’s see the code:

// Node struct
type Node struct {
 value    interface{}
 previous *Node
 next     *Node
}
// Getters
// Previous method to return the previous node if exists
func (n *Node) Previous() *Node {
 return n.previous
}
// Value method to return the current node value
func (n *Node) Value() interface{} {
 return n.value
}
// Setters
// SetNext method to set the next node
func (n *Node) SetNext(next *Node) {
 n.next = next
}
// SetPrevious method to set the previous node
func (n *Node) SetPrevious(previous *Node) {
 n.previous = previous
}

Now, we will define our Queue struct with front, back and length properties. The first one points to the first node in the queue, the second one points to the last node in the queue, and the last one keeps the number of nodes (elements) in our queue:

// Queue struct
type Queue struct {
 front  *Node
 end    *Node
 length int
}
// Getters
// Length method to return the current length
func (q *Queue) Length() int {
 return q.length
}

Now the magic comes in! To add a new element we’ll use the Enqueue method in our queue, considering:

• If the queue is empty it will be our front and back node, very smart I guess because is the one and only.
• If the queue is not empty we update our new node next property to point to our current end node of the queue, then we’ll update the previous property in the last end of the queue pointing to out new node; Further, we point the queue end property to our new node, and finally we increase the queue length by one.

// Enqueue method to place a value into the end of the queue
func (q *Queue) Enqueue(val interface{}) {
 newNode := &Node{value: val}
if q.length == 0 {
  q.front = newNode
  q.end = newNode
 } else {
  currentEnd := q.end
  currentEnd.SetPrevious(newNode)
newNode.SetNext(currentEnd)
  q.end = newNode
 }
 q.length = q.length + 1
}

The Dequeue method is a little bit tricky, but only a bit. Let’s take a closer look at it:

• If the queue is empty, it returns nil since there is nothing to retrieve from the queue.
• If the queue length equals to one we retrieve the current front node and set the front and end values to nil
• If the queue length is greater than the one we look for the current front node in the queue (that from now will be the old front) and make its previous as the new queue front node, we clean the linking of these two nodes setting the front next and the old front previous property equal to nil. Further, we decrease by one the length of the queue, and finally we return the value stored in the old front of the queue.

Let’s leave the code to speak for itself:

// Dequeue method to remove a value into the front of the queue
func (q *Queue) Dequeue() interface{} {
 switch {
 case q.length == 0:
  return nil
 case q.length == 1:
  currentFront := q.front
  q.front = nil
  q.end = nil
  q.length = q.length - 1
  return currentFront.Value()
 default:
  currentFront := q.front
  q.front = currentFront.Previous()
  q.front.SetNext(nil)
  currentFront.SetPrevious(nil)
  q.length = q.length - 1
return currentFront.Value()
 }
}

If you want to check more about data structures, you can visit this repository. Don’t forget to check the readme file, and don’t be afraid to make any comment, feedback or contribution.

Mardiniii/go-data-structures

Keep in touch for what’s coming next.