队列的链式实现和循环数组实现-----------------------------java语言描述

朱雀 2022-05-16 00:28 199阅读 0赞

Java有经典的**链式队列，循环队列**，也有高级应用常使用的**双向队列，优先队列**。本文从低级实现介绍到java类库中的相关队列。

# 队列的接口 #

如下所示：

public interface QueueInterface <T>{ //所有队列的实现必须实现这个接口
        public void enqueue(T newEntry);
        
        public T dequeue();
        
        public T getFront();
        
        public boolean isEmpty();
        
        public void clear();
    }

# 链式队列 #

首先，写一个LinkedQueue，实现QueueInterface接口.

/** 
     * Description: 链式结构实现队列
     *
     * @ClassName: LinkedQueue
     * @author 过道
     * @date 2018年8月13日 下午3:18:18 
     */
    public class LinkedQueue<T> implements QueueInterface<T>{
    
        /**
         * Title: enqueue 
         *
         * Description: 队列尾部新增元素 newEntry
         */
        @Override
        public void enqueue(T newEntry) {
            // TODO Auto-generated method stub
            
        }
    
        /**
         * Title: dequeue 
         *
         * Description: 队列头部删除元素
         */
        @Override
        public T dequeue() {
            // TODO Auto-generated method stub
            return null;
        }
    
        /**
         * Title: getFront 
         *
         * Description: 得到头部元素，同peek()
         */
        @Override
        public T getFront() {
            // TODO Auto-generated method stub
            return null;
        }
    
        /**
         * Title: isEmpty 
         *
         * Description: 判断队列是否为空
         */
        @Override
        public boolean isEmpty() {
            // TODO Auto-generated method stub
            return false;
        }
    
        /**
         * Title: clear 
         *
         * Description: 清空队列
         */
        @Override
        public void clear() {
            // TODO Auto-generated method stub
            
        }
    
    }

## 内部类Node ##

我决定从底层一步一步实现链式队列，因此，我需要自己定义一个内部类Node，用来实现链结点。代码如下

class Node<T> {
            private T data;
            private Node<T> next;
            public Node() {
                super();
            }
            public Node(T newEntry) {
               this(newEntry,null);
            }
            public Node(T data, Node next) {
                super();
                this.data = data;
                this.next = next;
            }
            // getter,setter方法
        }

## 链式队列的字段和构造器。 ##

我们先考虑链式队列需要的节点数，很明显，我们需要一个指向头结点的引用，便于我们删除队列头的元素，也需要一个指向尾结点的引用，便于我们新增元素。于是我们添加以下代码进入LinkedQueue中。

//字段，因为要保留内部实现权利，所以不准提供getter和setter
        private Node<T> first;
        private Node<T> last;
    
        // 构造方法，在其中初始化指向首尾结点的引用.
        public LinkedQueue() {
            first = null;
            last = null;
        }

## 所有方法的实现 ##

/**
         * Title: enqueue
         *
         * Description: 队列尾部新增元素 newEntry
         */
        @Override
        public void enqueue(T newEntry) {
            Node newNode = new Node<T>(newEntry);
            if (isEmpty()) { // 队列为空时
                first = newNode;
            } else {
                last.setNext(newNode); // 不为空时，我们将其与尾结点链接
            }
            // 指向尾结点的引用后移.
            last = newNode;
        }
    
        /**
         * Title: dequeue
         *
         * Description: 队列头部删除元素
         */
        @Override
        public T dequeue() {
            if (isEmpty()) {
                // 抛出异常，或者其他逻辑,我这里只是一个打印。
                System.err.println("dequeue() ---> isEmpty()  异常");
                return null;
            }
            T front = first.getData();
            first.setData(null);
            first = first.getNext();
            if (first == null) {
                last = null;
            }
            return front;
        }
    
        /**
         * Title: getFront
         *
         * Description: 得到头部元素，同peek()
         * 
         */
        @Override
        public T getFront() {
            if (isEmpty()) {
                // 抛出异常，或者其他逻辑,我这里只是一个打印。
                System.err.println("getFront() ---> isEmpty()  异常");
                return null;
            }
            return first.getData();
        }
    
        /**
         * Title: isEmpty
         *
         * Description: 判断队列是否为空
         */
        @Override
        public boolean isEmpty() {
            return (first == null) && (last == null);
        }
    
        /**
         * Title: clear
         *
         * Description: 清空队列
         */
        @Override
        public void clear() {
            first = null;
            last = null;
            // GC 会帮我们回收掉内存，我们只需要将这两个引用置为null，GC就明白你不再使用这一整条链了。
        }

