Data Structures — Stacks
Algorithms and Data Structures From Zero to Hero
In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations:
Push, which adds an element to the collection, and
Pop, which removes the most recently added element that was not yet removed. — Wikipedia
Basically, a stack is an ordered list in which insertion and deletion are done at one end, where the end is generally call the top. Last In, First Out (LIFO) or First In, Last Out (FILO).
Analogy
Imagine you work in a restaurant cleaning plates and you have plates stacked on top of each other in the canteen. The plate that is on top is the first to be removed, i.e. the plate that has been placed in the lowest position remains in the stack for the longest time. Therefore, it can simply be seen that the LIFO (Last In First Out) / FILO (First In Last Out) order is followed.
Time complexity:
- push(): O(1)
- pop(): O(1)
- peek(): O(1)
Implementation:
You can implement a Stack using an Array or Linked List there are some pros and cons to choosing one or the other.
Pros:
- Stack using Linked: Is more secure, reliable as they do not get corrupted easily and clean the objects automatically.
- Stack using Array: Easy to implement and memory saved pointer are not involved as we have random access.
Cons:
- Stack using Linked: Extra memory is required, total size have to be defined before and if the stack fall outside the memory can lead anormal termination.
- Stack using Array: The main disadvantage is that doesn’t grow and shrink depending on needs at runtime.
Summary
A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.
⬅️ Arrays and Linked List | Table of content | Data Structures — Queues ➡️
