A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 Super_Class 于 2013-5-1 17:56 编辑

如题。求详细代码  ,有无注释均可

评分

参与人数 1技术分 +1 收起 理由
黄玉昆 + 1

查看全部评分

3 个回复

倒序浏览
本帖最后由 Jacky_Chen1990 于 2013-5-1 02:59 编辑

以下是我以前的学习笔记,代码应该是以前从网上找的,我看过没有问题,希望可以帮助到你。
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作。
1.队列的顺序存储结构及实现
public class SequenceQueue<T>
{
        private int DEFAULT_SIZE = 10;
        //保存数组的长度。
        private int capacity;
        //定义一个数组用于保存顺序队列的元素
        private Object[] elementData;
        //保存顺序队列中元素的当前个数
        private int front = 0;
        private int rear = 0;
        //以默认数组长度创建空顺序队列
        public SequenceQueue()
        {
                capacity = DEFAULT_SIZE;
                elementData = new Object[capacity];
        }
        //以一个初始化元素来创建顺序队列
        public SequenceQueue(T element)
        {
                this();
                elementData[0] = element;
                rear++;
        }
        /**
         * 以指定长度的数组来创建顺序队列
         * @param element 指定顺序队列中第一个元素
         * @param initSize 指定顺序队列底层数组的长度
         */
        public SequenceQueue(T element , int initSize)
        {
                this.capacity = initSize;
                elementData = new Object[capacity];
                elementData[0] = element;
                rear++;
        }
        //获取顺序队列的大小
        public int length()
        {
                return rear - front;
        }
        //插入队列
        public void add(T element)
        {
                if (rear > capacity - 1)
                {
                        throw new IndexOutOfBoundsException("队列已满的异常");
                }
                elementData[rear++] = element;
        }
        //移除队列
    public T remove()
        {
                if (empty())
                {
                        throw new IndexOutOfBoundsException("空队列异常");
                }
                //保留队列的rear端的元素的值
                T oldValue = (T)elementData[front];
                //释放队列的rear端的元素
                elementData[front++] = null;
                return oldValue;
        }
        //返回队列顶元素,但不删除队列顶元素
    public T element()
        {
                if (empty())
                {
                        throw new IndexOutOfBoundsException("空队列异常");
                }
                return (T)elementData[front];
        }
        //判断顺序队列是否为空队列
        public boolean empty()
        {
                return rear == front;
        }
        //清空顺序队列
        public void clear()
        {
                //将底层数组所有元素赋为null
                Arrays.fill(elementData , null);
                front = 0;
                rear = 0;
        }
        public String toString()
        {
                if (empty())
                {
                        return "[]";
                }
                else
                {
                        StringBuilder sb = new StringBuilder("[");
                        for (int i = front  ; i < rear ; i++ )
                        {
                                sb.append(elementData.toString() + ", ");
                        }
                        int len = sb.length();
                        return sb.delete(len - 2 , len).append("]").toString();
                }
        }
}

