Once you have familiarized yourself with arrays in JavaScript, it's time to learn about some more types of data structures! Stacks and queues are quite similar in functionality to arrays, but have specific instances in which they can achieve better performance. Stacks and queues are relatively intuitive, and have plenty of real-world cases in which developers will find themselves implementing these useful data structures.
Stacks
Instead of visualizing a stack as a "horizontal" structure like an array, try and imagine a stack as a "vertical" structure, like a stack of plates piling on top of one another. You can think of a stack as a data structure in which you only insert and delete elements from one side of the structure. This is a common principle in programming called last in first out (LIFO). In other words, the elements inserted the latest at the top of the stack are also the first to be accessed and deleted. Using our plate analogy, the plates placed on top of the stack will be the easiest to grab and remove.
When working with stacks, the two most important operations used are push and pop--methods that we should recognize from working with arrays. Push is a destructive method that will insert a new element to the end (top) of our stack. Pop is also a destructive method, and will remove the most recent element from the stack.
While hard to notice at first, real-world examples of stacks are extremely common in web development. When searching the web and using a browser, your browsing history is constantly being logged using a stack. If you wish to return to your most recently visited page, a simple click of the "back" button will take you there. Additionally, we have all made use of the "undo" functionality when typing a document or using a text editor. Similar to browsing history, actions are tracked so that they can easily be accessed and "undone" using stacks.
Implementation
The simplest way to implement a stack in JavaScript is to utilize the push and pop array methods that the language already provides us with. Therefore, we can create an array and use the push and pop methods to create our operations and give us a working stack:
const stack = [];
const firstElement = 1;
const secondElement = 2;
const push = (element) => stack.push(element);
const pop = () => stack.pop();
push(firstElement);
push(secondElement);
console.log(stack) // [1, 2]
pop();
console.log(stack) // [1]
Now, you may be thinking that this just looks like an ordinary array that solely uses the push and pop methods--and you would be correct. In such a case that we can utilize an array as a stack, we should! This is because the time complexity of the push and pop methods will always be O(1). In simple terms, no matter what the size of the stack is, the time spent executing these operations will remain the same. (More on time complexity can be read here)
Queues
Now that we understand stacks, queues should also be relatively intuitive to understand. Instead of a stack of plates, a queue can simply be thought of as a line of people waiting for something. They could be waiting in line for movie tickets, a restaurant reservation, or even the restroom, but will follow the same rule of thumb--first come, first served. If stacks were associated with last in first out (LIFO), queues are associated with first in first out (FIFO).
When working with queues, the two most important operations used are enqueue and dequeue. Enqueue will be responsible for adding a new element to the end of our queue (back of the line), and dequeue will be responsible for removing the oldest element from the front of our queue (first person in line).
Implementation
Like implementing a stack, the simplest way to implement a queue in JavaScript is to utilize existing methods provided to us. Since the enqueue operation works the same as the push operation, we will use the push array method to implement enqueue. For dequeue, JavaScript yet again provides us with an existing array method to remove the first element of an array: shift.
const queue = [];
const firstElement = 1;
const secondElement = 2;
const enqueue = (element) => queue.push(element);
const dequeue = () => queue.shift();
enqueue(firstElement);
enqueue(secondElement);
console.log(queue) // [1, 2]
dequeue();
console.log(queue) // [2]
It should be noted that this is a simple method of creating a queue, but may not necessarily be the most efficient. One interesting thing to note about the time complexity of our stack and queue is that both our push and pop operations from our stack have a time complexity of O(1), while our dequeue operation will have a time complexity of O(n). This is because the shift array method is used in the implementation of dequeue and shares the same time complexity. Nevertheless, both stacks and queues can be extremely useful in their respective use-case scenarios. They can each help us organize data in sequential order while retaining efficiency in our code.
Top comments (0)