A stack is a data structure that stores items in a Last-In/First-Out (LIFO) manner. This means that the last item inserted into a stack is the first one to be removed.
This is analogous to a stack of books. The last book placed on the stack is the first one to be removed. The books are removed in the reverse order of their placement.
A stack is useful when the order of items is important. For example, a stack can be used to implement a browser's back button.
A stack can be implemented using a linked list or an array. In this repository, the stack is implemented using a linked list.
On worst case, the time complexity of the following operations is:
| Operation | Time Complexity |
|---|---|
| Insertion | O(1) |
| Deletion | O(1) |
The space complexity of a stack is O(n), where n is the number of elements in the stack.