# 一、什么是栈？

（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

# 二、怎么使用栈？

## 2.1 入栈 - push()

``````        Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
System.out.println(s1);
``````

## 2.2 判空 - empty()

``````        Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
System.out.println(s1.empty());

``````

## 2.3 出栈 - pop()

``````      Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
System.out.println(s1);
s1.pop();
System.out.println(s1);
``````

## 2.4 获取栈顶元素 - peek()

``````        Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
System.out.println(s1);
s1.peek();
System.out.println(s1);
System.out.println(s1.peek());
``````

## 2.5 获取栈中有效元素个数 - size()

``````        Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
System.out.println(s1.size());
``````

# 三、栈的模拟实现

## 3.1 push

``````	public boolean isFull() {
return this.usedSize == this.elem.length;
}

public void push(int val) {
if (isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.usedSize);
}
this.elem[this.usedSize] = val;
this.usedSize++;
}
``````

## 3.2 isEmpty

``````	public boolean isEmpty() {
return this.usedSize == 0;
}
``````

## 3.3 pop

``````	public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
int oldVal = this.elem[usedSize-1];
this.usedSize--;
return oldVal;
}
``````

## 3.4 peek

``````	public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return this.elem[usedSize-1];
}
``````

## 3.5 MyStack.java

``````import java.lang.reflect.Array;
import java.util.Arrays;

@SuppressWarnings({"all"})
public class MyStack {
public int[] elem;
public int usedSize;

public MyStack() {
this.elem = new int[5];
}

public void push(int val) {
if (isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.usedSize);
}
this.elem[this.usedSize] = val;
this.usedSize++;
}

public boolean isFull() {
return this.usedSize == this.elem.length;
}

public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
int oldVal = this.elem[usedSize-1];
this.usedSize--;
return oldVal;
}

public int peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return this.elem[usedSize-1];
}

public boolean isEmpty() {
return this.usedSize == 0;
}
}

``````

# 四、经典题

## 4.1 有效的括号

``````class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();

for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '[' || ch == '{') {
//如果是左括号 直接入栈
stack.push(ch);
} else {
//遇到了右括号
if (stack.empty()) {
System.out.println("右括号多");
return false;
}
char top = stack.peek();//哪个左括号
if (top == '(' && ch ==')' || top == '[' && ch ==']' || top == '{' && ch =='}') {
stack.pop();
} else {
System.out.println("左右括号不匹配");
return false;
}
}
}
if (!stack.empty()) {
System.out.println("左括号多");
return false;
}
return true;
}
}
``````

## 4.2 逆波兰表达式求值

``````class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String val = tokens[i];
if (!isOperation(val)) {
stack.push(Integer.parseInt(val));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (val) {
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.pop();
}
private boolean isOperation(String x) {
if (x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
return true;
}
return false;
}
}
``````

THE END