Stack
1.Introduction
Last element you add to the stack is the first one you access (Last In First Out)
Top (最後一個)
Push: Adding a new element to the top of the stack
Pop: Removing an element from the top of the stack
Peek
2.The complexity
Push, pop: O(1)
isEmpty, IsFull, size: O(1)
3.Where can stacks be used
Implementing undo in an application
Implementing the back button on the web browser
Holding the memory for recursive calls in a programming language
Translating infix notation for expressions to postfix
4.Match parenthesis in an expression
map: 存放} {, ) (, ] [
set: 存放{, (, [
stack: 後進先出, 用來確認上一個元素是否符合map的值
private static final Map<Character, Character> matchingParentsMap = new HashMap<>();
private static final Set<Character> openingParentSet = new HashSet<>();
static {
matchingParentsMap.put(')', '(');
matchingParentsMap.put(']', '[');
matchingParentsMap.put('}', '{');
openingParentSet.addAll(matchingParentsMap.values());
}
public static boolean hasMatchingParents(String input) {
try {
Stack<Character> parentStack = new Stack();
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
// Add to the stack for an opening parent
if (openingParentSet.contains(ch)) {
parentStack.push(ch);
}
if (matchingParentsMap.contains(ch)) {
Character lastParent = parentStack.pop();
if (lastParent != matchingParentsMap.get(ch)) {
return false;
}
}
}
return parentStack.isEmpty();
} catch (Stack.StackOverflowException soe) {
System.err.println("Stack StackOver");
} catch (Stack.StackUnderflowException sue) {
System.err.println("Stack StackUnder");
}
}
5.Find the minimum element in a stack in constant time
public static class MinimumStack{
private Stack<Integar> stack = new Stack<>;
private Stack<Integar> minimumStack = new Stack<>;
public void push(int data) throws
Stack.StackOverflowException,Stack.StackUnderflowException {
int min = data;
if (!miniStack.isEmpty()) {
if (min > minimumStack.peek()) {
min = minimumStack.peek();
}
}
stack.push(data);
minimumStack.push(min);
}
public int pop() throw Stack.StackUnderflowException {
minimumStack.pop();
return stack.pop();
}
public int getMinimum() throw Stack.StackUnderflowException {
return minimumStack.peek();
}
}
Last updated