数据结构学习笔记-队列（JAVA）

概念：队列是一种运算受限的线性表，它先进先出
队列的操作有：
构造队列、销毁队列、清空队列、计算队列长度、取队头元素、元素入队和元素出对
代码：
package com.alg.queue;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
//用数组实现队列
//队列是一种运算受限的线性表，它先进先出
//队列的操作有：构造队列、销毁队列、清空队列、计算队列长度、取队头元素、元素入队和元素出对
//Iterable为对for循环的支持
public class Queue<T> implements Iterable<T>
{
    protected Object[] elementData = null;
    // 默认数组大小
    private static final int DEFAULT_SIZE = 10;
    // 数组的每次增长幅度
    protected int capacityIncrement;
    // 操作数
    private int modCount;
    // 统计数组内保存的元素数量
    private int elementCount;
    public Queue()
    {
        this(DEFAULT_SIZE, 0);
    }
    public Queue(int capacity)
    {
        this(capacity, 0);
    }
    public Queue(int capacity, int capacityIncrment)
    {
        elementData = newElementArray(capacity);
        elementCount = 0;
        this.capacityIncrement = capacityIncrment;
    }
    // 清空队
    public void clear()
    {
        for (int i = 0; i < elementCount; i++)
        {
            elementData[i] = null;
        }
        modCount++;
        elementCount = 0;
    }
    // 取队头元素
    @SuppressWarnings("unchecked")
    public T peek()
    {
        T t = null;
        if (elementCount > 0)
        {
            t = (T) elementData[0];
        }
        return t;
    }
    // 出队
    @SuppressWarnings("unchecked")
    public T dequeue()
    {
        T t = null;
        if (elementCount > 0)
        {
            t = (T) elementData[0];
            System.arraycopy(elementData, 1, elementData, 0, --elementCount);
            modCount++;
        }
        return t;
    }
    // 入队
    public void enqueue(T object)
    {
        // 栈满，增加栈容量
        if (elementCount == elementData.length)
        {
            growByOne();
        }
        elementData[elementCount++] = object;
        modCount++;
    }
    @SuppressWarnings( {"unused", "unchecked"})
    private T[] newElementArray(int size)
    {
        return (T[]) new Object[size];
    } // 如果从节省空间角度考虑capacityIncrement最好设置
    private void growByOne()
    {
        int adding = 0;
        // 没有设置增量的情况
        if (capacityIncrement <= 0)
        { // 如果elementData长度为0，就加1，否则就增加elementData.length的一倍
            if ((adding = elementData.length) == 0)
            {
                adding = 1;
            }
        }
        else
        {
            adding = capacityIncrement;
        }
        T[] newData = newElementArray(elementData.length + adding);
        System.arraycopy(elementData, 0, newData, 0, elementCount);
        elementData = newData;
    }
    @SuppressWarnings("unchecked")
    public synchronized T remove(int location)
    {
        if (location < elementCount)
        {
            T result = (T) elementData[location];
            elementCount--;
            int size = elementCount - location;
            // 把location + 1到最后整个拷贝到从location开始到最后
            if (size > 0)
            {
                System.arraycopy(elementData, location + 1, elementData, location, size);
            }
            // 因为中间的某个删除的位置被覆盖，所以需要把最后一位直空
            elementData[elementCount] = null;
            modCount++;
            return result;
        }
        throw new ArrayIndexOutOfBoundsException(location);
    }
    // 增加了对for循环的支持
    public Iterator<T> iterator()
    {
        return new SimpleIterator();
    }
    @SuppressWarnings("unchecked")
    public synchronized T elementAt(int location)
    {
        if (location < elementCount)
        {
            return (T) elementData[location];
        }
        throw new ArrayIndexOutOfBoundsException(location);
    }
    public int size()
    {
        return elementCount;
    }
    // 简单了实现迭代器
    private class SimpleIterator implements Iterator<T>
    {
        int pos = -1;
        int expectedModCount;
        int lastPosition = -1;
        SimpleIterator()
        {
            super();
            expectedModCount = modCount;
        }
        public boolean hasNext()
        {
            return pos + 1 < size();
        }
        public T next()
        {
            if (expectedModCount == modCount)
            {
                try
                {
                    T result = elementAt(pos + 1);
                    lastPosition = ++pos;
                    return result;
                }
                catch (IndexOutOfBoundsException e)
                {
                    throw new NoSuchElementException();
                }
            }
            throw new ConcurrentModificationException();
        }
        public void remove()
        {
            if (this.lastPosition == -1)
            {
                throw new IllegalStateException();
            }
            if (expectedModCount != modCount)
            {
                throw new ConcurrentModificationException();
            }
            try
            {
                Queue.this.remove(lastPosition);
            }
            catch (IndexOutOfBoundsException e)
            {
                throw new ConcurrentModificationException();
            }
            expectedModCount = modCount;
            if (pos == lastPosition)
            {
                pos--;
            }
            lastPosition = -1;
        }
    }
}

package com.alg.queue;
public class QueueMain
{
    public static void main(String[] args)
    {
        Queue<String> queue = new Queue<String>();
        queue.enqueue("a");
        queue.enqueue("b");
        queue.enqueue("c");
        queue.enqueue("d");
        queue.enqueue("e");
        System.out.print("入队:");
        for (String q : queue)
        {
            System.out.print(q + " ");
        }
        System.out.println("出队元素：" + queue.dequeue());
        System.out.print("出队后:");
        for (String q : queue)
        {
            System.out.print(q + " ");
        }
        System.out.println("取队头元素:" + queue.peek());
        queue.clear();
        System.out.println("清空队:" + queue.size());
    }
}
运行结果：
入队:a b c d e 出队元素：a
出队后:b c d e 取队头元素:b
清空队:0