Forem: Damian

Data Structures — Part 2 — Stacks + How to Implement

Damian — Mon, 15 Mar 2021 20:31:09 +0000

Stack

A stack is a structure to store data unidirectionally. This means that the way to add or remove elements occurs in a single direction (from start to finish).

Unlike queues, stacks operate under a LIFO ( L ast I n F irst O ut) system. This means that the element closest to being removed will be the one that has entered more recently.

A very simple example of the implementation of a stack could be seen in the Undo / Redo system. Every time we access a page, it is saved in the history in a stack structure, so that when we click "Back" in the browser it takes us to the last record stored in the stack.

How Implement a Stack ?

Stack Implementation

Our stack will have several methods and properties, push, pop, peek, to look at what's next to be removed, length, and isEmpty. We'll start by creating an array held in closure to store our items.

We want to keep our collection in the correct order, so we always want to add and remove items from the same side of the array.

Push

Using push, we place new items at the end of the array.

function push(item) {
  stack.push(item);
}

The push method will add an item to the end of our array.

Reference Push Method

Pop

With pop, we remove the final item from the array. This ensures we maintain order in our stack.

function pop() {
  return stack.pop();
}

Peek

Now we'll create our peek method by returning the last item in our array.

function peek() {
  return stack[stack.length - 1];
}

If you wonder about the notation in brackets. It is the way we have to access an element by its index in javascript.

Length

We can create our length property. For this we can rely on a getter function that takes the size of the collection.

function get length() {
  return stack.length;
}

Is Empty

And finally we will add our isEmpty method to check if the collection is empty.

function isEmpty() {
  return stack.length === 0;
}

Let's put it all together

function createStack() {
  const stack = [];

  return {
    push(item) {
      stack.push(item);
    },
    pop() {
      return stack.pop();
    },
    peek() {
      return stack[stack.length - 1];
    },
    get length() {
      return stack.length;
    },
    isEmpty() {
      return stack.length === 0;
    }
  };
}

const lowerBodyStack = createStack();

lowerBodyStack.push("underwear");
lowerBodyStack.push("socks");
lowerBodyStack.push("pants");
lowerBodyStack.push("shoes"); 

console.log(lowerBodyStack.pop()); // shoes
console.log(lowerBodyStack.peek()); // pants
console.log(lowerBodyStack.length); // 3

Real Life Uses

An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack. Undo/Redo stacks in Excel or Word.
Language processing :
- space for parameters and local variables is created internally using a stack.
- compiler's syntax check for matching braces is implemented by using stack.
A stack of plates/books in a cupboard.
A garage that is only one car wide. To remove the first car in we have to take out all the other cars in after it.
Wearing/Removing Bangles.
Back/Forward stacks on browsers.
Support for recursion
- Activation records of method calls.

Data Structures - Part 1 - Queues + How to Implement

Damian — Tue, 02 Mar 2021 20:11:34 +0000

Queues

A queue is a simple data structure that allows elements to be inserted from one end, called the rear (also called tail), and deleted from the other end, called the front (also called head).

A queue is a collection of items that obeys the principle of first-in/first-out. It is a method for handling data structures where the first element is processed first and the newest element is processed last.

How Implement a Queue ?

Implementing a queue will probably lead us to have some methods linked such as get the size, adding a new element, deleting an element, or simply knowing if it is empty. Always respecting the order of implementation on which this type of data structure mentioned above (FIFO) is based.

Let's do some code

First we need a function to create our queue, right ? So let's create a new function using the native methods of JS (We are doing something simple to get the concept)

function createQueue() {
  const queue = [];
  return queue;
}

So far we have a function that returns an empty array. But we want to add some functionality to the implementation. For example, let's queue an item in our new queue

function enqueue() {
  queue.unshift(item);
}

What's going on here ? When we call our enqueue method, the unshift method, add whatever element we indicate to it, at the beginning of the queue.

Reference to Unshift Method

Now we can queue methods, but let's go further and add a method to unqueue

function dequeue() {
  return queue.pop();
}

As we said before, this type of structure is commonly called FIFO, so we need to remove the last item that we enter, that is what the native pop function of arrays in JS takes care of.

Reference to Pop Method

Our structure is almost ready, now let's add two methods to calculate the current size of our queue and check if it is empty.

