首页 > > 程序设计 > Java技术 >

用顺序映像实现栈

2019-03-11 09:44:32来源：博客园阅读 ()

(一).栈的理解　

　　（1）概述：只在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，我们称之为栈顶(top),表头我们称之为栈底(bottom)。不含元素的空表称之为空栈.

　　（2）栈的顺序映像：植栈中元素实际在数组中存储，其线性关系，与普通线性表相同，通过元素紧邻来表示。

　　　　a.入栈：

　　　　　　这里要注意的只有一点，就是数组容量的问题，在元素入栈的时候，要保证数组中有位置来容纳，带入栈的元素

　　　　b.出栈：

　　　　　　这里要注意的也只有一点就是，此时，栈是否为空栈，如果是空栈，就无法出栈。

（二）代码实现

　　（1）首先定义一个Stack接口

public interface Stack<T> {
    //返回栈的长度
    public int length();

    //入栈
    public void push(T elment);

    //出栈
    public  T pop();

    //取栈顶
    public T peek();

    //判断栈空
    public  boolean isEmpty();

    //清空栈
    public void clear();
}

（2）然后定义一个SequeceStack类实现Stack接口

public class SequeceStack<T> implements Stack<T> {
    private int DEFAULT_SIZE = 3;//定义栈默认初始长度
    private int capacity;//顺序栈的容量
    private int size ;//顺序栈中元素个数
    private static String[] elements;//定义一个数组用于保存顺序栈中的元素

    public SequeceStack() {
        capacity = DEFAULT_SIZE;
        elements = new String[capacity];
    }

    /**
     * 以指定的容量来初始化栈
     * @param initsize 指定的容量
     */
    public SequeceStack(int initsize) {
        if(initsize < 0 || initsize > Integer.MAX_VALUE-8){
            throw new OutofSizeException("容量不合法");
        }
        else{
            int capacity = 1;
            while ( capacity < initsize){
                capacity <<= 1;
            }
            elements = new String[capacity];
            this.capacity = capacity;//caution扩容的关键
        }

    }

    ///////////////////// 下面是栈的各项功能 /////////////////////
    /**
     * 获取栈中元素个数
     * @return 获取的元素个数
     */
    @Override
    public int length() {
        return size;
    }

    /**
     * 入栈
     * @param s 要入栈的元素
     */
    @Override
    public void push(T s) {
        //判断是否需要扩容
        ensureCapacity(size + 1);
        elements[size++] = (String) s;
    }

    private void ensureCapacity(int minCapacity) {
        //是否需要扩容
        if(minCapacity > capacity){
            //需要扩容
            while (minCapacity < capacity){
                minCapacity <<= 1;
            }
            //将旧数组的所有元素拷贝到扩容后的新数组
            elements = Arrays.copyOf(elements,minCapacity);
        }
    }

    /**
     * 出栈
     * @return 出栈的那个元素
     */
    @Override
    public T pop() {
        if(isEmpty()){
            throw new ArrayIndexOutOfBoundsException("栈为空");
        }else {
            T oldValue = (T) elements[size - 1];
            elements[--size] = null;
        return oldValue;
        }
    }

    /**
     * 获取栈顶元素
     * @return 获取到的栈顶元素
     */
    @Override
    public T peek() {
        if(size == 0){
            throw new ArrayIndexOutOfBoundsException("这是个空栈");
        }
        return (T) elements[size - 1];
    }

    /**
     * 判断栈是否为空
     * @return 如果栈为空，返回ture，否则返回false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空栈
     */
    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 打印栈所有元素
     * @return 打印的内容
     */
    @Override
    public String toString() {
        if(size == 0){
            return "[]";
        }else {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(elements[i] + ", ");
            }
            int len = sb.length();
            return sb.delete(len - 2,len).append("]").toString();
        }
    }
}

（3）最后定义一个测试类

public class SequenceStackTest {
    public static void main(String[] args) {
        SequeceStack ss = new SequeceStack();
        System.out.println("-------------初始化一个空栈-------------");
        System.out.println("栈空：" + ss.isEmpty());
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());

        System.out.println("-------------存储三个元素后-------------");
        ss.push("hello");
        ss.push("world");
        ss.push("java");
        System.out.println("栈空:" + ss.isEmpty());
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());

        System.out.println("-----------获取栈顶元素，但不删除栈顶元素-----------");
        System.out.println("获取到的栈顶元素为：" + ss.peek());
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());

        System.out.println("-------------将栈顶元素出栈----------------");
        System.out.println("栈顶出栈的元素为：" +ss.pop());
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());

        System.out.println("-------------清空栈---------------");
        ss.clear();
        System.out.println("栈空:" + ss.isEmpty());
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());

        System.out.println("-------------当存储元素个数大于4个元素时，需要扩容-------------");
        ss.push("hello");
        ss.push("world");
        ss.push("java");
        ss.push("chongqing");
        System.out.println("打印栈：" + ss.toString());
        System.out.println("栈中元素个数：" + ss.length());
    }
}

（4）当然，这里我自己自定义了一个异常

public class OutofSizeException extends RuntimeException {
    public OutofSizeException() {
    }

    public OutofSizeException(String message) {
        super(message);
    }
}