Data Structures: Stacks
A Quick Dive Into Stacks
Data Structures: Why Should We Care?
The first step in understanding and excelling at algorithms is having deep knowledge of data structures. Data structures are the foundation of Computer Science and Software Engineering, and as such, we have to have a good grasp of the basics of the most common data structures in order to be good at what we do.
While it might be intuitive, it is helpful for us to pause here and review what a data structure actually is. At the very basic level, a data structure is a way of storing, organizing, and manipulating a collection of data. According to Wikipedia,
In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
Data Structures and Software Engineering
As Software Engineers, we have to have a thorough understanding of data structures since, at the very core, what we work with is data. Having a thorough understanding of data structures is important so that we can choose the most optimal one to suit our specific needs, keeping space and time complexity in mind.
There are many different data structures, each with its own advantages and disadvantages in different scenarios. While many of us are, by now, quite familiar with many of these data structures, I figured it might be a useful refresher for many of us (myself included) to review some of these.
A stack is a “linear data structure which follows a particular order in which the operations are performed” (GeeksforGeeks). Stacks work following the Last In First Out (LIFO) principle, meaning that the element that is added last (the one at the top of the stack) is the first element that gets removed. Insertion and removal of elements can only happen at the top of the stack.
It is helpful to think of a stack of books when thinking of the stack data structure. Imagine we have a table with a stack of books. If we want to add a book to the stack, we would add it to the top of the stack. Conversely, if we decided to remove a book from the stack, we would have to start with removing the book at the top of the stack, that is, the one we had just added to the stack.
If we want to add an element to a stack, we can use the
push() function to do so at the top of the stack. Conversely, if we want to remove the top element from the stack, we use the
pop() function, which returns the top element.
Besides for the above functions, we can also use the
peek() function, which returns the top-most element, allowing us to look at it without removing it. We also have the
isEmpty() method, which checks if the stack is empty, and the isFull() method, which checks if the stack is full.
How Are Stacks Implemented?
Stacks are implemented using arrays or linked lists. Each of these implementations have their own strengths and drawbacks.
Arrays allow for quick and easy access and retrieval of information, but are fixed in size. Arrays allow us to use indexes in order to target a specific element. On the other hand, linked lists are dynamic, allowing for elements to be added and removed easily. However, it is quite cumbersome and timely (O(N) time) to traverse through a linked list and access the element you want.
For a more detailed look in to the advantages and disadvantages of arrays versus linked lists, I’d recommend checking out this great GeeksforGeeks article.
What Are Some Applications of Stacks?
Stacks are most useful when the order of actions performed is important. Some real-world examples of when stacks might be useful are reversing some sort of input (such as a string) and implementing undo/redo functionality.