232.用栈实现队列
思路：
用两个栈实现队列操作；定义两个栈，一个栈用于出栈outStack，另一个栈用于入栈inStack；当outStack为空时，则将inStack中的元素依次出栈并且加入到outStack中；
代码：
class MyQueue {
Stack<Integer> inStack;
Stack<Integer> outStack;
public MyQueue() {
inStack = new Stack();
outStack = new Stack();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
inToOutParam();
return outStack.pop();
}
public int peek() {
inToOutParam();
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
//将inStack中的元素加入到outStack中
public void inToOutParam() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
Integer param = inStack.pop();
outStack.push(param);
}
}
}
}
225.用队列实现栈
思路：
用一个队列实现栈的话，入栈可以正常从队列的入口进入，出栈的时候将队列pop进行size-1次,然后依次重新push到队列，最后再进行一次pop将移除元素返回即可；
代码：
class MyStack {
Deque<Integer> deque;
public MyStack() {
deque = new ArrayDeque<>();
}
public void push(int x) {
deque.addFirst(x);
}
public int pop() {
//此时，用一个队列实现栈的元素应该在队尾，我们将队列前边的所有元素都重新加入队列
int num = deque.size() - 1;
while (num > 0) {
Integer last = deque.removeLast();
deque.addFirst(last);
num--;
}
return deque.removeLast();
}
public int top() {
return deque.getFirst();
}
public boolean empty() {
return deque.isEmpty();
}
}
20.有效的括号
思路：
自己的思路是，创建两个栈，一个栈按照字符串的顺序放入一个栈strStack中，另一个栈tempStack用来临时存放左括号；
1、先将字符串字符从字符串尾至头依次压入strStack栈；
2、依次对strStack出栈，如果是左括号，则直接放入temp栈中，如果是右括号，则判断tempStack栈中的左括号和当前的右括号是否匹配，如果匹配则将tempStack也出栈，如果不匹配直接返回false;
3、最后判断两个栈是否都是空，如果都是空则校验通过；
代码：
class Solution {
public boolean isValid(String s) {
Stack<Character> tempStack = new Stack<>();
Stack<Character> strStack = new Stack<>();
for (int i = s.length()-1; i >=0; i--) {
strStack.push(s.charAt(i));
}
while (!strStack.isEmpty()) {
Character pop = strStack.pop();
if (isLeft(pop)) { //如果是左括号就加入到temp栈中；
tempStack.push(pop);
continue;
}
if (isRight(pop)) {
if (tempStack.isEmpty()) {
return false;
}
//对temp进行出栈，如果temp出栈和pop对应上，则双双跳出，如果没对应上，直接返回false；
if (isMatch(tempStack.peek(), pop)) {
tempStack.pop();
} else {
return false;
}
}
}
return tempStack.isEmpty() && strStack.isEmpty();
}
public boolean isLeft(Character s) {
return '(' == s || '[' == s || '{' == s;
}
public boolean isRight(Character s) {
return ')' == s || ']' == s || '}' == s;
}
public boolean isMatch(Character left, Character right) {
if ('(' == left && ')' == right) {
return true;
}
if ('[' == left && ']' == right) {
return true;
}
if ('{' == left && '}' == right) {
return true;
}
return false;
}
}
1047.删除字符串中的所有重复项
思路：
1、定义一个栈，用来存放相邻不重复的字符；
2、对字符串s进行遍历，每次遍历到的字符c对栈顶元素进行比较，如果相同则栈顶进行pop，如果不相同则将字符c压入栈；
3、最后将栈中的元素按照栈底到栈顶的顺序输出成字符串返回即可；
代码：
class Solution {
public String removeDuplicates(String s) {
//定义一个栈从来存放未重复的字母元素
Deque<Character> deque = new ArrayDeque();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (deque.isEmpty() || deque.getFirst() != c) {
deque.addFirst(c);
} else {
deque.removeFirst();
}
}
StringBuilder sb = new StringBuilder();
while (!deque.isEmpty()) {
sb.append(deque.removeLast());
}
return sb.toString();
}
}
150.逆波兰表达式
思路：
1、先创建一个用于存放操作数的栈numStack；
2、遍历整个数组，如果不为操作数则push进操作数栈numStack中，如果为操作符的话，则从操作数栈中弹出两个操作数进行运算，并且将运算结果重新push进numStack中；
3、最后的计算结果就是numStack的最后一个元素，即栈顶元素；
代码：
class Solution {
public int evalRPN(String[] tokens) {
//用于存放操作数的栈
Stack<Integer> numStack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String token = tokens[i];
if (isCompute(token)) {
Integer num1 = numStack.pop();
Integer num2 = numStack.pop();
if ("+".equals(token)) {
numStack.push(num1+num2);
}
if ("-".equals(token)) {
numStack.push(num2-num1);
}
if ("*".equals(token)) {
numStack.push(num2*num1);
}
if ("/".equals(token)) {
numStack.push(num2/num1);
}
} else {
numStack.push(Integer.valueOf(token));
}
}
return numStack.pop();
}
public boolean isCompute(String s) {
return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s);
}
}