Stacks and Queues: A Javascript Explanation for Beginners

A Stack? A Queue? Data Structures? What?

In Javascript, there are countless ways to store data. We call these different data storage types, data structures. There are a variety of data structures available to us as programmers. Two data structures that are commonly used are stacks and queues. These two data structures are often discussed in conjunction since their behaviors are opposite the other. Let's dive in and take a look ateach of them and how they function!

Stacks

Stacks are very similar to arrays in Javascript except they follow a strict convention when adding or removing data within them. A stack follows the notion of First In Last Out (FILO) or Last In First Out (LIFO). A good way to visualize a stack is like a pile of dishes in the sink. In order to access the bottom dish, you will have to remove all the dishes on top of it before you can reach it.

Now that we have an understand of how stacks work, let's create our own constructor function for implementing a stack! Here we're creating the base of our stack function with a few variables that will help us implement other methods to our stack function later on.

const makeStack = function() {
  const stack = {};

  // Creates an object with numeric keys to store values
  const storage = {};
  // Creates a count to keep track of how many items we've added
  let count = 0;
  // Creates a stackHeight variable to track how 'high' the stack is
  let stackHeight = 0;
  // Creates a size variable to track how large the stack is
  let size = 0;
};

Now that we have our stack, we need a way to add items to it. Like we discovered before, stacks are very similar to arrays and they also have a push method attached to them. Let's look at how this method operates.

  stack.push = (value) => {
    // Creates a property in the storage object with 
    // the value of count and assigns it to the value
    // passed into the push method
    storage[count] = value;
    // Increments the count
    count++;
    // Increments the size
    size++;
    // Sets the stackHeight equal to the count minus one
    stackHeight = count - 1;
  };

Since we can add things to our stack, it might be useful if we can get those things back out of our stack when we want them. Just like how stacks have a push method, they also have a pop method similar to arrays. Let's take a look at how that's implemented.

  stack.pop = () => {
    // Checks to see if the size is greater than 0, if so
    // decrement, this check is to ensure that our size is
    // never a negative value. 
    if (size > 0) {
      size--;
    }
    // Creates a variable called last that is equal to 
    // the very last value that was added to the stack. 
    let last = storage[stackheight];
    // Deletes that key within the storage object, so
    // it is removed from our stack
    delete storage[stackheight];
    // Decrements the stack height since an item was removed
    stackheight--;
    // Returns last variable
    return last;
  };

Another useful method we might want for our stack is a size method, so we can see how many items are inside of our stack. Let's take a look at how easy it is to implement this method.

 stack.size = () => {
    // Since we created a variable earlier called size 
    // that tracks the size of the stack as we add and 
    // remove items, we can simply return the size
    return size;
  };

This implementation gives a functional stack that allows for the addition and removal of items following the notions of FILO and LILO and reporting the size of our stack. Now let's take a look at queues and how they operate in reverse to a stack.

Queues

Now that we have an understand of how stacks work, we can use that knowledge to understand how a queue operates. A queue is very similar to a stack except the conventions for adding or removing data are flipped. A queue follows the notion of First In First Out (FIFO) or Last In Last Out (LILO). The simplest example of a queue is a line at say a fast-food joint. The first person in the line gets served first and the last person will be served last. As more people join the line or "queue" those people will be served in the ordered they joined.

Now that we have an understand of how queues work, let's create our own constructor function for implementing a queue! Here we're creating the base of our queue function with a few variables that will help us implement other methods to our queue function later on.

const makeQueue = function() {
  const queue = {};

  // Creates an object with numeric keys to store values
  const storage = {};
  // Creates a count variable to keep track of how many times 
  // we've added to the queue
  let count = 0;
  // Creates a line variable to keep track of what item we're at 
  // in our 'line'
  let line = 0;
  // Creates a size variable to keep track of the size of our queue
  let size = 0;
};

Now that we have setup the basis for our queue, let's create a method that allows us to add items to the queue. We'll call this method enqueue. We'll simply be adding to the end of queue so nothing fancy here.

  queue.enqueue = (value) => {
    // Creates a property with the value of count and 
    // assigns it the value of whatever was passed into 
    // the enqueue function
    storage[count] = value;
    // Increment our count variable
    count++;
    // Increment our size variable
    size++;
  };

Since we're adding items to our queue, it might be useful to pull those items out of our queue when we want them. In order to do this we'll implement a method called dequeue, which will return the first item that was added to the queue.

  queue.dequeue = () => {
    // Checks to see if the size is greater than zero
    // since if we remove all items, we don't want our
    // queue to have a negative size
    if (size > 0) {
      size--;
    }
    // Set a variable called first equal to the value 
    // stored at the property of whatever the value of 
    // line is
    let first = storage[line];
    // Removes that property from the storage object
    delete storage[line];
    // Increments line for the next call of dequeue
    line++;
    // Returns the value of the first variable
    return first;
  };

Now we have a working queue that adds and removes items that were added into it. Similar to our stack function, let's add a method that allows us to see how many items are currently in the queue.

  queue.size = () => {
    // Returns the value of the size variable
    return size;
  };

Finally, we have a working queue that adds and removes items following the notion of FIFO & LILO. Now that we've gone through and implemented both a stack and a queue let's review one last time how they both function.

Conclusion

When discussing stacks and queues, it is important to remember how each one functions. It's easy to forget how items are added and removed from one or the other, but just keep in mind the rules.

• Stacks: First In Last Out (FILO) & Last In First Out (LIFO)
• Queues: First In First Out (FIFO) & Last In Last Out (LILO)

Now that we've seen how both stacks and queues work, what are some real examples of implementing these data structures into code.

• Stacks:

  • Forward and Backward within a browser
  • Undo/Redo with Word documents

• Queues:

  • Amazon.com checkout
  • A printer receiving files to print

That concludes my discussion of the differences between queues and stacks, they're super useful in programming as we saw from the examples above, so don't forget about them!