学步园

链表实现，插入节点放最后就行了。

代码：

package nuaa.ds;

import java.util.NoSuchElementException;

public class LinkedQueue<T> {
	private Node<T> head;
	private Node<T> tail;
	private int size;
	
	public void enqueue(T t){
		if(null==t){
			throw new IllegalArgumentException();
		}
		if(size==0){
			head = new Node<T>(t);
			tail = head;
			size++;
			return;
		}
		Node<T> p = new Node<T>(t);
		
		tail.next = p;
		tail = p;
		size++;
	}
	
	public T dequeue(){
		if(size==0){
			throw new NoSuchElementException();
		}
		Node<T> p = head;
		head = head.next;
		return p.u;
	}
	public LinkedQueue(){
		this.size = 0;
	}
	
	public boolean isEmpty(){
		return size==0 ? true : false;
	}
	
	public T element(){
		return head.u;
	}
	public int  size(){
		return size;
	}
	class Node<U>{
		U u;
		Node<U> next;
		
		public Node(U u) {
			super();
			this.u = u;
		}
		
	}
}

数组实现循环队列：

分离出满和空单独讨论，满就doble size，空了就把索引head tail都置为-1

代码：

package nuaa.ds;

import java.util.NoSuchElementException;

public class Queue<E> {
	private Object[] arrays = new Object[this.capacity];	//holds the objects
	private int size=0;	//current size
	private int capacity = 2;	//default capacity
	private int head = -1;	//location of the head of queue
	private int tail = -1;	//location of the tail of queue
	
	public void enqueue(E e) {
		
		if(null==e){
			throw new IllegalArgumentException("e is null");
		}
		if(this.size()>=this.capacity||arrays.length==0){// arrays is full
			Object[] old = this.arrays;
			this.capacity = 2*this.capacity;
			this.arrays = new Object[this.capacity];
			this.head = 0;
			this.tail = old.length-1;
			for(int i=0;i<old.length;i++){//copy the elements
				arrays[i] = old[i];
			}
			
			//add the element
			this.tail++;	
		}else{// not full
			if(head==-1&&tail==-1){//empty
				this.head = 0;
				this.tail = 0;
				
			}else if(head<tail){ 
				if(tail==capacity-1){//tail is at the end of the arrays
					this.tail = 0;
				}else{
					tail++;
				}
			}else{//head>tail
				tail++;
			}
		}
		this.size++;
		arrays[tail] = e;
	}

	
	public E dequeue() {
		if(size==0){//empty
			throw new NoSuchElementException();
		}
		if(size==1){//only 1 element
			this.head = -1;
			this.tail = -1;
			this.size--;
			return (E)this.arrays[tail];
		}
		if(head==capacity-1){
			this.head = 0; 
			this.size--;
			return (E)arrays[capacity-1];
		}
		this.size--;
		this.head++;
		return (E)arrays[head-1];
	}
	public boolean isEmpty(){
		return size==0 ? true : false; 
	}
	
	public int size() {
		return this.size;
	}
}