One Pager Cheat Sheet

• In this lesson, we'll cover the concept ofAbstract Data Types (ADTs), and focus on learning aboutstacksand its time complexities, as well as how to use them in programming interviews.
• A Stack is an ADT that allows for the addition and removal of objects in a specific order.
• A stack is a data structure that follows the Last in, First out (LIFO) principle by requiring all items to be added or removed from the top so that the most recent element is always the first one to be removed.
• A Stack is a Last In, First Out (LIFO) data structure, where elements are only inserted or removed from the top, similar to "stacking" trays or plates in a cafeteria.
• 10 got pushed to the bottom and 20 has now been pushed onto the stack, making 20 the first and last element.
• When the stack.pop() method is used, the last inserted element (in this case 20) is removed, resulting in 10 becoming the sole first element.
• In a stack, you can only pop elements off the top, meaning that in order to remove an element from somewhere in the middle, you must pop off all the elements above it first.
• Stack overflow occurs when we try to push an element onto a stack already at max capacity, and stack underflow happens when we try to pop an element from an empty stack.
• You need to define a size for the Stack class so that it is not in an overflow or underflow state, although the default in C++ is usually sufficiently large.
• Stacks are commonly used for browser navigation, Windows operations, expression notation, syntax parsing, backtracking, memory monitoring, string reversing and a popular graph algorithm, DFS.
• The push and pop operations are of constant time complexity O(1), while the space complexity is O(n).
• We can implement a Stack by initializing an array of size MAXSIZE for stack[] and using methods such as push(), pop(), peek(), getSize() and print().
• The top of a stack with a MAXSIZE of 9 is used to determine if the stack is empty or full and also indicates the position of where new elements must be stored.
• A stack data structure consists of important functions such as pop and push, followed by operations such as push, pop, peek, getSize, etc. that are all called within the main function.
• We can implement a stack using Nodes of a Linked List in multiple programming languages.
• We can create aNodeclass and then use it to start setting up our StackLL class with the top node initialized as null.
• When top is not null, push adds a new element to the stack by making top point to a new Node containing the item.
• We inserted our item into a Node, creating a reference to top as the next Node and assigning top to this new node.
• We remove an item from the stack by changing the reference node from the current top node to the next one, i.e. top = top.next.
• The top() function is used to check the top.data value in a node; the isEmpty() method then compares top to null to check if the stack has a value or is empty.
• Stacks are Abstract Data Types which remain unchanged regardless of the underlying data structure and programming language used to implement them.