数据结构(2)栈的动态数组实现ArrayStack
栈本身是一种特殊的线性表,我们上一章说到,我们可以在线性表中的任意位置进行增删查改操作,前提是这个位置是存在的。
那么栈又有何特殊性呢?在栈里面,我们只能对其一端进行增删查改的操作,这个端我们称之为栈顶,另一端不进行操作的我们称之为栈底
栈:又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈又是一个先进后出LIFO的结构(Last In,First Out)
如图所示入栈操作,入栈顺序1-2-3-4
如图所示出栈操作,出栈顺序4-3-2-1
其实也不难发现,入栈操作,相当于在ArrayList中表尾添加元素;出栈操作,相当于在ArrayList中删除表尾元素
我们完全可以由上一章的ArrayList来实现我们的栈结构,当然这种实现方式本质上是动态数组实现的栈
当然也可以用动态链表实现,我们后面章节再说
同样和线性表一样,为了统一栈的操作规范,定义栈接口,代码如下
Stack.java
public interface Stack<E> {
public void push(E e); //进栈元素e
public E pop(); //出栈元素e
public E peek(); //查看当前栈顶元素,不取出
public boolean isEmpty(); //判断栈是否为空
public int getSize(); //获取栈中元素的个数
public void clear(); //清空栈
}
既然说了用ArrayList来实现栈,那就把ArrayList当成栈的一个成员变量即可,对栈的操作就相当于对线性表的操作
代码很简单,这里就不用细说了,大家能看懂
ArrayStack.java
/**
@Author Teacher_HENG
*/
//栈的动态数组实现方式
public class ArrayStack<E> implements Stack<E> {
private ArrayList<E> list;
public ArrayStack(){
this(10);
}
public ArrayStack(int capacity){
list=new ArrayList<>(capacity);
}
@Override
public void push(E e) {
list.addLast(e);
}
@Override
public E pop() {
return list.removeLast();
}
@Override
public E peek() {
return list.getLast();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public int getSize() {
return list.getSize();
}
@Override
public void clear() {
list.clear();
}
public int getCapacity(){
return list.getCapacity();
}
}