DEV Community: David Hurtado

Data Structures in JavaScript (Part 2): Stacks and Queues

David Hurtado — Thu, 08 Jun 2023 08:58:04 +0000

The stacks and queues are arrays with restrictions. These restrictions make elegant structures for storing temporary data. So you can think of them as temporary containers. The most important thing in these structures is that they focus on the order in which the data is handled.

In JavaScript, we don't have the stack and queues as built-in data types, like the array or object. So, we have to implement it ourselves. Also, it's important to know that the stack and queue are abstract data types. This means that these structures are a set of theoretical rules that revolves around some other built-in data structure. (In this case, the stack and queues revolve around the array data structure). Later we review the rules of each structure.

As a use case example, imagine you are coding a delivery app, like Doordash or UberEats. If you are a restaurant subscribed to this app, it's very important to take into account the exact order and time in which the delivery orders are created in your system. Because the first to enter, it's the first to be prepared. The second to enter, it's the second to be prepared, and so on. Later, when the delivery order it's dispatched, the order of creation it's not that important, and the data it's processed in other way.

Stacks

A stack, as we have mentioned it's like an array, a simple list of data elements. But it has 3 constrainsts:

Data can be inserted only at the end of a stack.
Data can be deleted only from the end of a stack.
Only the last element of a stack can be read.

The easiest analogy it's viewing a stacking toy. Imagine each piece of the toy as a piece of data. You can stack pieces above each one and you only can add another piece by the top. If you want to withdraw a piece, you only can withdraw the top piece.

We can use the acronym LIFO for remembering the stack operations: "Last In, First Out".

A great example of a stack it's viewing the "undo" function in a word processor. The system keeps track of the last key you have pressed. Also, the system keeps stacking each key pressed. If you want to undo, the system look for the last key pressed, reverse the operation and pop this operation out the stack.

For the JavaScript implementation, we could use 2 ways: closures or classes. They are different implementations, but they share the more important aspects: the stack variable should be private and we only can insert elements at the end of the array, delete elements at the end of the array, and read the last element in the array. If you aren't clear about the concepts of closures and classes, I highly suggest that review them. Let's review both:

Closure implementation

const createStack = () => {
  // This will be a private variable, 
  // inaccessible from the outer scope
  const stack = [];

  const push = (element) => {
    stack.push(element);
  };

  const pop = () => {
    stack.pop();
  };

  const read = () => {
    return stack[stack.length - 1];
  };

  // We return functions for mutating the stack
  // and reading the last entry

  return {
    push,
    pop,
    read,
  };
};

const myStack = createStack();

myStack.push('Enter in 1st place');
myStack.push('Enter in 2nd place');
myStack.push('Enter in 3rd place');

// The stack variable is inaccessible
console.log(myStack.stack); // undefined

// We only can access the last entry 
// with the read() function
console.log(myStack.read()); // "Enter in 3rd place"

myStack.pop();
console.log(myStack.read()); // "Enter in 2nd place"

myStack.pop();
console.log(myStack.read()); // "Enter in 1st place"

myStack.pop();
console.log(myStack.read()); // undefined

Classes implementation

class Stack {
  // We declare the stack as a private field
  // We use the # notation
  #stack;

  constructor() {
    // We initialize the stack as an empty array
    this.#stack = [];
  }

  push(element) {
    this.#stack.push(element);
  }

  pop() {
    this.#stack.pop();
  }

  read() {
    return this.#stack[this.#stack.length - 1];
  }
}

const classStack = new Stack();

classStack.push('Enter in 1st place');
classStack.push('Enter in 2nd place');
classStack.push('Enter in 3rd place');

console.log(classStack.read()); // "Enter in 3rd place"

classStack.pop();
console.log(classStack.read()); // "Enter in 2nd place"

classStack.pop();
console.log(classStack.read()); // "Enter in 1st place "

classStack.pop();
console.log(classStack.read()); // undefined

Queues

A queue is another data structure for processing temporary data. Is very similar to the stack, but it processes the data differently:

Data can be inserted only at the end of a queue. (Identical to the stack).
Data can be deleted only from the front of the queue. (Opposite of the stack)
Only the first element of a queue can be read. (Opposite of the stack).

