目录

队列接口

数组队列

循环队列

• 队列接口

package com.suanfa.queue;
/**
 * 队列接口
 * @author Administrator
 *
 * @param <E>
 */
public interface Queue<E> {
	int getSize();
	boolean isEmpty();
	void enqueue(E e);
	E dequeue();
	E getFront();

}

• 数组队列

package com.suanfa.queue;

import com.suanfa.array.DongTaifFunXingArray;

/**
 * 基于数组的队列，先进先出（FIFO：first in first out），出队时时间复杂度是O（n）级别
 * @author Administrator
 *
 */
public class ArrayQueue<E> implements Queue<E>{
	private DongTaifFunXingArray<E> array;
	
	public ArrayQueue(int capacity){
		array=new DongTaifFunXingArray<E>(capacity);
	}
	public ArrayQueue(){
		array=new DongTaifFunXingArray<E>();
	}
	
	/**
	 * 获取队列大小
	 * @return
	 */
	
	public int getSize(){
		return  array.getSize();
	}
	/**
	 * 获取队列容积
	 * @return
	 */
	public int getCapacity(){
		return array.getCapacity();
	}
	/**
	 * 检查队列是否为空
	 * @return
	 */
	public boolean isEmpty(){
		return array.isEmpty();
	}
	/**
	 * 从队列尾部添加一个元素
	 * @param e
	 */
	public void enqueue(E e){
		array.addLast(e);
	}
	/**
	 * 从队首取出一个元素
	 * @return
	 */
	public E dequeue(){
		return array.removeFirst();
	}
	/**
	 * 获取队首元素
	 */
	public E getFront() {
		return array.getFirst();
	}
	
	@Override
	public String toString() {
		StringBuilder res=new StringBuilder();
		res.append("Queue:");
		res.append("front [");
		for (int i = 0; i < array.getSize(); i++) {
			res.append(array.get(i));
			if(i!=array.getSize()-1)
				res.append(",");
		}
		res.append("]tail");
		return res.toString();
	}
	
	public static void main(String[] args) {
		ArrayQueue<Integer> queue=new ArrayQueue<Integer>();
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
			if(i%3==2)
				queue.dequeue();System.out.println(queue);
		}
		
	}
	

}

• 循环队列

package com.suanfa.queue;
/**
 * 循环队列，相当于一个环形数组，默认浪费一个空间，出队时时间复杂度时O（1）级别
 * @author Administrator
 *
 */
public class LoopQueue<E> implements Queue<E>{
	private E[]data;
	private int front,tail;//队首和队尾指针
	private int size;//元素个数
	
	public LoopQueue(int capacity){
		data=(E[])new Object[capacity+1];
		front=0;
		tail=0;
		size=0;
	}
	public LoopQueue(){
		this(10);
	}
	/**
	 * 获取可以使用的空间
	 * @return
	 */
	public int getCapacity(){
		return data.length-1;
	}
	/**
	 * 获取元素个数
	 */
	public int getSize() {
		return size;
	}
	/**
	 * 判断是否为空
	 */
	public boolean isEmpty() {
		return front == tail;
	}
	/**
	 * 扩容或缩容
	 * @param newCapacity
	 */
	private void resize(int newCapacity){
		E[] newdata=(E[])new Object[newCapacity+1];
		for(int i=0;i<size;i++){
			newdata[i]=data[(i+front)%data.length];//front是原数组的头，循环赋值
		}
		data=newdata;//指向新的队列
		front=0;//头指向新数组的第一个位置
		tail=size;//尾刚好是原数组的元素个数
	}
	/**
	 * 向队列尾部添加元素
	 */
	public void enqueue(E e) {
		if((tail+1)%data.length ==front){
			resize(getCapacity()*2);//如果队列满了，进行扩容
		}
		data[tail]=e;
		tail=(tail+1)%data.length;
		size++;
		
	}
	/**
	 * 从队首取出一个元素
	 */
	public E dequeue() {
		if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
		E ret=data[front];
		data[front]=null;
		front=(front+1)%data.length;
		size--;
		if(size==getCapacity()/4 && getCapacity()/2!=0)
			resize(getCapacity()/2);
		return ret;
	}
	/**
	 * 获取队首元素
	 */
	public E getFront() {
		if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
	}
	
	public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
	
	public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<Integer>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
	

}