栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
自己实现栈：
public int push(int e) {
}
public int pop(){
}
public int peek(){
}
public int size(){
}
public boolean empty(){
}
用数组实现一个栈，这个类的成员变量为数组，和整数变量，用来记录栈中的元素个数。
1，push：如果数组满了，需要进行扩容
private boolean isFull(){
return size==array.length;
}
private void expansionArray(){
array= Arrays.copyOf(array,array.length*2);
}
public int push(int val){
if (isFull()){
expansionArray();
}
array[size]=val;
size++;
return val;
}
2，pop：要取出栈顶元素，也就是数组的最后一个元素
public int pop(){
int tmp=peek();
size--;
return tmp;
}
3，peek：看一看栈顶元素
public int peek(){
if (empty()){
throw new RuntimeException();
}
return array[size-1];
}
4，size/empty：
public int size(){
return size;
}
public boolean empty(){
return size==0;
}
练习：
1，逆波兰表达式求值；
大致思路：
遍历字符串，当遇到数字时，将数字入栈，碰到运算符时，弹出两个栈顶元素，通过该运算符进行计算后，再将结果入栈，之后继续进行遍历，重复上述步骤。最后栈顶元素就是最终结果
public static int evalRPN(String[] tokens){
Stack<Integer> stack=new Stack<>();
for (int i = 0; i < tokens.length; i++) {
if(!isOperation(tokens[i])){
Integer val=Integer.valueOf(tokens[i]);
stack.push(val);
}else {
String ret=tokens[i];
int s2= stack.pop();
int s1= stack.pop();
switch (ret){
case "+":
stack.push(s1+s2);
break;
case "-":
stack.push(s1-s2);
break;
case "*":
stack.push(s1*s2);
break;
case "/":
stack.push(s1/s2);
break;
}
}
}
return stack.pop();
}
2，括号是否匹配
给一个括号的式子，看式子中的括号是否相互匹配
遍历字符串，遇到 ' ( ' , ' [ ' , ' { ' .时，入栈。如果遇到 ' ） ' , ' ] ' , ' } '.则弹出栈顶元素，并看栈顶元素和遇到的元素是否匹配。如果最后栈元素为空，则说明括号匹配成功
private static boolean isOperation(String ret){
if(ret=="+"||ret=="-"||ret=="*"||ret=="/"){
return true;
}
return false;
}
//判断括号是否匹配
public static boolean isValid(String s){
Stack<Character> stack=new Stack<>();
for (int i = 0; i <s.length(); i++) {
char ret=s.charAt(i);
if (ret=='('||ret=='['||ret=='{'){
stack.push(ret);
}
else {
if (stack.isEmpty()){
return false;
}else {
char ch2=stack.peek();
if (ch2=='('&&ret==')'||ch2=='['&&ret==']'||ch2=='{'&&ret=='}'){
stack.pop();
}
}
}
}
return stack.isEmpty();
}
3，给出两个整数数组，看第二个数组是否是第一个数组以不同方式出栈的一种结果。
遍历第一个数组，并将每一个元素放到栈中，直到栈顶元素与第二个数组的元素相同，弹出栈顶元素，并且第二个数组向后遍历，并判断栈顶元素是否与第二个数组的元素是否相同，如果相同，重复上一步骤。如果不相同继续放入数组一的元素。如果遍历完第二个数组，且栈中的元素为0，则数组二是数组一出栈的一种方式
public static boolean isPopOrder(int []pushV,int [] popV){
Stack<Integer> stack=new Stack<>();
int j=0;
for (int i = 0; i < pushV.length; i++) {
stack.push(pushV[i]);
while (!stack.isEmpty()&&stack.peek()==popV[j]&&j<popV.length){
stack.pop();
j++;
}
}
return stack.isEmpty();
}
4，创立一个类，得到最小值。类中有两个栈，一个正常放入元素，另一个的栈顶元素为第一个栈中的最小值
public class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack(Stack<Integer> stack, Stack<Integer> minStack) {
this.stack = new Stack<>();
this.minStack = new Stack<>();
}
}
（1）push：如果minStack为空，在stack，minStack中均放入该元素。如果放入的元素大于minStack的栈顶元素，则不放入minStack，如果放入的元素小于minStack栈顶元素，则将该元素放入minStack
public void push(int val){
if (minStack.isEmpty()){
stack.push(val);
minStack.push(val);
}else {
if (minStack.peek()>val){
minStack.push(val);
}
stack.push(val);
}
}
（2）pop：弹出stack的栈顶元素，如果stack的栈顶元素与minStack的栈顶元素相同，则minStack也弹出栈顶元素。
public void pop(){
if (stack.isEmpty()){
return;
}
if (stack.peek()==minStack.peek()){
minStack.pop();
stack.pop();
}else {
stack.pop();
}
}
（3）top：打印stack的栈顶元素
public int top(){
if (stack.isEmpty()){
return -1;
}
return stack.peek();
}
（4）getMin：打印stack中的最小值，也就是minStack的栈顶元素
public int getMin(){
if (stack.isEmpty()){
return -1;
}
return minStack.peek();
}