【一起学数据结构与算法】深度学习栈
目录
一、什么是栈?
栈(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
二维码