数据结构笔记总结(2.2)栈的基本实现

栈的实现

栈是一种非常有用又非常简单的数据结构,在这里我们将设计五个操作。

分别是:向栈中添加一个元素,也就是入栈,通常叫push();

从栈中拿出一个元素,也叫作出栈,通常叫做pop();

查看栈顶的元素是谁,这个动作通常叫做peek(),有的语言中也叫top();

另外还有两个基本操作,看栈里一共有多少个元素getSize();

判断一下栈是否为空isEmpty();

从用户的角度来看,支持这些操作就好,但是对于具体的底层实现,用户并不关心,实际上底层有多种实现方式。

为了使我们整个程序的逻辑结构更加清晰,同时也是为了支持面向对象的一些特性,如多态性。

代码设计上我们采用这样一种方式,设置一个叫Stack的接口,在这个接口中定义了这五种操作,这也是我们在java中常用的设计方式。

这一小节中我们将基于我们在上一章讲的动态数组来实现一个栈,取名叫ArrayStack

实际上它实现了Stack这个接口,在此基础上,它具体的完成这些操作所对应的逻辑。

代码演示

首先我们新建一个接口叫做Stack,并且是支持泛型的,然后定义上述的方法。

public interface Stack {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

接口定义好之后,我们就可以创建一个新的类,叫做ArrayStack。

首先它也是支持泛型的,其次它也要实现刚刚创建的Stack接口。

成员变量Array为我们上一章创建的,然后我们设计两个构造函数,思路和上一章一样。

第一个传来一个容积capacity,前提我们知道元素个数,如果我们不知道最终承载元素个数,再设计一个无参构造。

下面我们就可以实现接口的方法了。

public class ArrayStack implements Stack {

    private Array array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }

    @Override
    public E pop(){
        return array.removeLast();
    }

    @Override
    public E peek(){
        return array.getLast();
    }

    @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();
    }
}

我们再完善一下之前写的array类,增加getLast和getFirst方法来取出数组中最后一个和第一个元素。


public class Array {

    private E[] data;
    private int size;

    // 构造函数,传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数,默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        if(size == data.length)
            resize(2 * data.length);

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    public E getLast(){
        return get(size - 1);
    }

    public E getFirst(){
        return get(0);
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i = 0 ; i < size ; i ++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

    // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }
}

接下来我们来简单测试一下

public class Main {

    public static void main(String[] args) {

        ArrayStack stack = new ArrayStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

运行上面的程序,仔细观察并分析结果

首先,从0,1,2,3,4这五个数字依次入栈,入栈之后有一次出栈操作,会将栈顶的4拿出栈,最后这个栈就变成了0,1,2,3。

栈的复杂度分析

最后我们来看一下所有操作的的时间复杂度

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(2.2)栈的基本实现

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多