栈 / 队列
带最小值操作的栈
实现一个栈, 额外支持一个操作:min() 返回栈中元素的最小值
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack; // 维护一个辅助栈,传入当前栈的最小值
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int number) {
stack.push(number);
if (minStack.isEmpty()) {
minStack.push(number);
} else {
minStack.push(Math.min(number, minStack.peek()));
}
}
public int pop() {
minStack.pop();
return stack.pop();
}
public int min() {
return minStack.peek();
}
}
有效括号
给定一个字符串所表示的括号序列,包含以下字符: '(', ')', ', ', '[' and ']', 判定是否是有效的括号序列。括号必须依照 "()" 顺序表示, "()[]" 是有效的括号,但 "([)]" 则是无效的括号。
public boolean isValidParentheses(String s) {
Stack<Character> stack = new Stack<Character>();
for (Character c : s.toCharArray()) {
if ("({[".contains(String.valueOf(c))) {
stack.push(c);
} else {
if (!stack.isEmpty() && isValid(stack.peek(), c)) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
private boolean isValid(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
用栈实现队列
public class MyQueue {
private Stack<Integer> outStack;
private Stack<Integer> inStack;
public MyQueue() {
outStack = new Stack<Integer>();
inStack = new Stack<Integer>();
}
private void in2OutStack(){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
public void push(int element) {
inStack.push(element);
}
public int pop() {
if(outStack.isEmpty()){
this.in2OutStack();
}
return outStack.pop();
}
public int top() {
if(outStack.isEmpty()){
this.in2OutStack();
}
return outStack.peek();
}
}
逆波兰表达式求值
在反向波兰表示法中计算算术表达式的值, ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<Integer>();
String operators = "+-*/";
for (String token : tokens) {
if (!operators.contains(token)) {
s.push(Integer.valueOf(token));
continue;
}
int a = s.pop();
int b = s.pop();
if (token.equals("+")) {
s.push(b + a);
} else if(token.equals("-")) {
s.push(b - a);
} else if(token.equals("*")) {
s.push(b * a);
} else {
s.push(b / a);
}
}
return s.pop();
}