## 链式队列的全部源码 ##

/**
     * Description: 链式结构实现队列
     *
     * @ClassName: LinkedQueue
     * @author 过道
     * @date 2018年8月13日 下午3:18:18
     */
    public class LinkedQueue<T> implements QueueInterface<T> {
        // 字段，因为要保留内部实现权利，所以不准提供getter和setter
        private Node<T> first;
        private Node<T> last;
    
        // 构造方法，在其中初始化指向首尾结点的引用.
        public LinkedQueue() {
            first = null;
            last = null;
        }
    
        /**
         * Title: enqueue
         *
         * Description: 队列尾部新增元素 newEntry
         */
        @Override
        public void enqueue(T newEntry) {
            Node newNode = new Node<T>(newEntry);
            if (isEmpty()) { // 队列为空时
                first = newNode;
            } else {
                last.setNext(newNode); // 不为空时，我们将其与尾结点链接
            }
            // 指向尾结点的引用后移.
            last = newNode;
        }
    
        /**
         * Title: dequeue
         *
         * Description: 队列头部删除元素
         */
        @Override
        public T dequeue() {
            if (isEmpty()) {
                // 抛出异常，或者其他逻辑,我这里只是一个打印。
                System.err.println("dequeue() ---> isEmpty()  异常");
                return null;
            }
            T front = first.getData();
            first.setData(null);
            first = first.getNext();
            if (first == null) {
                last = null;
            }
            return front;
        }
    
        /**
         * Title: getFront
         *
         * Description: 得到头部元素，同peek()
         * 
         */
        @Override
        public T getFront() {
            if (isEmpty()) {
                // 抛出异常，或者其他逻辑,我这里只是一个打印。
                System.err.println("getFront() ---> isEmpty()  异常");
                return null;
            }
            return first.getData();
        }
    
        /**
         * Title: isEmpty
         *
         * Description: 判断队列是否为空
         */
        @Override
        public boolean isEmpty() {
            return (first == null) && (last == null);
        }
    
        /**
         * Title: clear
         *
         * Description: 清空队列
         */
        @Override
        public void clear() {
            first = null;
            last = null;
            // GC 会帮我们回收掉内存，我们只需要将这两个引用置为null，GC就明白你不再使用这一整条链了。
        }
    
        /**
         * 
         * Description: 链式实现队列所必须的结点。
         *
         * @ClassName: Node
         */
        class Node<T> {
            private T data;
            private Node<T> next;
            public Node() {
                super();
            }
            public Node(T newEntry) {
                this(newEntry, null);
            }
            public Node(T data, Node next) {
                super();
                this.data = data;
                this.next = next;
            }
            // getter,setter方法
            public T getData() {
                return data;
            }
            public void setData(T data) {
                this.data = data;
            }
            public Node<T> getNext() {
                return next;
            }
            public void setNext(Node<T> next) {
                this.next = next;
            }
        }
    }

# 数组队列、循环队列 #

先写一个ArrayQueue实现QueueInterface接口.

/**
     * Description: 数组实现循环队列。
     *
     * @ClassName: ArrayQueue
     * @author 过道
     * @date 2018年8月13日 下午2:10:13
     */
    public class ArrayQueue<T> implements QueueInterface<T> {
    
        /**
         * Description: enqueue
         */
        @Override
        public void enqueue(T newEntry) {
            // TODO Auto-generated method stub
            
        }
    
        /**
         * Description: dequeue
         */
        @Override
        public T dequeue() {
            // TODO Auto-generated method stub
            return null;
        }
    
        /**
         * Description: getFront
         */
        @Override
        public T getFront() {
            // TODO Auto-generated method stub
            return null;
        }
    
        /**
         * Description: isEmpty
         */
        @Override
        public boolean isEmpty() {
            // TODO Auto-generated method stub
            return false;
        }
    
        /**
         * Description: clear 
         */
        @Override
        public void clear() {
            // TODO Auto-generated method stub
            
        }
    }

