The Stack Data Structure
Following my Big-O notation post I decided to talk about stacks. A stack is a simple data structure that provides LIFO (Last In First Out) functionality. It is used in a variety of ways such as functions (the undo command), parsers, regular expression evaluation and backtracking algorithms to name a few.
Operations Of A Stack
In your everyday life you see and interact with stacks all the time: a stack of books, a stack of cards, a stack of dirty dishes or a stack of cash 💰. In all of these scenarios think about how you interact with them. You always put stuff on top and take off the top element. You wouldn’t grab the bottom dish in the sink would you? No, you grab the top dish and work your way down. This is how a stack works.
There are only two main operations you have when using a stack; push and pop. The push operations pushes a new element onto the top of the stack, whereas the pop operation removes the top element of the stack. It is because of the simplicity of only working with the top element that the runtime for insertion and deletion on a stack is O(1)!
The stack data structure is one of the easiest to comprehend and conceptualize! In my next tutorial and video I will go over the queue data structure and its operations enqueue and dequeue. If you haven’t subscribed to my Youtube channel please do so, so you can be in the loop and catch my livestreams. For more data structure and run time analysis help, check out my cheat sheet and support the blog!
Big-O Notation Cheat SheetProduct on sale