队列(数据结构--Java版)

    队列:队列是一种先进先出的数据结构,它的元素只能在一端增加,该端称为rear,元素的删除只能在另一端进行,这一端称为front.

 

1.基于数组的实现(循环队列)

public class QueueClass {
	private int maxQueueSize;//队列的大小
	private int count;		 //计数器
	private int queueFront;  //队列的头元素
	private int queueRear;   //队列的尾元素
	private int[] list;
	
	public QueueClass(){
		maxQueueSize=100;
		queueFront=0;
		queueRear=maxQueueSize-1;//队尾初始化为最后一个元素
		count=0;
		list=new int[maxQueueSize];
	}
	
	public void initializeQueue(){
		for(int i=queueFront;i<queueRear;i=(i+1)%maxQueueSize){
			list[i]=0;
		}
		queueFront=0;
		queueRear=maxQueueSize-1;
		count=0;
	}
	//判断是否为空队列
	public boolean isEmptyQueue(){
		return count==0;
	}
	//判断是否为满队列
	public boolean isFullQueue(){
		return count==maxQueueSize;
	}
	//取队列的头元素
	public int fornt(){
		if(isEmptyQueue()){}
		return list[queueFront];
	}
	//取队尾元素
	public int back(){
		if(isEmptyQueue()){}
		return list[queueRear];
	}
	//入队
	public void addQueue(int newElement){
		if(isFullQueue()){}
		queueRear=(queueRear+1)%maxQueueSize;
		count++;
		list[queueRear]=newElement;
	}
	//出队
	public void deleteQueue(){
		if(isEmptyQueue()){}
		count--;
		list[queueFront]=0;
		queueFront=(queueFront+1)%maxQueueSize;
	}
	
}

2.链式队列

//节点
class QueueNode {
	int info;
	QueueNode link;
}

public class LinkedQueueClass {
	private QueueNode queueFront;//队头
	private QueueNode queueRear; //对尾

	public void initializeQueue() {
		queueFront = null;
		queueRear = null;
	}
	//判断是否为空队列
	public boolean isEmptyQueue() {
		return queueFront == null;
	}
	//判断是否为满队列
	public boolean isFullQueue() {
		return false;
	}
	//取队列的头元素
	public int fornt() {
		if (isEmptyQueue()) {}
		return queueFront.info;
	}
	//取队尾元素
	public int back() {
		if (isEmptyQueue()) {}
		return queueRear.info;
	}
	//入队
	public void addQueue(int newElement) {
		QueueNode newNode;
		newNode = new QueueNode();

		newNode.info = newElement;
		newNode.link = null;

		if (queueFront == null) {
			queueFront = newNode;
			queueRear = newNode;
		} else {
			queueRear.link = newNode;
			queueRear = queueRear.link;
		}
	}
	//出队
	public void deleteQueue() {
		if (isEmptyQueue()) {}
		queueFront = queueFront.link;
		if (queueFront == null)
			queueRear = null;
	}
}