算法与数据结构-队列

队列

特点

先进先出

入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

用数组实现的队列叫作顺序队列，用链表实现的队列，叫作链式队列。

Demo

注意：这个Demo里边的Array是数组篇中的Array引用。

//队列得共有接口
package com.wanda.interfaces;

public interface Queue<E> {
	void enqueue(E value);
	E dequeue();
	E getFront();
	int getSize();
	boolean isEmpty();
}

           

package com.wanda.array;

import com.wanda.interfaces.Queue;

public class ArrayQueue<E> implements Queue<E>{
		private Array<E> array;
		public ArrayQueue(int capacity) {
			// TODO Auto-generated constructor stub
			array=new Array<>(capacity);
		}
		public ArrayQueue() {
			// TODO Auto-generated constructor stub
			array=new Array<>();
		}

	@Override
	public void enqueue(E value) {
		// TODO Auto-generated method stub
		array.addLast(value);
		
	}

	@Override
	public E dequeue() {
		// TODO Auto-generated method stub
		return array.removeFirst();
	}

	@Override
	public E getFront() {
		// TODO Auto-generated method stub
		return array.getFirst();
	}

	@Override
	public int getSize() {
		// TODO Auto-generated method stub
		return array.getSize();
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return array.isEmpty();
	}
	@Override
	public String toString() {
		StringBuilder res=new StringBuilder();
		res.append("queue");
		res.append("fornt [");
		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();
	}

}

           

循环队列

顾名思义就是队列的头部和尾部可以是同一个元素，也就是让它循环起来。

写好循环队列的条件

队列为空的判断条件仍然是 head == tail

当队满时，(tail+1)%n=head。

package com.wanda.array;

import com.wanda.interfaces.Queue;

public class LoopQueue<E> implements Queue<E> {
	private E[] data;
	private int front,tail;
	private int size;
	public LoopQueue(int capacity) {
		// TODO Auto-generated constructor stub
		data=(E[])new Object[capacity+1];
		//初始化时头部和尾部指向同一个元素
		front=0;
		tail=0;
		size=0;
	}
	//默认指定空间大小为10
	public LoopQueue() {
		this(10);
	}
	//获取队列容量
	public int getCapacity() {
		return data.length-1;
	}

	//入队操作
	@Override
	public void enqueue(E value) {
		// TODO Auto-generated method stub
		if((tail+1)%data.length==front) {//当队列满了进行扩容
			resize(getCapacity()*2);
		}
		data[tail]=value;
		tail=(tail+1)%data.length;
		
	}

	private void resize(int capacity) {
		// TODO Auto-generated method stub
		E[] newData=(E[]) new Object[capacity+1];
		for(int i=0;i<size;i++) {
			newData[i]=data[(i+front)%data.length];
			
		}
		data=newData;
		front=0;
		tail=size;
		
	}
	//出队操作
	@Override
	public E dequeue() {
		// TODO Auto-generated method stub
		if(isEmpty()) {
			throw new IllegalArgumentException("can not dequeue,beacause queue is empty");
		}
		E ret=data[front];
		data[front]=null;
		front=(front+1)%data.length;
		if(size==getCapacity()/4&&getCapacity()/2!=0) {
			resize(getCapacity()/2);//缩容操作
		}
		return ret;
	}

	@Override
	public E getFront() {
		// TODO Auto-generated method stub
		return data[front];
	}

	@Override
	public int getSize() {
		// TODO Auto-generated method stub
		return data.length;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size==0;
	}

	@Override
	public String toString() {
		StringBuilder res=new StringBuilder();
		res.append("queue->");
		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>(5);
		for(int i=0;i<10;i++) {
			queue.enqueue(i);
			/*if(i%3==0) {
				queue.dequeue();
			}*/
		}
		System.out.println(queue);
	}
}