程序员:数据结构与算法,顺序栈简介

Bonbonwen 2019-12-18

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

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

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

}

}

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

相关推荐