程序员：数据结构与算法，顺序栈简介
栈
说到栈，学了面向对象就很了解，面向对象说过的主函数进栈，构造函数进栈、构造函数弹栈，都是在对栈的操作，比如我们主函数先进栈，构造函数再 进栈，我们无法先将主函数弹栈，只能等构造函数弹栈后，再操作。由此就可以得到栈的定义：栈是限定仅在表尾进行插入和删除操作的线性表。
栈这种后进先出数据结构的应用是非常普遍的，例如子弹夹，最后进入弹夹的子弹总是最先射出去。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），栈又被称为后进先出的线性表，也就是说栈元素有线性关系，只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里的表尾是指栈顶，而不是栈底。
栈的插入操作，叫作进栈，也称为压栈，入栈。类似子弹入弹夹。
栈的删除操作，叫作出栈，也叫作弹栈，如同弹夹中的子弹出来。
栈的抽象数据类型我们定义为接口Stack，用Java语言实现，基本内容如下：（其中的方法都是抽象的，有public abstract，这里我们省略了）
public interface Queue<E> extends Iterable {
//获取队列中元素的个数
int getSize();
//判断队列是否为空
boolean isEmpty();
//入队一个元素
void enqueue(E e);
//出队一个元素
E dequeue();
//获取队头
E getFront();
//获取队尾
E getRear();
//清空队列
void clear();
}
接下来写顺序栈ArrayStack，让它实现接口Stack，顺序栈内部是由顺序表实现的，之前我写了顺序表ArrayList，只需要创建ArrayList对象list，重复的方法直接调用list的方法实现。
import java.util.Iterator;
/*
顺序栈内部是有顺序表实现的
ArrayStack
ArrayList
*/
public class ArrayStack<E> implements Stack<E> {
private ArrayList<E> list;
//创建一个默认大小的栈
public ArrayStack(){
//创建顺序表对象list
list = new ArrayList<>();
}
//创建一个容量由用户指定的顺序栈
public ArrayStack(int capacity){
list = new ArrayList<>(capacity);
}
//获取有效元素个数这个方法，顺序表中有，直接调用
@Override
public int getSize() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E e) {
//进栈从表尾进，调用addLast
list.addLast(e);
}
@Override
public E pop() {
//出栈元素从表尾出，调用removeLast
return list.removeLast();
}
//查看当前栈顶
@Override
public E peek() {
return list.getLast();
}
@Override
public void clear() {
//清空栈和清空顺序表一样，直接调用
list.clear();
}
@Override
public Iterator<E> iterator() {
//迭代器也是直接调用
return list.iterator();
}
//顺序栈的toString方法，重新写
public String toString(){
//创建StringBuilder对象，不需要额外创字符串，在原来的上加字符
StringBuilder sb = new StringBuilder();
sb.append(String.format("ArrayStrck: %d/%d\n",getSize(),list.getCapacity()));
//用数组的形式输出
sb.append('[');
if(isEmpty()){ //若为空，打印 []
sb.append(']');
}else{
for(int i=0;i<getSize();i++){
//在原来上加字符
sb.append(list.get(i));
if(i==list.getSize()-1){
sb.append(']'); //遍历到最后一个元素打印']'
}else{
sb.append(','); //不然在每个元素中间打','
}
}
}
//调用对象的tostring方法返回对象
return sb.toString();
}
}
写完顺序栈的基本方法，可以写一个测试类测试一下各个方法的正确性。