在平时的编程中，队列可以应用于很多方面。
在生活中我们同样可以随处见到它的身影，比如我们排队，先排的人先得到服务，后进来的人后接受服务。这就是队列。
说白了，就是FIFO原则（First in First out, 先进先出)。
队列的实现是基于存储结构不同而不同的，通常会有两种方式存储。线性存储或者非线行存储。
1、线性存储。是基于数组等长度固定的存储方式来实现的。我这里是先定义了一个接口，然后基于接口来实现的。
下面请看代码，
package simple;
interface queue {
boolean isEmpty();
void in(Object value);
Object top();
void out();
boolean isFull();
int getSize();
}
public class ArrayBase implements queue {
private static final int MAXSIZE = 100;
int front;
int rear;
int number;
Object[] data;
ArrayBase() {
front = rear = -1;
number = 0;
data = new Object[MAXSIZE];
}
@Override
public void in(Object value) {
// TODO Auto-generated method stub
if (this.isFull()) {
System.out.println("Sorry, the queue is full!");
} else {
this.rear = (this.rear + 1) % MAXSIZE;
number++;
this.data[this.rear] = value;
}
}
@Override
public Object top() {
// TODO Auto-generated method stub
if (this.isEmpty()) {
System.out.println("Sorry, the queue is empty!");
}
int p = (this.front + 1) % MAXSIZE;
return data[p];
}
@Override
public void out() {
// TODO Auto-generated method stub
if (this.isEmpty()) {
System.out.println("Sorry, the queue is empty!");
}
this.front = (this.front - 1) % MAXSIZE;
number--;
}
@Override
public boolean isFull() {
// TODO Auto-generated method stub
if (this.rear == MAXSIZE - 1) {
return true;
}
return false;
}
public boolean isEmpty() {
if (number == 0) {
return true;
}
return false;
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return this.number;
}
}
接下来是测试类：
package simple;
public class MyQueueTest {
public static void main(String []args){
ArrayBase myQueue=new ArrayBase();
System.out.println(((ArrayBase) myQueue).isEmpty());
myQueue.in(false);
myQueue.in(1);
myQueue.in('T');
myQueue.in("Biao");
System.out.println("Now there are "+myQueue.getSize()+" items!");
System.out.println("Top Item is: "+ myQueue.top());
myQueue.out();
System.out.println("After the out operation,there are "
+myQueue.getSize()+" items in this queue!");
}
}
然后就是我们的测试结果了：
true
Now there are 4 items!
Top Item is: false
After the out operation,there are 3 items in this queue!
2、当然也可以使用非线性的存储结构来实现队列，好处是可以避免“假溢出”的现象，充分的利用到空间。
下面是代码实现：
package simple;
interface queueListBase {
boolean isEmpty();
void in(Object value);
Object top();
Object out();
int getSize();
}
class Node{
Object data;
Node next;
Node(){
data=null;
next=null;
}
}
public class ListBase implements queueListBase{
int number;
Node front;
Node rear;
public ListBase(){
number=0;
front=rear=null;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
if(this.front==this.rear){
return true;
}
return false;
}
/*
* (non-Javadoc)此方法应该尤其要注意的是对初始时的分析
* 我就在此处忘记了front的存在，结果就会导致程序一直抱NullPointerException的错误！
* @see simple.queueListBase#in(java.lang.Object)
*/
@Override
public void in(Object value) {
// TODO Auto-generated method stub
if (rear == null && front == null) {
rear = new Node();
rear.data=value;
front = rear;
} else {
Node node = new Node();
node.data=value;
rear.next = node;
rear = node;
number++;
}
}
@Override
public Object top() {
// TODO Auto-generated method stub
Node temp=new Node();
temp.data=this.front.data;
return temp;
}
@Override
public Object out() {
// TODO Auto-generated method stub
Object temp=null;
if(this.isEmpty()){
System.out.println("Sorry,the queue is Empty!");
return false;
}else{
temp=this.front.data;
this.front=this.front.next;
if(front.next==null){
this.rear=this.front;
}
number--;
}
return temp;
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return number;
}
}
下面是我的测试代码：
package simple;
public class MyQueueTest {
public static void main(String []args){
// ArrayBase myQueue=new ArrayBase();
ListBase myQueue=new ListBase();
System.out.println(((ListBase) myQueue).isEmpty());
myQueue.in(false);
myQueue.in(1);
myQueue.in('T');
myQueue.in("Biao");
System.out.println(myQueue.out());
System.out.println(myQueue.out());
System.out.println(myQueue.out());
System.out.println(myQueue.out());
System.out.println("Now there are "+myQueue.getSize()+" items!");
System.out.println("Top Item is: "+ myQueue.top());
myQueue.out();
System.out.println("After the out operation,there are "
+myQueue.getSize()+" items in this queue!");
}
}
下面是测试的结果：
true
false
1
T
Sorry,the queue is Empty!
false
Now there are 0 items!
Top Item is: simple.Node@659e0bfd
Sorry,the queue is Empty!
After the out operation,there are 0 items in this queue!
结果分析：
不难看出，在链式队列内存储值时，字符串类型并没有成功存储进去。但这并不代表队列无法存储字符串类型的数据，所以我们应该注意这一点！否则将会有可能导致今后软件的出错！下面是一个更加完整的非线性的队列的实现代码，也是我入队操作失败后得到纠正的一篇博客，与君共勉，共同进步吧！非线性队列的实现
