数据结构与算法(1)：基于数组实现的栈结构Java代码实现

栈的定义：

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行

从影响数据结构的3个要素来分析栈：逻辑结构、存储结构、数据操作。

• 逻辑结构：线性结构
• 存储结构：底层可以是顺序存储，比如基于数组；底层可以是链式存储，比如基于链表。
• 数据操作：栈中对数据的增加删除需要满足先进先出的规则。

底层为数组的栈实现：

本文使用Java语言实现，该实现的栈底层数据结构为数组，支持数组的动态变容。

接口定义

import java.util.Iterator;

/**
 *
 * @Created on 2017-02-15 8:40
 * 栈结构定义，定义了基本的6种操作
 */
public interface FlowerStack<T> {

    /**
     * 压栈
     * @param item
     */
    void push(T item);

    /**
     * 出栈
     * @return
     */
    T pop();

    /**
     * 栈的大小
     * @return
     */
    int size();

    /**
     * 栈是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 生成迭代器
     */
    Iterator<T> iterator();


}

实现类代码：

import java.util.Iterator;

/**
 * @Created on 2017-02-15 8:23
 * 自定义栈 该类采用顺序栈的方式
 * 要求可以自动扩容、缩小
 */
public class FlowerArrayStack<T> implements FlowerStack<T> {

    // 持有一个数组
    private T[] arr = (T[]) new Object[1];
    private int length = 0;


    public FlowerArrayStack() {
        // 初始化
    }

    public void push(T item) {

        // length 指针上移

        if (length == arr.length) {
            resize(arr.length * 2);
        }

        arr[length++] = item;
    }

    @Override
    public T pop() {
        // 返回最顶部的
        if (length == 0) {
            return null;
        }
        T result = arr[--length];
        arr[length] = null;
        // 注意缩小容量
        if (length > 0 && length == arr.length / 4) {
            resize(arr.length / 2);
        }
        return result;
    }

    private void resize(int max) {
        T[] temp = (T[]) new Object[max];
        for(int i=0; i<length; i++) {
            temp[i] = arr[i];
        }
        this.arr = temp;
    }

    @Override
    public int size() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        return this.length == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new FlowerArrayStackIterator();
    }

    public int getCapacity() {
        return arr.length;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

   class FlowerArrayStackIterator implements Iterator<T> {

       int i = length;

       @Override
       public boolean hasNext() {
           return i > 0;
       }

       @Override
       public T next() {
           return arr[--i];
       }

       @Override
       public void remove() {

       }
   }

}

测试用例代码：

import org.junit.Test;

import java.util.Iterator;

/**
 * 
 * @Created on 2017-02-15 14:33
 * FlowerArrayStack 测试类
 */
public class FlowerArrayStackTest {

    @Test
    public void test() {
        FlowerArrayStack<Integer> stack = new FlowerArrayStack<Integer>();
        for(int i=0; i<500; i++) {
            stack.push(i);
        }

        Iterator<Integer> it = stack.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        for(int i=0; i<1000; i++) {
            stack.pop();
        }

    }

}