栈是一个先入后出的有序列表。
栈是限制线性表中元素的插入和删除只能在线性表的同一端进行操作的一种特殊线性表。其中,允许插入和删除的一端为变化的一段,称为栈顶(Top),另一端为固定的一端,称为栈底。
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除的元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
使用数组来模拟栈
定义一个top来表示栈顶,初始化为-1
入栈:top++;stack[top]=data;
出栈:int value =stack[top];top--;return value
//定义一个ArrayStack 表示栈 class ArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组,数组模拟栈,数据就放在该数组 private int top =-1; //top 表示栈顶 初始化为-1 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int [this.maxSize]; } //栈满 public boolean isFull(){ return top==maxSize-1; } //栈空 public boolean isEmpty(){ return top==-1; } //入栈 push public void push(int value){ //先判断栈是否满 if(isFull()){ System.out.println("栈满!"); return; } top++; stack[top] = value; } //出栈 pop public int pop(){ if(isEmpty()){ throw new RuntimeException("栈空!没有数据!"); }else { int value = stack[top]; top--; return value; } } //栈的遍历 遍历时需要从栈顶开始显示数据 public void showStack(){ if(isEmpty()){ System.out.println("栈为空,没有数据!"); } for(int i=top;i>-1;i--) System.out.printf("stack[%d]=%d\n",i,stack[i]); } }