class MyQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public MyQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
while (!stack2.isEmpty()) {
return stack2.pop();
}
int len = stack1.size();
for (int i = 0; i < len; i++) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
public int peek() {
while (!stack2.isEmpty()) {
return stack2.peek();
}
int len = stack1.size();
for (int i = 0; i < len; i++) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
//真正意义上，理解写一个类的方法，也就是深入源码。
//绝对的理解栈和队列的题目，包括交换、反转，这个题目得重点看一下
//单个队列转成栈得写法
class MyStack {
LinkedList<Integer> queue;
public MyStack() {
//这样写错了
//LinkedList<Integer> queue = new LinkedList<Integer>();
queue = new LinkedList<Integer>();
}
public void push(int x) {
//一个数我不需要交换，两个数我需要交换一次，n个交换n-1次
int len = queue.size();
queue.offer(x);
for (int i = 0; i < len; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
//两个队列得写法
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
//一个队列作为辅助队列，很简单额，我服了
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
//栈出场，栈是一种逻辑数据结构，可以用数组和链表实现。注意，是逻辑
class Solution {
public boolean isValid(String s) {
if (s.isEmpty()) return true;
Deque<Character> stack = new LinkedList<>();
for (Character x : s.toCharArray()) {
if (x == '(') {
stack.push(')');
} else if (x == '[') {
stack.push(']');
} else if (x == '{') {
stack.push('}');
} else if (stack.isEmpty() || x != stack.pop()){
return false;
}
}
if (stack.isEmpty()) {
return true;
}
return false;
}
}
//不能说自己思路不够开阔吧，应该是没有思路、、、
//获取栈首元素后，元素不会出栈stack.peek()
//获取栈首元素后，元素将会出栈stack.pop()
class Solution {
public boolean isValid(String s) {
int len = s.length();
if (len % 2 == 1) return false;
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
if (stack.isEmpty() || stack.peek() != map.get(c)) {
return false;
} else {
stack.pop();
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
// class Solution {
// public String removeDuplicates(String s) {
// Deque<Character> stack = new LinkedList<>();
// for (int i = 0; i < s.length(); i++) {
// char c = s.charAt(i);
// if (!stack.isEmpty() && c == stack.peek()) {
// stack.pop();
// } else {
// stack.push(c);
// }
// }
// Deque<Character> stackTemp = new LinkedList<>();
// StringBuilder res = new StringBuilder();
// while (!stack.isEmpty()) stackTemp.push(stack.pop());
// while (!stackTemp.isEmpty()) res.append(stackTemp.pop());
// return res.toString();
// }
// }
//StringBuilder本身就可以作为栈
class Solution {
public String removeDuplicates(String s) {
StringBuffer stack = new StringBuffer();
int top = -1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (top >= 0 && stack.charAt(top) == ch) {
stack.deleteCharAt(top);
top--;
} else {
stack.append(ch);
top++;
}
}
return stack.toString();
}
}
// //队列不行哦，获取的是首元素，别想当然
// class Solution {
// public String removeDuplicates(String s) {
// Queue<Character> queue = new LinkedList<>();
// for (int i = 0; i < s.length(); i++) {
// char c = s.charAt(i);
// if (!queue.isEmpty() && c == queue.peek()) {
// queue.poll();
// } else {
// queue.offer(c);
// }
// }
// StringBuilder res = new StringBuilder();
// while (!queue.isEmpty()) res.append(queue.poll());
// return res.toString();
// }
// }
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack1 = new LinkedList<>();
Deque<String> stack2 = new LinkedList<>();
for (int i = 0; i < tokens.length; i++) {
String token = tokens[i];
//判断字符s.charAt(i)内容是否是数字isDigit
//这是自己写的方法，判断字符串是否是数字
if (isNumber(token)) {
stack1.push(Integer.parseInt(token));
} else {
stack2.push(token);
}
if (!stack2.isEmpty()) {
int value1 = stack1.pop();
int value2 = stack1.pop();
//弹栈是一个操作，所以在if的时候就会执行了，这样多次if就重复了，所以提前弹出来记录。
String s = stack2.pop();
if ("+".equals(s)) {
int value3 = value1 + value2;
stack1.push(value3);
} else if ("-".equals(s)) {
int value3 = value2 - value1;
stack1.push(value3);
} else if ("*".equals(s)) {
int value3 = value2 * value1;
stack1.push(value3);
} else {
int value3 = value2 / value1;
stack1.push(value3);
}
}
}
return stack1.pop();
}
public static boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
// class Solution {
// public int evalRPN(String[] tokens) {
// Deque<Integer> stack = new LinkedList<Integer>();
// int n = tokens.length;
// for (int i = 0; i < n; i++) {
// String token = tokens[i];
// if (isNumber(token)) {
// stack.push(Integer.parseInt(token));
// } else {
// int num2 = stack.pop();
// int num1 = stack.pop();
// switch (token) {
// case "+":
// stack.push(num1 + num2);
// break;
// case "-":
// stack.push(num1 - num2);
// break;
// case "*":
// stack.push(num1 * num2);
// break;
// case "/":
// stack.push(num1 / num2);
// break;
// default:
// }
// }
// }
// return stack.pop();
// }
// public boolean isNumber(String token) {
// return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
// }
// }