黑马程序员技术交流社区

标题: java中数据结构之队列的实现。求详细代码 ，有无注释均可 [打印本页]

---

作者: Super_Class    时间: 2013-5-1 01:10
标题: java中数据结构之队列的实现。求详细代码 ，有无注释均可


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

---

作者: Jacky_Chen1990    时间: 2013-5-1 02:56


以下是我以前的学习笔记，代码应该是以前从网上找的，我看过没有问题，希望可以帮助到你。
队列是一种特殊的线性表，它只允许在表的前端(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();
                        }
                }
        }
}

---

作者: Jacky_Chen1990    时间: 2013-5-1 02:59

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();
                }
        }
}

---

作者: Jacky_Chen1990    时间: 2013-5-1 02:59
因为一个帖子的字数有限，分成两贴回答了。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2