栈

说到栈，学了面向对象就很了解，面向对象说过的主函数进栈，构造函数进栈、构造函数弹栈，都是在对栈的操作，比如我们主函数先进栈，构造函数再 进栈，我们无法先将主函数弹栈，只能等构造函数弹栈后，再操作。由此就可以得到栈的定义：栈是限定仅在表尾进行插入和删除操作的线性表。

栈这种后进先出数据结构的应用是非常普遍的，例如子弹夹，最后进入弹夹的子弹总是最先射出去。

我们把允许插入和删除的一端称为栈顶（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();

}

}

写完顺序栈的基本方法，可以写一个测试类测试一下各个方法的正确性。