Data Structures — Stack, Last In First Out
A stack is the most simple data structure there is, and it is so useful it is used in many common computer problems. A compiler uses a stack to check if your code has a balanced bracket, i.e{[]}.
A Twitter user checks a tweet, clicks on one of the replies, sees another interesting reply now clicks on those, and they keep going down the rabbit hole. When they click back, now they are back to the previous reply, back again now they are one step back to where they started. That's a stack keeping track of your views and allows you to get back to the previous state.
A stack is like containers or books stacked on top of each other. Add more books to the stack on top. If you want to take one out, you can only start from the top. That's what it means last in first out. The one at the top is always the last one in.
In the Linked List article, we implemented the basic linked list that has insertion and removal at the front or head of the list. This basic Linked List is already behaving like a stack. This is one way of implementing a stack, where the size of the stack is dynamic.
Another way is to implement a stack is by using a fixed-size array.
As seen above, our stack has a fixed size array with a max size of 10. An int variable named top keeps track of the index top of the stack. So we can implement the function to check if the stack is empty by just checking the value of the variable top.
Now let's look at how we push an item to the stack. The first thing to note, in a fixed array, we should not ever try to access the index that is bigger than the size of the array or we would get a runtime error. In our case here, the max value of the top is 9, since an array is 0 based index, then 10 items in our stack are stored in index 0 to 9.
So before inserting, we need to make sure we are not out of bound. Only then can we insert the value into the stack.
Removing an item from the stack uses the function pop. Typically the pop function would also return the top element that is removed. Some implementations prefer to return noting, in that case, you have to get the top element first, then call the pop function.
We would implement pop that would also return the value that is removed. Similar to the push function, we would also need to make sure the pop works only when the top value is at least 0. That means we should not pop when the stack is empty, or we would face out-of-bound errors in the array.
That is all the typical functions necessary to implement a stack.
Let's look at how can we use a stack to check if a curly bracket in a string is balanced.
Given a string with left and right curly brackets, determine if the brackets are balanced.
All the following brackets are balanced, as each opening bracket has a matching closing bracket.
- {}
- {}{}
- {{}}
- {{}{{}{}}}
Here is a list of brackets that is not balanced.
- {
- }{
- {{}{
Based on what we understand of how balanced brackets look, we can then implement a simple function that uses the stack to check if the brackets are balanced.
The logic is simple. We iterate through each character in the string and check if an opening bracket is found, we push to the stack. If the next bracket in the string is a closing bracket, we pop from the stack and check if it's an opening bracket. If yes, then continue to the rest of the string.
Otherwise, we have to finally check if the stack is empty. An empty stack means we have popped all matching opening brackets in the stack which indicates that the brackets are balanced.
You can test this program at https://github.com/shahnk19/data-structures. Follow the guide to run the build step, and followed by running the program as shown below:
The full implementation of the stack can be found in this Github repo:
