栈实现之顺序栈——MyArrayStack

2019-11-06 07:00:06

字体：大中小

来源：转载

供稿：网友

到现在为止，我们已经实现了两种不同存储方式的线性表：顺序表MyArrayList和双向链表MyLinkedList。今天我们要实现另一种非常流行的线性数据结构——栈。

栈(Stack)实际上是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶(top)。栈是一种典型的后进先出(LIFO)型线性表，如下图所示：

这里写图片描述

最早进入的元素6最晚才能出去，而最后进入的元素2可以最早出去，这就是后进先出。

和线性表类似，实现栈也同样可以利用两种存储方式。如利用数组作为底层容器，来存储元素，则被称为顺序栈；使用链式存储方式实现的栈则被称为链栈。

那么我们就来分析一下，如何实现顺序存储结构的顺序栈——MyArrayStack。

MyArrayStack：

MyArrayStack需要装载各种类型的元素，因此需要支持泛型。MyArrayStack底层使用数组来存储元素，可以方便地进行压栈、弹出等操作。

MyArrayStack应当提供以下操作方法：

peek() //获取栈顶的元素(不删除该元素)push(E element) //将元素压入栈顶pop() //弹出栈顶的元素(从数组中删除该元素)contains(E element) //检查列表中是否存在指定元素size() //返回列表中元素的个数clear() //清空列表中所有的元素isEmpty() //检查列表是否为空

那么我们现在就来一起实现MyArrayStack这个数据结构吧

public class MyArrayStack<E>{ //在声明MyArrayList时，如不指明大小，则初始大小为10 PRivate static final int DEFAULT_CAPACITY = 10; private E[] contents; private int size = 0; //两种构造函数，允许用户创建指定大小或者默认大小的线性表 public MyArrayStack(){ init(DEFAULT_CAPACITY); } public MyArrayStack(int initCapacity){ init(initCapacity); } //私有化方法init帮助构造函数来初始化数组contents private void init(int capacity){ //注意不能建立泛型数组，因此我们强行转换一个Object数组 if(capacity<=0) throw new IndexOutOfBoundsException(); contents = (E[]) new Object[capacity]; }

接下来我们提供几个简单的获取元素数量、查看是否为空的方法

public int size(){ return this.size; } public boolean isEmpty(){ return size()==0; } //这里i从1开始取值，因为我们存储序号以1为基数 public void clear(){ for(int i=1;i<=size();i++){ //将数组中元素的引用指向null，这样GC就可以回收内存 contents[i] = null; } this.size = 0; }

下面是将元素压入栈中的压栈方法实现

public boolean push(E element){ if(size()>=contents.length-1){ //一旦列表中的元素个数等于了数组的长度-1，我们就对数组进行扩容 //因为现在在数组中存放第一个元素的位置是contents[1]而不是contents[0] ensureCapacity(); } //让元素在数组中以基数为1的形式存储 contents[++size] = element; return true; } private void ensureCapacity(){ //此处新数组的容量是旧数组的2倍加1，你可以自己选择扩容的多少 E[] newContents = (E[]) new Object[2*contents.length+1]; //将就数组中的值全部拷于新数组中,让元素在数组中以基数为1的形式存储 System.arraycopy(contents,1,newContents,1,size()); //在让contents指向新的数组 contents = newContents; }

下面是弹出栈顶元素(将该元素从数组中删除)方法的实现

public E pop(){ //取出栈顶上的元素 E topElement = contents[size()]; //帮助GC处理内存 contents[size--] = null; return topElement; }

完成了压栈、弹出方法之后，我们最后实现获取栈顶元素与查看是否存在两个方法

public E peek(){ return contents[size()]; } public boolean contains(E element){ if(element == null){ for(int i=1;i<=size();i++){ if(contents[i] == null) return true; } return false; } else{ for(int i=1;i<=size();i++){ if(element.equals(contents[i])) return true; } return false; } }

到这里我们的Stack数据结构就已经实现完成了，有的朋友可能会问，为什么要专门创造出这样一个只允许在栈顶完成插入删除元素的数据结构呢？

那是因为像压栈、弹出这些操作是以常数时间运行的。对于某些有自增和自减寻址功能的寄存器来说，整数的压栈、弹出功能都可以写成一条机器指令。这也是为什么栈在现代计算机系统中占有着重要的地位。

到这里，我们就已经实现了自己的MyArrayStack数据结构。

本博文源码下载地址，欢迎下载测试。

上一篇：c#总结--面向对象三大特征

下一篇：接口的作用