手机版
你好,游客 登录 注册
背景:
阅读新闻

使用Java数组实现顺序栈

[日期:2015-05-20] 来源:Linux社区  作者:hapjin [字体: ]

1,首先总结一下线性表(分为顺序表和链接表,【即顺序存储结构和链式存储结构的区别】)和栈(顺序栈和链接栈)还有队列(顺序队列和链接队列)的Java类库中的实现:

java.util.ArrayList 实现了顺序表,java.util.LinkedList 实现了链接表的功能。

java.util.ArrayDeque实现了顺序栈和顺序队列(该类中即定义了与栈操作有关的方法,也定义了与队列操作有关的方法)、java.util.LinkedList实现了链接栈和链接队列。

2,定义了一个Stack<E>接口,指明该栈实现了哪些具体的操作。接口如下:

public interface Stack<E> {
    public int length();//返回栈的长度
   
    public E pop();//出栈
   
    public void push(E element);//进栈
   
    public E peek();//访问栈顶元素
   
    public boolean empty();//判断栈是否为空
   
    public void clear();//清空栈
}

3,在JAVA类库中,java.util.ArrayDeque类实现了顺序栈的功能。ArrayDeque可以实现动态地扩展栈的大小,但是不支持多线程访问。同时,ArrayDeque还实现了顺序队列的功能。

4,定义了一个Object[] 类型的数组,用来保存顺序栈中的元素。具体实现类SequenceStack.java 如下:

import java.util.Arrays;

public class SequenceStack<E> implements Stack<E> {
   
    private int DEFAULT_SIZE = 16;//定义栈的初始默认长度
    private int capacity;//保存顺序栈的长度
    private int size;//保存顺序栈中元素的个数
    private Object[] elementData;//定义一个数组用于保存顺序栈中的元素
   
    public SequenceStack() {
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
   
    //以指定的大小来创建栈
    public SequenceStack(int initSize){
        capacity = 1;
        while(capacity < initSize)
            capacity <<= 1;//将capacity设置成大于initSize的最小2次方
        elementData = new Object[capacity];
    }

    //返回当前顺序栈中元素的个数
    public int length() {
        return size;
    }

    public E pop() {
        if(empty())
            throw new IndexOutOfBoundsException("栈空,不能出栈");
        E oldValue = (E)elementData[size - 1];
        elementData[--size] = null;//让垃圾回收器及时回收,避免内存泄露
        return oldValue;
    }

    public void push(E element) {
        ensureCapacity(size + 1);
        elementData[size++] = element;
    }
   
    private void ensureCapacity(int minCapacity){
        if(minCapacity > capacity){
            while(capacity < minCapacity)
                capacity <<= 1;
        elementData = Arrays.copyOf(elementData, capacity);
        }
    }

    //获取栈顶元素,不会将栈顶元素删除
    public E peek() {
        if(size == 0)
            throw new ArrayIndexOutOfBoundsException("栈为空");
        return (E)elementData[size - 1];
    }

    public boolean empty() {
        return size == 0;
    }

    public void clear() {
//        Arrays.fill(elementData, null);
        for(int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    public String toString(){
        if(size == 0)
            return "[]";
        else{
            StringBuilder sb = new StringBuilder("[");
            for(int i = size - 1; i >= 0; i--)
                sb.append(elementData[i].toString() + ", ");
            int len = sb.length();
            //删除由于上面for循环中最后添加的多余的两个字符 (一个是逗号,一个是空格符号)
            return sb.delete(len - 2, len).append("]").toString();
        }
    }
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2015-05/117754.htm

linux
相关资讯       Java数组  Java栈实现 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款