class MinStack {Stack <Integer>stack;Stack  <Integer>minStack; public MinStack() {stack=new Stack<>();minStack=new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()) {minStack.push(val);} else {int topval=minStack.peek();if(val<=topval) {minStack.push(val);}}}public void pop() {if(stack.peek().equals(minStack.peek())) {minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

public class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();char ch;for (int i = 0; i < s.length(); i++) {ch=s.charAt(i);if(ch=='{'||ch=='['||ch=='(') {stack.push(ch);} else if (stack.empty()){return false;} else if(stack.peek().equals('(')&&ch==')'||stack.peek().equals('{')&&ch=='}'||stack.peek().equals('[')&&ch==']'){stack.pop();} else {return false;}}return stack.empty();}
}

public class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for (int i = 0; i <tokens.length; i++) {if(opinion(tokens[i])) {int val1=stack.pop();int val2=stack.pop();switch(tokens[i]) {case "+":stack.push(val1+val2);break;case "-":stack.push(val2-val1);break;case  "*":stack.push(val1*val2);break;case "/":stack.push(val2/val1);break;}} else {stack.push(Integer.parseInt(tokens[i]));}}return stack.pop();}private boolean opinion(String ch) {return ch.equals("*")||ch.equals("+")||ch.equals("/")||ch.equals("-");}
}

  public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack1=new Stack();int j=0;for(int i=0;i<pushV.length;i++) {stack1.push(pushV[i]);while(j<popV.length&&!stack1.empty()&&stack1.peek()==popV[j]) {stack1.pop();j++;}}return stack1.empty();}
}

public class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1=new LinkedList<>();queue2=new LinkedList<>();}public void push(int x) {if(empty()){queue1.offer(x);} else if  (!queue2.isEmpty()){queue2.offer(x);} else  {queue1.offer(x);}}public int pop() {int val=0;if(empty()) {return -1;} else {if (!queue1.isEmpty()) {int count=queue1.size()-1;while(count!=0) {queue2.offer(queue1.poll());count--;}val=queue1.poll();}else {int count=queue2.size()-1;while(count!=0) {queue1.offer(queue2.poll());count--;}val= queue2.poll();}}return val;}public int top() {int temp=0;if(empty()) {return -1;} else {if (!queue1.isEmpty()) {int count=queue1.size();while(count!=0) {temp=queue1.peek();queue2.offer(queue1.poll());count--;}}else  {int count=queue2.size();while(count!=0) {temp=queue2.peek();queue1.offer(queue2.poll());count--;}}}return temp;}public boolean empty() {return queue1.isEmpty()&&queue2.isEmpty();}
}

public class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1=new Stack<>();stack2=new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(!stack2.empty()) {int val= stack2.pop();return val;} else if(!stack1.empty()) {int count = stack1.size();while(count!=0) {stack2.push(stack1.pop());count--;}return stack2.pop();}return -1;}public int peek() {if(!stack2.empty()) {int val= stack2.peek();return val;} else if(!stack1.empty()) {int count = stack1.size();while(count!=0) {stack2.push(stack1.pop());count--;}int val=stack2.peek();return val;}return -1;}public boolean empty() {return stack1.empty()&&stack2.empty();}
}