数组实现，我们需要添加的字段较多，构造器较为简单,

private T[] queue;
        private int frontIndex; // 队首
        private int lastIndex; // 队尾
        // 如果调用者没有传入容量，则使用默认容量
        private static final int DEFAULT_CAPACIY = 50;
    
        public ArrayQueue(int initCapacity) {
            T[] tempQueue = (T[]) new Object[initCapacity + 1]; // 为了方便起见，a[0]不会使用，所以 +1，保持容量不变。
            frontIndex = 0;
            lastIndex = initCapacity;
        }
    
        // 默认构造器
        public ArrayQueue() {
            this(DEFAULT_CAPACIY);
        }

实现接口中的各个方法

/**
         * Title: enqueue
         *
         * Description: enqueue
         */
        @Override
        public void enqueue(T newEntry) {
            // 确保容量够用s
            ensureCapacity();
            backIndex = (backIndex + 1) % queue.length;
            queue[backIndex] = newEntry;
        }
    
        /**
         * Description:
         *
         * @Title: ensureCapacity void
         */
        private void ensureCapacity() {
            // 如果发现数组容量被使用完，申请一个双倍size的数组进行替换。
            if (frontIndex == (backIndex + 2) % queue.length) {
                T[] oldQueue = queue;
                int oldSize = oldQueue.length;
                int newSize = oldSize * 2;      // 容量翻倍
                
                @SuppressWarnings("unchecked")
                T[] tempQueue = (T[]) new Object[newSize];
                for (int i = 0; i < tempQueue.length; i++) {
                    tempQueue[i] = oldQueue[frontIndex];
                    frontIndex = (frontIndex + 1) % oldSize;
                }
                // 再次初始化首尾
                frontIndex = 0;
                backIndex = oldSize - 1;
            }
        }
    
        /**
         * Title: dequeue
         *
         * Description: 删除头部元素
         */
        @Override
        public T dequeue() {
            if (isEmpty()) {
                // 抛出异常
            }
            T front = queue[frontIndex];
            queue[frontIndex] = null;
            frontIndex = (frontIndex + 1) % queue.length;
            return front;
        }
    
        /**
         * Title: getFront
         *
         * Description: getFront
         */
        @Override
        public T getFront() {
            if (isEmpty()) {
                // 抛出异常，
            }
            return queue[frontIndex];
        }
    
        /**
         * Title: isEmpty
         *
         * Description: isEmpty
         */
        @Override
        public boolean isEmpty() {
            return frontIndex == (backIndex + 1) % queue.length;
        }
    
        /**
         * Title: clear
         *
         * Description: clear
         */
        @Override
        public void clear() {
            while (!isEmpty()) {
                dequeue();
            }
        }

循环数组实现的所有源码

