什么是栈
1.英文单词为Stack
2.栈是一个先入后出的有序队列(firt in last out)
3.允许插入和删除的一端称为栈顶, 另外一端称为栈底
4.最先放入的在栈底, 最后放入的在栈顶, 最后放入的先被删除, 最先放入的最后被删除
出栈入栈示意图
栈的应用场景
1.子程序的调用, 在执行子程序之前, 会把下个执行的地址存到堆栈中, 直到子程序执行完后再将地址取出, 回到原来的程序中
2.递归调用, 和子程序类似, 递归的时候会将参数
3.二叉树的遍历
4.图形的深度优先(depth-first)搜索法
用数组模拟栈的使用
思路分析
1.定义一个数组stack
2.定义一个top来表示栈顶, 初始化为-1
3.入栈, top++, stack[top] = value;
4.出栈, stack[top]; top--;
- 代码实现
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //定义一个数组模拟栈
private int top = -1; //top表示栈顶
/**
* 创建数组
* @param maxSize
*/
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
/**
* 满
* @return
*/
public boolean isFull(){
return top == maxSize-1;
}
/**
* 空
* @return
*/
public boolean isEmpty(){
return top == -1;
}
/**
* 入栈
* @param value
*/
public void push(int value){
if(isFull()){
System.out.println("栈满");
return;
}
top ++;
stack[top] = value;
}
/**
* 出栈
* @return
*/
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈空");
}
int value = stack[top];
top --;
return value;
}
/**
* 遍历栈
*/
public void list(){
if(isEmpty()){
System.out.println("栈 空");
return;
}
for(int i=top; i>=0; i--){
System.out.println(stack[i]);
}
}
}
使用栈来实现一个计算器
思路分析:
1.先定义两个栈, 数栈和符号栈, 数栈存放表达式的数字, 符号栈存放表达式的运算符
2.通过一个索引index, 遍历表达式
3.发现是数字就直接放入到数字栈
4.发现是符号, 如果符号栈为空, 直接入符号栈, 如果符号栈有运算符, 就进行比较, 如果当前的运算符优先级小于或者等于栈中的运算符, 就需要从数栈中pop出两个数, 再从符号栈中pop出一个符号, 进行运算, 将得到的结果放入数栈, 然后将当前的运算符放入到符号栈, 如果当前的运算符的优先级大于栈中的运算符, 就直接入符号栈。
5.当表达式扫描完毕, 就顺序的从数栈和符号栈中pop出相应的数和符号, 并进行运算, 最后得到的数字就是表达式的结果
- 代码实现
public class Stack {
public static void main(String[] args) {
//表达式
String expression = "3+2*6-2";
//1. 创建两个栈, 一个数字栈, 一个符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
//2. 定义一个索引, 用于遍历表达式
int index = 0;
//3.开始遍历
char c; //保存每次
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
String nums = ""; //用于拼接多位数字
while (true){
c = expression.substring(index, index+1).charAt(0);
if(operStack.isOper(c)){//是不是运算符
if(operStack.isEmpty()){// 为空直接入栈
operStack.push(c);
}else {//符号栈不为空, 做符号优先级比较
if(operStack.priority(c) <= operStack.priority(operStack.peek())){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res); //把运算结果入数栈
operStack.push(c); //把运算符入符号栈
}else {
//运算符大于栈中运算符, 直接入符号栈
operStack.push(c);
}
}
}else {//数字, 这个地方需要考虑是不是多位数
nums += c;
if(index == expression.length()-1){//表达式最后一位了, 直接入栈
numStack.push(Integer.parseInt(nums));
}else {//判断下一位是不是数字, 是数字, 就继续扫描, 如果是运算符, 就入栈
if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))){
numStack.push(Integer.parseInt(nums));
nums = "";
}
}
}
index ++;
//判断是否扫描到最后
if(index >= expression.length()){
break;
}
}
//计算
while (true){
if(operStack.isEmpty()){
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
int result = numStack.pop();
System.out.println("结果:"+ result);
}
}
/**
* 栈
*/
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //定义一个数组模拟栈
private int top = -1; //top表示栈顶
/**
* 创建数组
* @param maxSize
*/
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
/**
* 满
* @return
*/
public boolean isFull(){
return top == maxSize-1;
}
/**
* 空
* @return
*/
public boolean isEmpty(){
return top == -1;
}
/**
* 入栈
* @param value
*/
public void push(int value){
if(isFull()){
System.out.println("栈满");
return;
}
top ++;
stack[top] = value;
}
/**
* 出栈
* @return
*/
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈空");
}
int value = stack[top];
top --;
return value;
}
/**
* 返回当前栈的值, 并不是pop
* @return
*/
public int peek(){
return stack[top];
}
/**
* 遍历栈
*/
public void list(){
if(isEmpty()){
System.out.println("栈 空");
return;
}
for(int i=top; i>=0; i--){
System.out.println(stack[i]);
}
}
/**
* 是不是运算符
* @param val
* @return
*/
public boolean isOper(char val){
return val == '+' || val == '-' || val == '*' || val == '/';
}
/**
* 运算符优先级, 数字越高优先级越高
* @param oper
* @return
*/
public int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
}else if(oper == '+' || oper == '-'){
return 0;
}else {
return -1;
}
}
/**
* 计算
* @param num1
* @param num2
* @param oper
* @return
*/
public int cal(int num1, int num2, int oper){
int res = 0; //保存运算结果
switch (oper){
case '+':
res = num1 + num2;
break;
case '-':
res = num1 - num2;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num1 / num2;
break;
default:
break;
}
return res;
}
}
