栈相关问题
class MinStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MinStack() {
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}
public void push(int val) {
stack1.push(val);
if(stack2.isEmpty() || val<stack2.peek()){
stack2.push(val);
}else{
stack2.push(stack2.peek());
}
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
this.q1 = new LinkedList<>();
this.q2 = new LinkedList<>();
}
public void push(int x) {
q1.offer(x);
}
public int pop() {
while(q1.size() > 1){
int val = q1.poll();
q2.offer(val);
}
int res = q1.poll();
while(q2.size() > 0){
q1.offer(q2.poll());
}
return res;
}
public int top() {
int res = 0;
while(q1.size() > 0){
if(q1.size() == 1){
res = q1.peek();
}
int val = q1.poll();
q2.offer(val);
}
while(!q2.isEmpty()){
q1.offer(q2.poll());
}
return res;
}
public boolean empty() {
return q1.size() == 0;
}
}
/**
* 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 Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String s:tokens){
if(s.equals(“+”)){
int a = stack.pop();
int b = stack.pop();
stack.push(a+b);
}else if(s.equals(“-“)){
int a = stack.pop();
int b = stack.pop();
stack.push(b-a);
}else if(s.equals(“*”)){
int a = stack.pop();
int b = stack.pop();
stack.push(a*b);
}else if(s.equals(“/”)){
int a = stack.pop();
int b = stack.pop();
stack.push(b/a);
}else{
stack.push(Integer.parseInt(s));
}
}
return stack.peek();
}
}
class Solution {
public String decodeString(String s) {
Stack<Integer> num_stack = new Stack<>();
Stack<String> dict_stack = new Stack<>();
int n = s.length();
String res = “”;
for(int i=0;i<n;i++){
char ch = s.charAt(i);
if(Character.isDigit(ch)){
int num = ch – ‘0’;
while(i+1 < n && Character.isDigit(s.charAt(i+1))){
num = num*10 + s.charAt(i+1)-‘0’;
i++;
}
num_stack.push(num);
}else if(ch == ‘[‘){
dict_stack.push(“[“);
}else if(Character.isLetter(ch)){
dict_stack.push(ch+“”);
}else if(ch == ‘]’){
String temp = “”;
while(dict_stack.peek() != “[“){
temp = dict_stack.pop() + temp;
}
dict_stack.pop();
int repeat = num_stack.pop();
String local = “”;
for(int j=0;j<repeat;j++){
local += temp;
}
dict_stack.push(local);
}
}
while(!dict_stack.isEmpty()){
res = dict_stack.pop() + res;
}
return res;
}
}