package unit10.queueBlog;
    
    import unit10.queue.QueueInterface;
    
    /**
     * Description: 数组实现循环队列。
     *
     * @ClassName: ArrayQueue
     * @author 过道
     * @date 2018年8月13日 下午2:10:13
     */
    public class ArrayQueue<T> implements QueueInterface<T> {
        private T[] queue;
        private int frontIndex; // 队首
        private int backIndex; // 队尾
        // 如果调用者没有传入容量，则使用默认容量
        private static final int DEFAULT_CAPACIY = 50;
    
        public ArrayQueue(int initCapacity) {
            T[] tempQueue = (T[]) new Object[initCapacity + 1]; // 为了方便识别，保留一个位置不被使用，所以 size +1。
            frontIndex = 0;
            backIndex = initCapacity;
        }
        // 默认构造器
        public ArrayQueue() {
            this(DEFAULT_CAPACIY);
        }
        /**
         * Title: enqueue
         *
         * Description: enqueue
         */
        @Override
        public void enqueue(T newEntry) {
            // 确保容量够用s
            ensureCapacity();
            backIndex = (backIndex + 1) % queue.length;
            queue[backIndex] = newEntry;
        }
        /**
         * Description:
         *
         * @Title: ensureCapacity void
         */
        private void ensureCapacity() {
            // 如果发现数组容量被使用完，申请一个双倍size的数组进行替换。
            if (frontIndex == (backIndex + 2) % queue.length) {
                T[] oldQueue = queue;
                int oldSize = oldQueue.length;
                int newSize = oldSize * 2;      // 容量翻倍
                
                @SuppressWarnings("unchecked")
                T[] tempQueue = (T[]) new Object[newSize];
                for (int i = 0; i < tempQueue.length; i++) {
                    tempQueue[i] = oldQueue[frontIndex];
                    frontIndex = (frontIndex + 1) % oldSize;
                }
                // 再次初始化首尾
                frontIndex = 0;
                backIndex = oldSize - 1;
            }
        }
        /**
         * Title: dequeue
         *
         * Description: 删除头部元素
         */
        @Override
        public T dequeue() {
            if (isEmpty()) {
                // 抛出异常
            }
            T front = queue[frontIndex];
            queue[frontIndex] = null;
            frontIndex = (frontIndex + 1) % queue.length;
            return front;
        }
        /**
         * Title: getFront
         *
         * Description: getFront
         */
        @Override
        public T getFront() {
            if (isEmpty()) {
                // 抛出异常，
            }
            return queue[frontIndex];
        }
        /**
         * Title: isEmpty
         *
         * Description: isEmpty
         */
        @Override
        public boolean isEmpty() {
            return frontIndex == (backIndex + 1) % queue.length;
        }
        /**
         * Title: clear
         *
         * Description: clear
         */
        @Override
        public void clear() {
            while (!isEmpty()) {
                dequeue();
            }
        }
    }

使用java 自身的类库实现队列的集中方式.

使用linkedList实现Queue(),

public class LinkedQueue<T> implements QueueInterface<T> {
        private LinkedList<T> list;
    
        public LinkedQueue() {
            list = new LinkedList<T>();
        }
    
        @Override
        public void enqueue(T newEntry) {
            list.addLast(newEntry);
        }
    
        @Override
        public T dequeue() {
            // 移除首位
            return list.removeFirst();
        }
    
        @Override
        public T getFront() {
            return list.getFirst();
        }
    
        @Override
        public boolean isEmpty() {
            // 或者 list.size() == 0
            return list.isEmpty();
        }
    
        @Override
        public void clear() {
            while (!isEmpty()) {
                list.remove();
            }
        }
    
    }

Java类库：类AbstractQueue

Java 类库的标准包java.util含有抽象类AbstractQueue.这个类实现了接口java.util,Queue,且不允许队列中含有null值。

这里只是将java源码删除注释后搬运过来，方便查看它拥有的方法.

public abstract class AbstractQueue<E> extends AbstractCollection<E>
        implements Queue<E> {
    
        protected AbstractQueue() {
        }
    
        public boolean add(E e) {
            if (offer(e))
                return true;
            else
                throw new IllegalStateException("Queue full");
        }
    
        public E remove() {
            E x = poll();
            if (x != null)
                return x;
            else
                throw new NoSuchElementException();
        }
    
    
        public E element() {
            E x = peek();
            if (x != null)
                return x;
            else
                throw new NoSuchElementException();
        }
        public void clear() {
            while (poll() != null)
                ;
        }
        public boolean addAll(Collection<? extends E> c) {
            if (c == null)
                throw new NullPointerException();
            if (c == this)
                throw new IllegalArgumentException();
            boolean modified = false;
            for (E e : c)
                if (add(e))
                    modified = true;
            return modified;
        }
    //以下为父类继承出来的方法，搬运到一起方便学习
        public boolean isEmpty() {
            return size() == 0;
        }
        public boolean contains(Object o) {
            Iterator<E> it = iterator();
            if (o==null) {
                while (it.hasNext())
                    if (it.next()==null)
                        return true;
            } else {
                while (it.hasNext())
                    if (o.equals(it.next()))
                        return true;
            }
            return false;
        } 
        public Object[] toArray() {
            // Estimate size of array; be prepared to see more or fewer elements
            Object[] r = new Object[size()];
            Iterator<E> it = iterator();
            for (int i = 0; i < r.length; i++) {
                if (! it.hasNext()) // fewer elements than expected
                    return Arrays.copyOf(r, i);
                r[i] = it.next();
            }
            return it.hasNext() ? finishToArray(r, it) : r;
        }
    }