2.循环队列(顺序结构存储实现)
import java.util.Arrays;
public class LoopQueue<T>
{
        private int DEFAULT_SIZE = 10;
        //保存数组的长度。
        private int capacity;
        //定义一个数组用于保存循环队列的元素
        private Object[] elementData;
        //保存循环队列中元素的当前个数
        private int front = 0;
        private int rear = 0;
        //以默认数组长度创建空循环队列
        public LoopQueue()
        {
                capacity = DEFAULT_SIZE;
                elementData = new Object[capacity];
        }
        //以一个初始化元素来创建循环队列
        public LoopQueue(T element)
        {
                this();
                elementData[0] = element;
                rear++;
        }
        /**
         * 以指定长度的数组来创建循环队列
         * @param element 指定循环队列中第一个元素
         * @param initSize 指定循环队列底层数组的长度
         */
        public LoopQueue(T element , int initSize)
        {
                this.capacity = initSize;
                elementData = new Object[capacity];
                elementData[0] = element;
                rear++;
        }
        //获取循环队列的大小
        public int length()
        {
                if (empty())
                {
                        return 0;
                }
                return rear > front ? rear - front
                        : capacity - (front - rear);
        }
        //插入队列
        public void add(T element)
        {
                if (rear == front
                        && elementData[front] != null)
                {
                        throw new IndexOutOfBoundsException("队列已满的异常");
                }
                elementData[rear++] = element;
                //如果rear已经到头,那就转头
                rear = rear == capacity ? 0 : rear;
        }
        //移除队列
        public T remove()
        {
                if (empty())
                {
                        throw new IndexOutOfBoundsException("空队列异常");
                }
                //保留队列的rear端的元素的值
                T oldValue = (T)elementData[front];
                //释放队列的rear端的元素
                elementData[front++] = null;
                //如果front已经到头,那就转头
                front = front == capacity ? 0 : front;
                return oldValue;
        }
        //返回队列顶元素,但不删除队列顶元素
        public T element()
        {
                if (empty())
                {
                        throw new IndexOutOfBoundsException("空队列异常");
                }
                return (T)elementData[front];
        }
        //判断循环队列是否为空队列
        public boolean empty()
        {
                //rear==front且rear处的元素为null
                return rear == front
                        && elementData[rear] == null;
        }
        //清空循环队列
        public void clear()
        {
                //将底层数组所有元素赋为null
                Arrays.fill(elementData , null);
                front = 0;
                rear = 0;
        }
        public String toString()
        {
                if (empty())
                {
                        return "[]";
                }
                else
                {
                        //如果front < rear,有效元素就是front到rear之间的元素
                        if (front < rear)
                        {
                                StringBuilder sb = new StringBuilder("[");
                                for (int i = front  ; i < rear ; i++ )
                                {
                                       sb.append(elementData.toString() + ", ");
                                }
                                int len = sb.length();
                                return sb.delete(len - 2 , len).append("]").toString();
                        }
                        //如果front >= rear,有效元素为front->capacity之间、0->front之间的
                        else
                        {
                                StringBuilder sb = new StringBuilder("[");
                                for (int i = front  ; i < capacity ; i++ )
                                {
                                        sb.append(elementData.toString() + ", ");
                                }
                                for (int i = 0 ; i < rear ; i++)
                                {
                                        sb.append(elementData.toString() + ", ");
                                }
                                int len = sb.length();
                                return sb.delete(len - 2 , len).append("]").toString();
                        }
                }
        }
}




回复 使用道具 举报

3.队列的链式存储结构及实现

public class LinkQueue<T>
{
        //定义一个内部类Node,Node实例代表链队列的节点。
        private class Node
        {
                //保存节点的数据
                private T data;
                //指向下个节点的引用
                private Node next;
                //无参数的构造器
                public Node()
                {
                }
                //初始化全部属性的构造器
                public Node(T data ,  Node next)
                {
                        this.data = data;
                        this.next = next;
                }
        }
        //保存该链队列的头节点
        private Node front;
        //保存该链队列的尾节点
        private Node rear;
        //保存该链队列中已包含的节点数
        private int size;
        //创建空链队列
        public LinkQueue()
        {
                //空链队列,front和rear都是null
                front = null;
                rear = null;
        }
        //以指定数据元素来创建链队列,该链队列只有一个元素
        public LinkQueue(T element)
        {
                front = new Node(element , null);
                //只有一个节点,front、rear都指向该节点
                rear = front;
                size++;
        }
        //返回链队列的长度        
        public int length()
        {
                return size;
        }
        //将新元素加入队列
        public void add(T element)
        {
                //如果该链队列还是空链队列
                if (front == null)
                {
                        front = new Node(element , null);
                        //只有一个节点,front、rear都指向该节点
                        rear = front;
                }
                else
                {
                        //创建新节点
                        Node newNode = new Node(element , null);
                        //让尾节点的next指向新增的节点
                        rear.next = newNode;
                        //以新节点作为新的尾节点
                        rear = newNode;
                }
                size++;
        }
        //删除队列front端的元素
        public T remove()
        {
                Node oldFront = front;
                front = front.next;
                oldFront.next = null;
                size--;
                return oldFront.data;
        }
        //访问链式队列中最后一个元素
        public T element()
        {
                return rear.data;
        }
        //判断链式队列是否为空队列
        public boolean empty()
        {
                return size == 0;
        }
        //清空链队列
        public void clear()
        {
                //将front、rear两个节点赋为null
                front = null;
                rear = null;
                size = 0;
        }
        public String toString()
        {
                //链队列为空链队列时
                if (empty())
                {
                        return "[]";
                }
                else
                {
                        StringBuilder sb = new StringBuilder("[");
                        for (Node current = front ; current != null
                                ; current = current.next )
                        {
                                sb.append(current.data.toString() + ", ");
                        }
                        int len = sb.length();
                        return sb.delete(len - 2 , len).append("]").toString();
                }
        }
}

评分

参与人数 1技术分 +2 收起 理由
黄玉昆 + 2 真详细

查看全部评分

回复 使用道具 举报
因为一个帖子的字数有限,分成两贴回答了。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马