ivangeorgiev.dev

Introduction to data structures: Stack

Learn about the stack data structure in an intuitive way

The stack data structure is one of my favorite data structures.
It follows an interesting principle called "last in first out" or LIFO for short.
Let's learn what the stack data structure is and how it works.

We use stacks in our daily lives every time we place items one on top of another. Let's give a few examples:

• When we place plates one on top of another.
• When we fold clothes and place them one on top of another.
• When we make sandwiches 🥪. We place a slice of bread on a plate, then we place a slice of meat on top of the slice of bread, then place a slice of cheese on top of the slice of meat and we finally place another slice of bread on top of the slice of cheese (you can of course make a different sandwich 😄).

What is the LIFO principle?
The LIFO principle states that the last item that was placed on the stack is the first one to be taken off the stack.
In our example with the plates, the last plate that was placed on the stack is the first one that can be taken off the stack. We could of course lift some plates and take a plate from somewhere in the middle or bottom of the stack, but it's not very convenient.
In programming "lifting" items from the stack in order to take out some item that is not on the top of the stack is not allowed.

The stack data structure usually provides the following operations:

• push - used to place an item on the top of the stack.
• pop - used to remove an item from the top of the stack.
• peek - used to "see" what item is on the top of the stack without removing it.
• isEmpty - used to check if the stack is empty.
• size - used to check how many items are on the stack.

Let's give a few practical uses of the stack data structure:

• Function call stack - the functions that are executed are placed on a stack. Each item on the stack contains the data needed for the function to complete its work. The last function that was called is the first one to finish executing and the first one to be removed from the stack.
• Action undo - when we edit a document and want to undo some actions, the last action that was done is the first action to be undone.
• String reversal - we can reverse a string using a stack. Starting from the string's first character, place each character on a stack. The string's first character will be at the bottom of the stack and its last character will be at the top. Remove the characters from the stack one by one. You will get the characters in reversed order compared to the original string.

How do stacks work internally?
The stack data structure usually uses an array or a linked list internally. Generally, I would create a stack using a linked list, but it also depends on the requirements.
The "function call stack" practical example would benefit from a stack that uses a linked list. The reason is that the stack will need to grow and shrink as functions are executed. An array would not provide the needed flexibility.
The "action undo" practical example could benefit from a stack that uses a linked list, but also a stack that uses an array. A stack that uses an array could be used if we want to limit the number of actions that can be undone (e.g. last 5 actions).
The "string reversal" practical example would benefit from a stack that uses an array. We would know the length of the string that needs to be reversed and we could create a fixed size stack that uses an array.

If you enjoy my articles, please consider supporting me.