function length() {
  return queue.length
}
function isEmpty() {
  return queue.length == 0
}```



We will use the native method length, to calculate the dimension of our queue. And we will do a simple mathematical check equaling 0 to know if our queue is empty or not.

Now, let's put it all together.



```javascript
function createQueue() {
  const queue = [];
  return { 
    enqueue(item) {
      queue.unshift(item);
    },
    dequeue() {
      return queue.pop();
    },
    get length() {
      return queue.length;
    },
    get values() {
      return queue;
    },
    isEmpty() {
      return queue.length == 0;
    } 
  };
}

const myQueue = createQueue(); console.log("Is Empty ?", myQueue.isEmpty()); // true
myQueue.enqueue("Adding my first element"); myQueue.enqueue("Learning how a queue works");

console.log("My Queue Elements", myQueue.values); // ["Learning how a queue works", "Adding my first element"]
console.log("Is Empty ?", myQueue.isEmpty()); // false console.log("Size of Queue", myQueue.length); // 2 

myQueue.dequeue();
console.log("Size of Queue", myQueue.length); // 1

Play Code Here

Real Life Uses

Queue is used in BFS (Breadth First Search) algorithm. It helps in traversing a tree or graph.
Queue is also used by Operating systems for job scheduling.
Queue is used in networking to handle congestion.

Really Funny Example of a Queue

What I need to create my own Snake “Nokia” game ?

Okay, so initially my snake will be of some X pixels length. Every time it consumes food, its length increments by 1. I’ll also have to keep track of the snake’s head, or the start. And the end. And also any turning points on the body. And every time the user turns the snake in a valid direction, I’ll have to add a new turning point at that position. And then the tail — the end of the snake has to follow the same turns the head made initially. So let me rephrase that. The head first turns. Eventually the rest of the body turns. The head turns again, the body turns again. If head turns East then North then West, the body turns East then North then West. I’ll need a queue.

Bonus

Priority Queue

Priority Queue is an extension of queue with following properties:

Every item has a priority associated with it.
An element with high priority is dequeued before an element with low priority.
If two elements have the same priority, they are served according to their order in the queue.
In the below priority queue, element with maximum ASCII value will have the highest priority.

Enqueue

Our method for enqueue items will now receive a second argument, which will tell us if the item has a high priority. By default this value will be false. Because we could omit the value if we do not want to indicate if it has a high priority. In this way, according to the conditional logic that we apply, the item will be added to the low priority queue.

function enqueue(item, isHighPriority = false) {
  isHighPriority
    ? highPriorityQueue.enqueue(item)
    : lowPriorityQueue.enqueue(item);
}```



*Dequeue*

Our method for dequeue will be set first in the high priority list, in case it is not empty, dequeue the first item in the high priority list. Otherwise go to the low priority list to remove an item.



```javascript
function dequeue() {
  if (!highPriorityQueue.isEmpty()) { 
    return highPriorityQueue.dequeue();\
  } 

  return lowPriorityQueue.dequeue(); }

Peek

Our peek method gets a similar change. Just like we dequeue from the high priority queue first, we're going to peek from the high priority queue first as well. In fact, I can copy-paste this code and just make a change to which method is being called.

function peek() {
  if (!highPriorityQueue.isEmpty()) {
    return highPriorityQueue.peek();
  }

  return lowPriorityQueue.peek(); }

Length

Our length method will only return the size of both queues added together.

function length() {
  return highPriorityQueue.length + lowPriorityQueue.length;
}```



*Is Empty*

Lastly, our isEmpty method is the conjunction of the two queues' isEmpty methods.



```javascript
function isEmpty() {
  return highPriorityQueue.isEmpty()
    && lowPriorityQueue.isEmpty();
}```



Let's put all together



```javascript
import { createQueue } from "./queue";

function createPriorityQueue() {
  const lowPriorityQueue = createQueue();
  const highPriorityQueue = createQueue();

  return {
    enqueue(item, isHighPriority = false) {
     isHighPriority
       ? highPriorityQueue.enqueue(item)
       : lowPriorityQueue.enqueue(item);
    },
    dequeue() {
      if (!highPriorityQueue.isEmpty()) {
        return highPriorityQueue.dequeue();
      }

      return lowPriorityQueue.dequeue();
    },
    peek() {
      if (!highPriorityQueue.isEmpty()) {
        return highPriorityQueue.peek();
      }

      return lowPriorityQueue.peek();
    },
    length() {
      return highPriorityQueue.length + lowPriorityQueue.length;\
    },
    isEmpty() {
      return highPriorityQueue.isEmpty()
        && lowPriorityQueue.isEmpty();
    }
  };
}

const myQueue = createPriorityQueue();

myQueue.enqueue("A fix here");
myQueue.enqueue("A bug there");
myQueue.enqueue("A new feature");

console.log(myQueue.peek()); // A fix here

myQueue.dequeue();

console.log(myQueue.peek()); // A bug there 

myQueue.enqueue("Emergency task!", true); 

console.log(myQueue.peek()); // Emergency task! myQueue.dequeue(); console.log(myQueue.peek()); // A bug there

Play Code

Real Life Uses

Dijkstra’s Shortest Path Algorithm - Prim’s algorithm - Huffman codes for Data compression.
Heap sort
Load balancing on servers.

If you got this far, now you surely know how to implement a queue yourself and what its advantages are. In the next post we will see how the stack data structure works.

Why testing should be part of your business?

Damian — Fri, 15 May 2020 15:21:17 +0000

Consider the title of this article not as a question but, rather, as the consequence of successful business decisions. You will find a series of arguments that will make it easy for you to justify introducing testing into your product, as well as advantages that this type of practice exposes for your business.

So let’s start with the basic: What is testing?

I like to define it as an extra layer in the architecture of your product, with the purpose of validating and verifying that the software works correctly per the requirements of your product department. Indeed, that’s a fancy way of saying that the product will be error-free, yet that still is not entirely true.

Testing will depend on how it is written, if it has been developed according to business rules, and if all of those rules have been taken into account.

We generally develop this practice in terms of product, to verify if our results match what was intended. In technical terms, this practice is extremely useful to find errors early in development, which will lead to a more efficient start-up with the lowest possible error rate.

There are two ways to execute tests: automated and manual. But given this is the 21st century, do you really want to manually run validations? This involves people who can and will make mistakes—better leave it to the machines.

There are numerous technical advantages when it comes to testing, among them:

Streamline the process
- When we develop more and more features for our application, we will eventually have to change old designs and implementations, which translates into extra costs and risks. Do we really want to introduce an error into old features? Nope! But with a unit test, you can start refactoring without issues since your unit will tell you if it meets the requirements or not.
Code quality
- Testing improves the quality of code. If we use it at an early stage of the project, we will be able to develop all our rules (including edge cases) with greater clarity and precision.
Find problems early
- Our code will go through processes that can detect errors in the early stages of the project. This translates into less development time and greater confidence in our product as it reaches production. Plus, we avoid developer overtime for debugging.
Scalable
- Simplify integrations with other units or applications.
Documentation
- This is one of my favorite items! Testing during your product’s development will allow clear documentation about what it does, how it performs, and all the test cases it should cover. There is no better visualization of your product than some good documentation.
Debug process
- Simplify the debugging process—if our unit or module fails, the only possible cause is the most recent code change.
Reduce costs
- Unit testing finds errors early and helps reduce the cost of error corrections. Imagine the cost of an error found during the later stages of development, like during system tests or acceptance tests—errors detected later are usually the result of many changes, and you don’t really know which one caused the error.

Different Testing Layers

Unit Test: Test each individual piece of code. Think of each function, class, or method.

Integration: You test the integrations of many units together. You make sure your code works when put together, including all dependencies.

E2E: This type of test does its job of performing the complete flows expected by a user, simulating both successful and unsuccessful paths.

Regression: After integrating, we must run the unit tests again. This regression assures us that the new changes have not broken anything.

Acceptance: You must prove that the program meets the expectations of the user or client.

I like to think about testing in a practical way, like how many layers I have to mock to make it work.
In the unit test, I must mock any external dependencies of my unit code. In integrations, I should only mock the API calls to emulate the responses I need. In the case of E2E, you shouldn’t mock anything to check how all flows work.

In another article I will explain in more detail each type of testing.

Let’s do a simple exercise of synthesis optimization as if we are the project manager and we really want to have a product in the least amount of time and with the lowest costs.
Do we really want to spend hundreds of hours finding and fixing bugs for not having an extra layer from the get-go?

If our product starts producing patch after patch, what does that tell customers about our application? Do we really want to have a bad image for not implementing testing at an early stage and not keeping costs low?

Conclusion

Testing is a tool that I humbly consider absolutely necessary. I can’t swear that it is essential, as there is evidence of hundreds of products that are in production without having been put through the paces I’ve recommended above. However, they generally are not the most successful products. Most big companies have adopted testing and have integrated it as a natural part of the process, which adds enormous value to the product (and, indeed, to the company in terms of technical standards).

Are you convinced? Or are you satisfied in paying extra developer hours to patch your app?