링크 기반, 배열 구현 대기 열, 순환 대기 열

public interface QueueADT {
	//  
	public void enqueue(Object element);
	//  
	public Object dequeue();
	//      
	public Object first();
	//    
	public boolean isEmpty();
	//      
	public int size();
	
	public String toString();
}

public class LinkedQueue implements QueueADT {
	
	//      ，     ，         
	class Node {
		int data; //    
		Node next;//    

		public Node(int data) {
			this.data = data;
		}
	} 
	//    、    
	private Node front,rear;
	//       
	private int count;
	
	public LinkedQueue() {
		front=null;
		rear=null;
		count=0;
	}
	//              ，        ，          ，          
	//       ，          
	@Override
	public void enqueue(Object element) {
		Node node=new Node((Integer)element);
		if(isEmpty()){
			front=rear=node;
		}else{
			rear.next=node;
			rear=node;
		}
		count++;
	}
	
	@Override
	public Object dequeue() {
		if(isEmpty()){
            System.out.println("       ");
            System.exit(1);
        }
		Object result=front.data;
		front=front.next;
		count--;
		return result;
	}

	@Override
	public Object first() {
		return front.data;
	}

	@Override
	public boolean isEmpty() {
		return (size()==0);
	}

	@Override
	public int size() {
		return count;
	}
	
	public static void main(String[] args) {
        
        LinkedQueue queue = new LinkedQueue();
        
        System.out.println("   0 9  ，      5 ");
        for(int i = 0;i < 10;i++)
            queue.enqueue(i);
        for(int i = 0;i < 5;i++)
            queue.dequeue();
        System.out.println("      ： " + queue.size());
        System.out.println("     ？： " + queue.isEmpty());
        System.out.println("     ： " + queue.first());

    }

}

//       ，       ，      ，           ，        ，            
public class ArrayQueue implements QueueADT {
	
	private Object[] contents;
	//      ，rear       ，         
	private int rear;
	private static int SIZE = 10;
	
	public ArrayQueue(){
        contents = new Object[SIZE];
        rear = 0;
    }
	
	public void expand(){
        Object[] larger = new Object[size()*2];
        for(int index = 0;index < rear;index++)
            larger[index] = contents[index];
        
        contents = larger;
    }
	
	@Override
	public void enqueue(Object element) {
		if(rear == contents.length)
            expand();
        contents[rear] = element;
        rear++;
	}

	@Override
	public Object dequeue() {
		if(isEmpty()){
            System.out.println("    ");
            System.exit(1);
        }
        Object result = contents[0];
        //        ，            
        for(int index = 0;index < rear;index++)
                contents[index] = contents[index+1];
        rear--;
        return result;        
	}

	@Override
	public Object first() {
		return contents[0];
	}

	@Override
	public boolean isEmpty() {
		return (size()==0);
	}

	@Override
	public int size() {
		return rear;
	}

}

//                       ，              ，       ，         
public class CircularArrayQueue implements QueueADT{
	
	private Object[] contents;
    private int front,rear;//front     ，rear            
    private int count;//        
    private static int SIZE = 10;
    
    
    public CircularArrayQueue(){
        contents = new Object[SIZE];
        front = -1;
        rear = 0;
        count = 0;
    }
	//          ，     ，                            
	@Override
	public void enqueue(Object element) {
		if(isEmpty()){
			contents[0]=element;
			front=0;
			rear=1;
			count++;
		}else{
			contents[rear]=element;
			rear=(rear+1)%contents.length;
			count++;
		}
	}

	@Override
	public Object dequeue() {
		if(isEmpty()){
            System.out.println("    ！！！");
            System.exit(1);
        }
		Object result = contents[front];
        front = (front + 1) % contents.length;
        count--;
        return result;    
	}

	@Override
	public Object first() {
		return contents[front];
	}

	@Override
	public boolean isEmpty() {
		return (size()==0);
	}

	@Override
	public int size() {
		return count;
	}

}