1. Stack

• First In Last Out (a pile of books)
• Insertion at the top, Deletion at the top
• History of the visited pages, Undo sequence, chain of method calls in JVM, Auxiliary data structure for algorithms, component of other data structures
• What does the JVM do?

2. Operation

3. Implementation

Array-based Stack

One variable to keep track

• t : the index of the top element

• Performance The space usage : O(N) *N = the size of the array Each operation(deletion, insertion) runs in O(1)
• Limitation(stak based on array) The maximum size of the stack must be defined in advance, cannot be changed Trying to push a new element into a full stack causes an implementation-specific exception

4. Application

Checking if Parentheses are matching

• push when it's an opening
• pop when it's a closing, and it matches the one at the top

Evaluate Postfix