先来看一个实际需求
根据用户输入的表达式,得出计算结果,这样一个程序怎么写? 对于计算机而言,用户的输入就是一个字符串,这里就涉及到数字拆分、运算符解析、运算符优先级。感觉很麻烦。
而栈这样的一个数据结构就可以解决上述问题。
栈是一个先入后出的有序列表。 栈是限制线性表中元素的插入和删除只能在线性表的同一段进行的一种特殊线性表。允许插入和删除的一端为变化的一端称为栈顶,另一端为固定的一端称为栈底。 先放入栈中的元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素是先删除,最先放入的元素后删除
入栈与出栈示意图
定义一个Top来表示栈顶,初始化为 -1 入栈的操作:当有数据入栈时,top++;stack[top] = data
出栈的操作:当弹出数据时,int value = stack[top];top--return value
class ArrayStack{
private int maxSize;
private int[] stack; //栈数组
private int top = -1; //栈顶
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
//判断栈是否满
public boolean isFull(){
return top == maxSize - 1;
}
//栈是否为空
public boolean isEmpty(){
return top == -1;
}
//入栈
public void push(int value){
if(isFull()){
System.out.println("栈已满,不能放");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
int value = stack[top];
top--;
return value;
}
//显示栈中的元素
public void list(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
//从栈顶开始显示数据
for(int i = top ; i >= 0 ;i--){
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
}