CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem

## Resources

Takeaways:

- Stacks are LIFO (Last In First Out) - similar to a stack of books. When you retrieve an element from a Stack, you get the element that was added most recently.
- The last element added to a Stack is called the "top" element. This makes sense if you think about the stacking books analogy - the book you add last will be at the top!
- Stacks have fast operations: adding (pushing), removing (popping), and retrieving the top/last element (peeking) are all
`O(1)`

(constant). - Space is
`O(n)`

. - Stacks are commonly implemented with Arrays or Linked Lists. To keep my implementation simple, I went with a regular (versus dynamic) array - this means the consumer of the Stack class is required to provide a size on initialization.

Here's the finished implementation with test code:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem

## Discussion