Java实现--队列

昨天风王“山竹”肆虐大片土地...今天还在不断下雨

进入正题吧。今天学习的是队列，跟栈(LIFO)不同，队列采用的是先进先出(FIFO)的模式，个人认为，其实队列跟栈都是比较简单的，我们定义了两个指针变量，一个是队首（front），另外一个就是队尾（rear），为了更统一的理解，我们把队列里面的一个个元素（在这里是数字），当做现实世界中一个个的人。讲最重要的两个操作，insert操作和remove操作

insert操作：

当第一个人往这个队列一站，这时候，队首指针和队尾指针都会指向这个人，接着排第二个人，此时数组里面的下标为1，所以我们在赋值给rear队尾指针的时候赋其值为-1，因为多了一个人，我们先自增rear，即++rear然后再把这个人排到队列里面去..接下来只要来一个人就往里面放人（当然这里有一个前提，就是我们不能超过数组容量，否则会导致数组越界）。因为是队列，只要我们第一个人不出这个队列，那么队首永远都是这个人，但是队尾指针却会随着排进来的人而改变，永远指向的都是最后一个人。当然这里会有一种特殊情况，即如果我们这个队列只容许容纳十个人，前面6个人都搞完了各自的业务，这时候又来了一个人要往里面排队，那么这时候该怎么办呢？此时的队尾指针指向的是数组最大容量的数字即maxSize-1，我们已经不能再讲rear（队尾）自增了，这时候我们便要进行环绕式处理，看看下面两张图。

有没有点顿悟的感觉？我们将rear回到数组下标为0的地方，（图片中的-1表示我们起初将rear赋值为-1），就像我们有时候在饭堂吃放，一排不够排我们就会绕个圈排，这是同样的道理。当我们的队列已经满的时候就不能再插入新的人了，如果还要执行该操作，我们此时就要抛出异常。

remove操作:

将队首的人弹出去，然后将队首指针front指向下一个人即自增。特殊情况：当我们遇到上图中的情况，我们要将front指向数组标为0的地方。

 

下方为代码：

/**
 * 自定义队列
 * @author Administrator
 *
 */
public class Queue {
	private long[] QueueArray;
	private int maxSize;
	private int front;
	private int rear;
	private int nItems;
	
	
	public Queue(int maxSize){
		this.maxSize = maxSize;
		QueueArray = new long[maxSize];
		front = 0;
		rear = -1;
		nItems = 0;
	}
	
	//往队列里面插入数据
	public void insert(int number) {
		if(!isFull()) {
			if(rear==maxSize-1) {
				rear = -1;
			}
			QueueArray[++rear] = number; 
			nItems++;
		}else {
			try {
				throw new Exception("The queue is full!");
			}catch(Exception e){
				e.printStackTrace();
			}
		}
	}
	
	//每调用一次都将队列里面的首个元素即队首移除
	public String remove() {
		if(!isEmpty()) {
			long temp = QueueArray[front++];
			if(front==maxSize) {
				front = 0;
			}
			nItems--;
			return "Remove "+temp+" successful!";
		}else {
			return "The Queue is Empty.Not any number you can remove!";
		}
	}
	
	//返回队列的的队首
	public String peekFront() {
		return "The Queue front is:"+QueueArray[front];
	} 
	
	//返回队列的队尾
	public String peekRear() {
		return "The Queue rear is:"+QueueArray[rear];
	} 
	
	//检查该队列是否为空
	public boolean isEmpty() {
		/*if(nItems!=0) {
			return false;
		}else {
			return true;
		}可以直接用一条语句完成上述操作*/
		return (nItems==0);
	}
	
	//判断该队列是否已满即
	public boolean isFull() {
		/*if(nItems==maxSize) {
			return true;
		}else {
			return false;
		}同样也可以直接用一条语句完成上述操作*/
		return (nItems==maxSize);
	}
	
	//返回该队列的长度
	public int size() {
		return nItems;
	}
}

/**
 * 测试自定义的队列
 * @author Administrator
 *
 */
public class TestQueue {
	public static void main(String[] args) {
		Queue q = new Queue(10);
		q.insert(10);
		q.insert(30);
		q.insert(40);
		q.insert(50);
		q.insert(60);
		q.insert(80);
		q.insert(100);
		q.insert(120);
		q.insert(110);
		q.insert(150);
		System.out.println(q.isEmpty());
		System.out.println(q.isFull());
		System.out.println(q.peekFront());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.remove());
		q.insert(130);
		System.out.println(q.peekRear());		
	}
}

 

结果显示：

如果插入的时候队列都处于空的状态那么结果为：

false
true
The Queue front is:10
Remove 10 successful!
Remove 30 successful!
Remove 40 successful!
Remove 50 successful!
Remove 60 successful!
Remove 80 successful!
The Queue rear is:130

如果队列已满还要插入，此时会抛出异常：

java.lang.Exception: The queue is full!
	at Queue.insert(Queue.java:32)
	at TestQueue.main(TestQueue.java:20)
The Queue rear is:150

 

insert和delete的时间复杂度均为O（1）.