Data Structures – Stacks

Stacks are one of the fundamental data structures that you learn in a data structures class. The stack has one key feature that makes it unique and different from queues. For a stack, it follows a last in first out principle. This means that if you were to have a stack of plates, the plate on top is the first one you would remove. That is the concept of a stack, but what are the critical components of a stack?

 

Critical Components Of Stack

In any programming language, you have to be able to construct any data structure from the basic concepts from the above. However, because stacks are so commonly used in Computer Science and programming in general, the implementation details are seen everywhere. Here is a list of some of the core methods for creating a stack class.

  • Push: inserts an element onto the top of the stack
  • Pop: removes an element from the top of the stack
  • Top: references the element at the top of the stack
  • Size: informs you of the current number of elements on the stack
  • Clear: removes all elements from the stack

These are the core elements of the stack class required to implement the stack. You can create a stack using both an array, or a linked list. In this case, we are going to do the array implementation of a stack. Here’s the implementation in JavaScript with comments to help you follow along.

As you can see in this example, we implemented many of the stack elements using an array to do so. In this case, JavaScript already has the stack methods included in the array class by default. Let’s break down how these methods work in the array-based implementation.

When pushing, the new element is added at the next available index in the array. In this case, 1 goes in the first index, 2 goes in the second index. The next method is pop; pop will take the element on top, in this case, index 2 and remove it, going back to index 1. Lastly, the size is just the number of elements in the array currently. This is the basic functioning of any stack and should not be taken for granted; you can see the last in first out (LIFO) in the test above. Now, you might not think this is useful, but the stack can be useful in many ways when you apply data structures to a problem.

For example, you may have a problem such as wanting to know who needs to get out of a driveway first or keeping track of the recent notifications. The most recent notifications would be on top, allowing you to structure your code base to track the stack elements for this. So, for example, an application that will send notifications starting from the most recent to the oldest notification instead. There are other uses as well, but you first have to see how the stack could be useful to you when the problem is represented. You could potentially add numbers together using a stack as well, adding conditions to influence when the stack is pushed or popped.

Either way, I hope this introduction on how the stack works helps you understand the data structure a bit more. The most important thing you can do for yourself is to test the code and see how you can make it work for you in different cases.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s