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

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 🙂