【玩转数据结构 从入门到进阶】 队列

package Arr;
/**
 * 数组队列
 * @author 大南海
 *
 * @param <E>
 */
public class ArrayQueue<E> implements Queue<E> {

	private Array<E> array;

	public ArrayQueue(int capacity) {
		array = new Array<>(capacity);
	}

	public ArrayQueue() {
		array = new Array<>();
	}
    
	
	public int getSize() {
		return array.getSize();
	}
	
	//入队
	@Override
	public void enqueue(E e) {
		array.addList(e);
	}

	@Override
	public boolean isEmpty() {
	
		return array.isEmpty();
	}
     
	
	public int getCapacity() {
		return array.getCapacity();
	}
	
	//出队
	@Override
	public E dequeue() {
		
		return array.removeFirst();
	}
	
	

	@Override
	public E getFront() {
		
		return array.getFirst();
	}
	@Override
	public String toString() {
		StringBuffer res=new  StringBuffer();
		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<>();
		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 Arr;

/**
 * 循环队列
 */
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);
	}

	public int getCapacity() {
		return data.length - 1;
	}

	public boolean isEmpty() {
		return front == tail;
	}

	public int getSize() {
		return 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 daqueue 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("Cannot daqueue from an empty queue.");
		}

		return data[front];
	}

	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];

		}
		data = newData;
		front = 0;
		tail = size;

	}
	@Override
	public String toString() {
		StringBuilder res=new StringBuilder();
		res.append(String.format("Queue:size=%d,capacity", 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();
	}

}

package Arr;

public interface Queue <E>{

	 void enqueue(E e);
	 
	 boolean isEmpty();
	 
	 E dequeue();
	 
	 E getFront();

	
}

 需要更多优质课程请加：