数据结构篇|栈
1. 简介
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——出自百度百科
栈的使用场景
- 编辑器的撤销操作
- 程序系统栈的调用
2. 栈的实现
实现这个栈在这里我选择复用上一篇文章实现的数组的一些方法，链接如下：
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
将实现的Array类拷贝过来之后，接着我们需要创建一个接口，这个接口中包含上图代码所示的方法，方法的作用基本和字面意思一样。getSize()方法表示获取栈中元素的个数，isEmpty()表示判断栈是否为空，push()表示向栈中添加一个E类型的元素，这里的E是泛型的类型，pop()方法是将一个元素进行出栈，peek()方法表示查看栈顶的元素是什么并将其返回。
3. 实现类的设计
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
}
创建完了接口之后我们再创建一个实现类，就取名叫做ArrayStack。类中包含的成员变量是复制过来的Array类，然后还有两个构造方法，第一个是需要传入一个栈的容量capacity，然后在方法中实现Array类并将容量设置为capacity。第二个构造方法适用于不知道栈需要多大容量的情况，这里就直接实例化Array类，那么容量就是10了。
- getSize()、isEmpty()方法的实现
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
这两个方法非常简单，getSize()方法是获得栈中元素个数的方法，那么就直接调用Array类中的getSize()方法即可。isEmpty()也是同样的，直接调用Array类中的方法即可。
- getCapacity()方法
public int getCapacity(){
return array.getCapacity();
}
这个方法的作用是获取栈的容量，那么直接调用对应方法即可。
- push()、pop()、peek()方法
@Override
public void push(E e){
array.addLast(e);
}
@Override
public E pop(){
return array.removeLast();
}
@Override
public E peek(){
return array.get(array.getSize()-1);
}
这三个方法的实现也是可以复用Array类中的方法的。push()方法是向栈中添加元素，这里我们调用addLast()方法，直接向数组的末尾添加元素。pop()方法是让栈顶元素出栈，所以直接调用removeLase()即可。peek()方法是为了查看栈顶元素，所以我们需要查看数组中的最后一个元素。这里调用了Array类中的get()方法，传入的参数是数组中的最后一个元素。
-
测试ArrayStack
这样我们就通过复用自己实现的Array类，实现了栈应该具有的功能。接下来就实现一个方法来测试我们的栈吧！
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1){
res.append(", ");
}
}
res.append("] Top");
return res.toString();
}
