Javascript: Stacks & Queues with Arrays

Image from https://gohighbrow.com/

Data Structures are some of the most fundamental aspects when it comes to computer science. These structures are tools which are used to store data in a computer in a way that is used efficiently. There are many different types of structures, but this post will be focused on Stacks & Queues. These are both linear data structures that are pretty similar, but have a few unique principles that belong to each type.

A Pancake Stack

What is a Stack?

Although I hate pancakes (WAFFLES, FTW! =]), my first thought when it comes to stacks are pancake stacks. When a chef is cooking pancakes and starts off with an empty plate, the first pancake that is cooked through will be placed on top of the empty plate. Then, every subsequent pancake will be placed right on top of the last pancake that was placed on the plate. Eventually, the pancakes will be stacked until it looks like the photo above. If we were to take just one pancake, the easiest pancake that can be take from the stack would be the one from the top, making LAST pancake that was IN the stack be the FIRST one OUT of the stack.

This thought process would be exactly the same as a stack as a linear data structure. The principle it would follow would be “last in, first out” (LIFO), or “first in, last out” (FILO), which are both essentially the same thing. Stacks have a few basic operations that can be performed on them:

1. Push — adds an item in the stack
2. Pop — removes an item from the stack
3. Peek/Top — returns the top element of the stack
4. isEmpty — returns true if the stack is empty

All of these operations should be familiar as these are the same as array operations! Typically, stacks can be implemented using arrays or linked lists. For this blog, I’ll implement this using arrays and Javascript Objects. Review the code below:

Javascript Stack Class

In actual applications, stacks can be used in various ways. One way would be to reverse the letters in a word. A stack can be used by push each letter from the start into a stack, then popping the letters back out. Since it follows the LIFO (last in, first out) principle, the letters would be popped out in reverse order. Another application would be the “undo mechanism” in text editors as the operations done are kept track as a stack, with the last action being the first undo whenever the operator is run. Stacks are typically used in solving problems utilizing recursion.

Next in queue! (from Zootopia)

What is a Queue?

When I think of a queue, I always think about waiting in line. When I think of waiting in line, I always think about the worse line you can be in, which is at the DMV line. If you’ve ever seen Zootopia, they have an awesome analogy to an experience one can have at the DMV. Typically at the DMV, you’d wait in line by getting a ticket number. If you were the first person to arrive, you’d get #1, then the next person would get #2, etc. Hopefully, the staff at the DMV will operate where they will go in order, ascending through the ticket numbers, starting with the FIRST one IN being the FIRST one OUT.

Again, this thought process would be the same way to think of queue data structures. The principle they follow would be ‘first in, first out” (FIFO). Like with stacks, they have a few basic operations that can be performed with them:

1. Enqueue — adds an item as the last item to the queue
2. Dequeue — removes the first item from the queue
3. Front — get the first item from queue
4. Rear — get the last item from queue

These type of operations should also sound familiar based on what they are doing. Queues can also be implemented using arrays or linked lists. Review the code below for queues implemented with arrays & JS classes:

Javascript Queue class

The most practical application of queues within the computer are through processors. Since queues are linear and sequential, it coincide with how processors use a linear set of instructions to execute. Queues are used in solving problems having sequential processing.

But why should I care?

In computer science, modeling is very important. With stacks and queues, they are just examples of abstraction. Meaning, they are just another later of rules to add onto a pre-existing structure so we can control the data in a different manner. In regards to their run times, we would get O(1) run time on all operations since we are only accessing the “start” or “end” of the data structures.

Resources:

1. “Stacks and Queues”, accessed October 27, 2020, https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html#:~:text=A%20queue%20is%20a%20container,%2Dout%20(FIFO)%20principle.&text=The%20difference%20between%20stacks%20and,item%20the%20least%20recently%20added.
2. “Stack Data Structure,” GeekForGeeks, accessed October 27, 2020, https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
3. “Queue | Set 1 (Introduction and Array Implementation),” GeekForGeeks, accessed October 27, 2020, https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/
4. “Difference between Stack and Queue Data Structures,” GeekForGeeks, accessed October 27, 2020, https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
5. “Computer Science: Stacks and Queues,” Highbrow, accessed October 27, 2020, https://gohighbrow.com/stacks-and-queues/