数据结构之栈篇

栈(Stack)

关于栈

• 栈是一种线性的数据结构
• 相比数组，栈对应的操作是数组的子集
• 只能从一端添加元素，也只能从同一端取出元素（这一端称为栈顶）
• 后进先出（Last In First Out）

栈对应的操作

• Stack<E>
• 向栈中添加元素：void push(E)
• 从栈顶取出元素：E pop()
• 删除栈顶元素: E peek()
• 其它操作(如获取栈的大小，判断栈是否为空)

实现栈

1. 接口的实现

   /** * 栈接口 * @author wbkearly * @param <E> 栈中元素类型 */ public interface Stack<E> { /** * 获取栈中元素个数 * @return 栈中元素个数 */ public int getSize(); /** * 判断栈是否为空 * @return 栈是否为空 */ public boolean isEmpty(); /** * 将元素e压入栈中 * @param e 要压入栈的元素e */ public void push(E e); /** * 栈顶元素出栈 * @return 栈顶元素 */ public E pop(); /** * 获取栈顶元素 * @return 栈顶元素 */ public E peek(); } 

2. 基于自己实现的数组类来实现栈的相关操作(ArrayStack)，这里的Array类是在我之前博客中所创建的Array类，由于Array中的操作已经非常的详细，我们在创建Stack时只需要非常简单的进行函数的调用就可以了。

   /** * 基于Array实现的栈 * @author wbkearly * @param <E> 栈中元素类型 */ public class ArrayStack<E> implements Stack<E> { private Array<E> array; /** * 构造函数,传入栈容量capacity初始化栈 * @param capacity 栈容量 */ public ArrayStack(int capacity) { array = new Array<>(capacity); } /** * 无参构造函数,栈容量默认capacity=10 */ public ArrayStack() { array = new Array<>(); } @Override public int getSize() { return array.getSize(); } /** * 获取栈容量 * @return 栈中元素个数 */ public int getCapacity() { return array.getCapacity(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public void push(E e) { array.addLast(e); } @Override public E pop() { return array.removeLast(); } @Override public E peek() { return array.getLast(); } /** * 重载Object类的toString()方法 */ @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("Stack: "); stringBuilder.append("["); for(int i = 0; i < array.getSize(); i++) { stringBuilder.append(array.get(i)); if(i != array.getSize() - 1) { stringBuilder.append(", "); } } stringBuilder.append("] top"); return stringBuilder.toString(); } } 

总结：以上是基于我们的数组类实现了栈的相关操作，上面定义了接口，当我们实现了链表时，还可以基于链表来实现自己的Stack。