A good example of a queue is a line of people at a movie theater. The first person in the line is the first person to leave the line. If another person came to the line, he will enter by the back of the line.

We can use the acronym FIFO for remembering the queue operations: "First In, First Out".

For the JavaScript implementation of queue, we could use 2 ways as the stacks: closures or classes. Let's review both:

Closure implementation

const createQueue = () => {
  // This will be a private variable
  // inaccessible from the outer scope
  const data = [];

  const enqueue = (element) => {
    data.push(element);
  };

  const dequeue = () => {
    return data.shift();
  };

  const read = () => {
    return data[0];
  };

  // We return functions for mutating the queue
  // and reading the last entry

  return {
    enqueue,
    dequeue,
    read,
  };
};

const myQueue = createQueue();

myQueue.enqueue('Enter in 1st place');
myQueue.enqueue('Enter in 2nd place');
myQueue.enqueue('Enter in 3rd place');

// The stack variable is inaccessible
console.log(myQueue.data); // undefined

// We only can access the last entry
// with the read() function

console.log(myQueue.read()); // "Enter in 1st place"

myQueue.dequeue();
console.log(myQueue.read()); // "Enter in 2nd place"

myQueue.dequeue();
console.log(myQueue.read()); // "Enter in 3rd place"

myQueue.dequeue();
console.log(myQueue.read()); // undefined

Class implementation

class Queue {

  // We declare the data as a private field
  // We use the # notation
  #data;

  constructor() {
    // We initialize the data as an empty array
    this.#data = [];
  }

  enqueue(element) {
    this.#data.push(element);
  }

  dequeue() {
    return this.#data.shift();
  }

  read() {
    return this.#data[0];
  }
}

const classQueue = new Queue();

classQueue.enqueue('Enter in 1st place');
classQueue.enqueue('Enter in 2nd place');
classQueue.enqueue('Enter in 3rd place');

console.log(classQueue.read()); // "Enter in 1st place"

classQueue.dequeue();
console.log(classQueue.read()); // "Enter in 2nd place"

classQueue.dequeue();
console.log(classQueue.read()); // "Enter in 3rd place "

classQueue.dequeue();
console.log(classQueue.read()); // undefined

Conclusion

We reviewed the stack and queue data structures and defined them as arrays but with some restrictions. Both structures are similar and the main difference is the order in which the data is processed. In JavaScript, they aren't built-in structures, so we have implemented ourselves with classes or closures.

Thanks for reading this post, I hope you found it interesting! You also can read the first article of the series and let me know what is the most interesting part (or not!) of these articles.

Feel free to follow me to get notified when new articles are out 🙂

Data structures in JavaScript: Arrays, Objects and beyond (Part 1)

David Hurtado — Wed, 24 May 2023 09:23:12 +0000

In the last few weeks, I've been reading A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow. This book is great if you already have some experience programming and you want to level up your knowledge of these topics. So far, the algorithms parts have been great, but if you ask me, the most insightful and revealing part for me has been the data's structure.

If you're coming from a CS degree or similar background, these topics could be a piece of cake and surely you'll be familiar with it. But for those that come from a very different background and made a bootcamp or are self-taught, these topics sometimes are ignored. Because when we start, we're taught that our code initially should work. And it's ok if we are starting, but later when we begin to gain more experience, besides finding a code that works, we should find efficient and readable code.

And that's where data structures come. Yes, they give us structure and order. But the most important thing it's they help us with the effiency, because each structure performs differently in each context and operations.

Data Structure Operations

To understand the performance of any data structure we'll usually refer to four basic operations: reading, searching, inserting and deleting.

Arrays

The array is the most basic data structure in computer science. In essence, an array it's a chunk of memory where you can store a simple list of data elements. The arrays have a very useful property that it's their length. This property returns us the number of elements within the array. Also, each element in an array has an index: a number that identifies where a piece of data it's stored inside the array. In terms of efficiency, reading an element inside an array is very efficient and it'll cost us one step. For searching, it'll depend on the search algorithm we use, but if for example, we use a linear search, for an array of N elements, it could cost us a maximum of N steps. Insertion could take us a maximum of N + 1 step (this is the case if we want to insert an element in the first index of the array). On the other hand, deletion could take us a maximum of N steps. As we could see, inserting and deleting elements at the end of the array it's very efficient, but if we want to make this at the beggining of the array, it won't have the same effiency.

