【栈和队列】2、栈的基本实现

简单记录 - bobo老师的玩转算法系列–玩转数据结构 - 栈和队列

栈的实现

Stack<E>

void push(E)
E pop()
E peek()
int getSize()
boolean isEmpty()

push 入栈 pop 出栈 peek(top) 看栈顶元素

getSize()看栈一共元素 isEmpty()是否为空

从用户的角度看，支持这些操作就好

具体底层实现，用户不关心

实际底层有多种实现方式

我们开发者要深入理解、实现

ArrayStack<E> implementInterface Stack<E>

void push(E)
E pop()
E peek()
int getSize()
boolean isEmpty()

ArrayStack实现了Stack接口

实践栈的实现

Array

public class Array<E> {

    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;

    }

}

Stack interface

public interface Stack<E> {

    int getSize();

    boolean isEmpty();

    void push(E e);

    E pop();

    E peek();

}

ArrayStack<E> implementInterface Stack<E>

public class ArrayStack<E> implements Stack<E> {

    private Array<E> 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();

    }

}

Main

public class Main {

    public static void main(String[] args) {

        ArrayStack<Integer> stack = new ArrayStack<>();

        for(int i = 0 ; i < 6 ; i ++){

            stack.push(i);

            System.out.println(stack);

        }

        System.out.println("isEmpty：" + stack.isEmpty());

        System.out.println("Size:" + stack.getSize());

        for(int i = 0 ; i < 6 ; i ++){

            stack.pop();

            System.out.println(stack);

        }

        System.out.println("isEmpty：" + stack.isEmpty());

    }

}

Result

D:\Environments\jdk-11.0.2\bin\java.exe -javaagent:D:\Java\ideaIU-2019.2.win\lib\idea_rt.jar=4439:D:\Java\ideaIU-2019.2.win\bin -Dfile.encoding=UTF-8 -classpath D:\IdeaProjects\imooc\Play-with-Data-Structures\03-Stacks-and-Queues\02-Array-Stack\target\classes Main

Stack: [0] top

Stack: [0, 1] top

Stack: [0, 1, 2] top

Stack: [0, 1, 2, 3] top

Stack: [0, 1, 2, 3, 4] top

Stack: [0, 1, 2, 3, 4, 5] top

isEmpty：false

Size:6

Stack: [0, 1, 2, 3, 4] top

Stack: [0, 1, 2, 3] top

Stack: [0, 1, 2] top

Stack: [0, 1] top

Stack: [0] top

Stack: [] top

isEmpty：true

Process finished with exit code 0

栈的复杂度分析

ArrayStack<E>

void push(E) O(1) 均摊
E pop() O(1) 均摊
E peek() O(1)
int getSize() O(1)
boolean isEmpty() O(1)

巴特西

【栈和队列】2、栈的基本实现 - Java

最新文章

热门文章