数据结构-------队列

数据结构：

2.2 队列：

队列特性：队列：FIFO（先进先出）
队列可由顺序表或者链表实现：

数组实现

//初始化
	Object[] queue;
	int size;
	
	int front=0;
	int back=0;
	QueueBulid(int length){
		queue=new Object[length];
		size=length;
	}
//入队
	public void enqueue(Object element){
		
		queue[back]=element;
		//back=(back+1)%size;
		back++;
	}	
//出队
public Object dequeue(){
		Object result=queue[front];
		//front=(front+1)%size;
		front++;
		return result;
	}

链表实现

	//初始化
	private int listSize;
	private Node listTop;
	private Node listTail;
	
	class Node{
	
		Object data;
		Node next;
		
		public Node() {
			// TODO Auto-generated constructor stub
		}
		
		public Node(Object data, Node next) {
			// TODO Auto-generated constructor stub
			this.data=data;	
			this.next=next;
			
		}
	}
//入队
public void linkedEnqueue(Object element){
		Node newNode;
		if(listSize==0){
			listTop=new Node(element, null);
			listTail=listTop;
		}else{
			newNode=new Node(element, null);
			listTail.next=newNode;
			listTail=newNode;
		}
		listSize++;
	}

//出队
public Object linkedDequeue(){
		Object result=null;
		if(listSize!=0){
			result=listTop.data;
			listTop=listTop.next;	
			listSize--;
		}
		return result;
	}

循环队列

普通队列在入队和出队的过程中会存在前面的数据出队了，后面继续在入队最后造成队满了，但是前面已出队数据所占的地址无法让后面入队数据所占用，这会造成数据“假溢出”，造成资源的浪费。为了解决这一问题，设计出循环队列。

//初始化
	int front;
    int rear;
    Object[] queueList;
    int size;
   
    public CircleQueue(int MaxLen) {
        // TODO Auto-generated constructor stub    
        queueList=new Object[MaxLen];
        size=MaxLen;
        front=0;
        rear=0;
    }
//入队 
    public void enqueue(Object element){
    	queueList[rear]=element;
		rear=(rear+1)%size;
	}
//出队 
	public Object dequeue(){
		Object result=queueList[front];
		//防越界
		front=(front+1)%size;
		
		return result;
	}