let animals = ['dog', 'cat', 'lion', 'bird'];

// Length property
console.log(animals.length); // 4

// Reading. Want to know the value stored in certain index
console.log(animals[2]); // 'lion'

// Searching.
// Want to know if a string of value 'bird',
// and if it exist, we want to know the index

const valueToFind = 'bird';

const indexOfValue = animals.findIndex((animal, index) => {
  console.log(`${index + 1} step`);
  return animal === valueToFind;
});

console.log(indexOfValue);

// Counting steps
// '1 steps'
// '2 steps'
// '3 steps'
// '4 steps'

// Index of the searched value
// '3'

// Inserting
// First, in the end of the array

animals.push('wolf');
console.log(animals); // ['dog', 'cat', 'lion', 'bird', 'wolf']

// Now in the middle

animals.splice(1, 0, 'tiger');
console.log(animals); // ['dog', 'tiger, 'cat', 'lion', 'bird', 'wolf']

// Deleting
//First, in the end of the array

animals.pop();
console.log(animals); // ['dog', 'tiger, 'cat', 'lion', 'bird']

// Now in the middle

animals.splice(2, 1);
console.log(animals); // ['dog', 'tiger, 'lion', 'bird']

Hash Tables (Objects)

A hash table is a list of paired values. The first item in the pair is called key, and the second item is called the value. The biggest perk in this structure is that reading and inserting are incredibly fast. Also, if we have data that it's related in pairs, hash tables are a natural data structure for organizing this data. For example, if you have a list of items with their prices:

{'Blue jean': 105, 'Yellow shirt': 45, 'Green Jacket': 78}

The magic of the hash table resides in the pairing of the key-value. Because of that, the cost of reading and insertion is O(1) (one step). If we don't know the keys, we cannot take advantage of these benefits.

In JavaScript, the most common implementation of hash table is the Object. In the Objects, we can pair the keys with values or functions. The values are called properties and the functions are called methods. For accessing or reading the values of the keys, we can use either the dot notation (object.key) or the bracket notation (object['key']) notations.

const myHashTable = {
  prop1: 'I am the value of this property or key.',
  method1: function () {
    console.log('I am logging inside a method');
  },
};

console.log(myHashTable.prop1); // 'I'm the value of this property or key'

// Calling the method with bracket ([]) notation
myHashTable['method1'](); // 'I am logging inside a method'

For insertion and delete we could see the next example:

const myObject = {
  prop1: 'Hello',
};

myObject.insertedProp = 'I am inserted';
delete myObject.prop1;

console.log(myObject); // { insertedProp: "I am inserted" }

Also, another implementation of hash tables in JavaScript are Maps. They are similar to Objects but with important differences. For example, the keys in the Maps could be any value (functions, objects, or any primitive). In Objects, the keys must be either a String or a Symbol. Also, the Map is an iterable, the object doesn't implement naturally the iteration protocols. If you are interested in viewing all the differences you can check in the MDN documentation.

Sets

Set is a data structure that doesn't allow duplicate values to be contained within it. It's a simple list of values but with the constraint of only allowing unique values. JavaScript uses hash tables for implementing Sets.

// Create Set

const mySet = new Set();

// Insetions
// For insertion we use the method .add()

mySet.add(1); // Set(1) { 1 }
mySet.add(5); // Set(2) { 1, 5 }

// Doesn't allow inserting a repeted value

mySet.add(5); // Set(2) { 1, 5 }

// Searching
// For searching and checking if a value exist,
// we use the method .has()

mySet.has(1); // true
mySet.has('dog'); // false

// Delete

mySet.delete(5); // Removes 5 from set
mySet.has(5); // false

One of the most useful uses that we can give to sets is to eliminate repeated data within an array:

// Use to remove duplicate elements from an array

const numbers = [2, 3, 2, 4, 4, 5, 21];

// Here we make a Set starting from an array
// The conversion eliminate duplicate data
// Later we transform the Set to an array using the spread operator (...)
console.log([...new Set(numbers)]);

// [2, 3, 4, 5, 21]

In the next post we'll continue reviewing other data structures, like Stacks, Queue and other ones.

Thank you for reading. See you in the next post.