文章导读
【队列结构和栈结构一样，也是一种特殊的线性表。队列结构只允许在表的一端插入元素，而在另一端删除元素，队列结构的这种特性非常类似于现实生活中的排队，后来的人在队尾入队，办完业务的人在队首出队。本文主要讨论用队列结构解决业务办理自动叫号问题】
1、认识队列结构
在现实生活中，当人们去银行、行政大厅等企业和办事机构办理业务时，都需要从排队机领取排队号码，等待叫号。类似排队机这样的程序，其内部数据结构一般都会用到队列结构。
队列结构和栈结构一样，都是特殊的线性表，但也有不同之处。栈结构只允许在表的一端插入和删除数据，而队列结构只允许在表的一端插入元素，而在另一端删除元素。允许插入元素的一端称为队尾，允许删除元素的一端称为队头。若给定一队列：
S = (a1，a2，……，an)
则称a1是队头元素，an是队尾元素，表中元素按an，……a2，a1的次序入队，出队的顺序是a1，a2，……，an。也就是说，队列结构的元素访问原则是先进先出，因此队列结构也称为先进先出的线性表，如下图所示。
图 1 队列结构
队列结构运算有入队、出队、访问队头元素、置队空四种基本运算。
（1）入队运算
该运算在长度为n的队列中，将元素置入队尾。若队列已满，返回出错信息。
（2）出队运算
该运算在长度为n的队列中，取出队首元素，并从队首删除该元素。若队列为空，返回出错信息。
（3）访问队首元素
该运算在长度为n的队列中，取出队首元素。若队列为空，返回出错信息。
（4）置队空
该运算将队列设置为空队列。
在程序中要实现队列结构，采用线性链表存储结构最为合适。每次的入队和出队运算无需移动队列元素，队列长度也可以动态变化。在Java语言中，可以使用LinkedList类构建队列结构。LinkedList类每个结点用内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。
例1：使用Java语言建立一个队列
package com.milihua.algorithm.lineartable;
import java.util.Iterator;
import java.util.LinkedList;
public class Queue<E> {
/**
* 声明用于存储E泛型的队列
*
*/
LinkedList<E> queue = new LinkedList<>();
/**
* 入队运算
*
*/
public void enQueue(E obj) {
queue.addLast(obj);
}
/**
* 出队运算
*
*/
public E deQueue() {
if( queue.isEmpty() )
return null;
E e = queue.getFirst();
queue.removeFirst();
return e;
}
/**
* 队列置空运算
*
*/
public void emptyQueue() {
queue.clear();
}
/**
* 访问队列头部运算
*
*/
public E getHead() {
if( queue.isEmpty() )
return null;
E e = queue.getFirst();
return e;
}
/**
* 获取队列长度
*
*/
public int getSize() {
return queue.size();
}
/**
* 从队列头部开始遍历队列
*
*/
public void display()
{
System.out.print("[");
for(Iterator iter = queue.iterator(); iter.hasNext();)
{
E e = (E) iter.next();
System.out.print(e.toString());
System.out.print(",");
}
System.out.print("]");
}
}Queue队列类使用泛型定义，可以存储不同类型的队列元素。使用LinkedList线性链表作为队列结构，实现了出队、入队、置空队列、访问队列头部、遍历队列运算。出队运算在返回队列头部元素的同时，需要从队列中删除该元素，入队运算需要把元素加入到队尾。出队和入队算法的时间复杂度都为O(1)。
Queue队列类的测试程序代码如下。
package unittest;
import com.milihua.algorithm.lineartable.Queue;
public class QueueTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//声明存储字符串的队列
Queue<String> queueStr = new Queue<>();
//入队操作
queueStr.enQueue("this is one");
queueStr.enQueue("this is two");
queueStr.enQueue("this is three");
queueStr.enQueue("this is four");
queueStr.enQueue("this is five");
queueStr.enQueue("this is six");
//输出队列
queueStr.display();
//出队
System.out.println("第一个出队：" + queueStr.deQueue().toString());
System.out.println("第二个出队：" + queueStr.deQueue().toString());
//输出队列
queueStr.display();
}
}2、用队列结构实现业务办理自动叫号
前面讨论了队列结构的实现及运算，接下来探讨一下如何用队列实现业务办理的自动叫号。
业务办理自动叫号有两个关键事件。一个事件是取号，当新的客户办理业务时，需要在排队机取号；一个事件是叫号，当业务办理窗口开始办理新业务时，需要叫号。取号事件是入队操作，叫号事件是出队操作。
/**
* 取号事件处理
* 新客户入队
* 返回前面等待人数
*
*/
public Integer inQueue(Integer num) {
queue.enQueue(num);
length += 1;
return length;
}
/**
* 叫号事件处理
* 客户出队
* 返回当前排队号
*/
public Integer outQueue() {
if (queue.getSize() <= 0)
return -1;
Integer num = queue.deQueue();
return num;
}取号事件和叫号事件处理方法中的queue对象是前面介绍的队列Queue类，length是当天办理业务总客户数。inQueue是取号事件处理方法，传入参数为排队号，queue将传入的排队号加入队列，length做加1操作，并返回length。outQueue是叫号事件处理方法，出队之前需要判断队列是否为空，如队列为空，则返回-1，若队列不为空，queue做出队操作，并返回排队号。
业务办理自动叫号类代码如下。
package com.milihua.algorithm.lineartable;
public class QueueOffer {
/**
* 排队人数
*
*/
int length = 0;
/**
* 声明一个队列，用于排队
*
*/
Queue<Integer> queue = new Queue<>();
/**
* 取号事件处理
* 新客户入队
* 返回前面等待人数
*
*/
public Integer inQueue(Integer num) {
queue.enQueue(num);
length += 1;
return length;
}
/**
* 叫号事件处理
* 客户出队
* 返回当前排队号
*/
public Integer outQueue() {
if (queue.getSize() <= 0)
return -1;
Integer num = queue.deQueue();
return num;
}
/**
* 获取当前排队人数
*
**/
public Integer getSize() {
return queue.getSize();
}
/**
* 遍历队列
*
*/
public void display() {
queue.display();
}
/**
* 获取总排队人数
*
**/
public Integer getLength() {
return length;
}
}QueueOffer类为程序主要处理类，类的主要方法为取号和叫号事件处理，并内置了队列queue类，用于内部的队列结构。QueueOffer类主要完成取号和叫号事件的处理，程序还需要模拟取号和叫号事件的随机发生，模拟取号和叫号事件的随机发生，可以采用键盘输入模拟。假定用户输入“add”表示新客户到达取号，用户输入数字1至6表示办理业务的工作窗口叫号，用户输入“exit”表示停止业务办理。模拟程序代码如下。
import java.util.Scanner;
import com.milihua.algorithm.lineartable.QueueOffer;
public class QueueOfferTest {
/**
* 办事窗口字符串数组表示
*/
static String[] w = {"1","2","3","4","5","6"};
public static void main(String[] args) {
QueueOffer offer = new QueueOffer();
System.out.println("取号请输入add，叫号请分别输入数字1-6，退出输入exit");
while(true)
{
Scanner sc = new Scanner(System.in);
String str = sc.next();
if( str.equals("exit") )
break;
else if( str.equals("add") )
{
Integer num = offer.getLength() + 1;
offer.inQueue(num);
System.out.printf("您前面有 %d 人在等待", offer.getSize());
System.out.println();
offer.display();
}
else if( isCallNum(str) )
{
Integer num = offer.outQueue();
if( num == -1 )
{
System.out.println("没有客户在等待");
}
else
{
System.out.printf("请 %d 号到 %s 窗口", num,str);
System.out.println();
}
}
else
{
System.out.println("您的输入有误，取号请输入add，"
+ "叫号请分别输入数字1-9，"
+ "退出输入exit");
}
}
}
/**
* 判读是否是叫号事件
*/
public static boolean isCallNum(String op)
{
for(int i = 0; i < w.length; i++ )
{
if( op.equals(w[i]) )
return true;
}
return false;
}
}文章小结
（1）队列结构是一种运算受限的线性表，插入运算和删除运算只能在表头和表尾进行。允许插入的一端称为队尾，允许删除的一端称为队首，插入称为入队操作，删除称为出队操作。现实生活中的排队非常类似于队列结构，后来的人要加入排队序列得需要从队尾加入，业务办理完毕得需要从队首出队。因此，队列结构也称为先进先出表。
（2）取号和叫号是业务办理自动叫号程序的两个主要事件，取号是入队操作，叫号是出队操作。在Java语言中，一般使用LinkedList来实现队列结构，LinkedList类是线性链表结构，入队和出队运算无需移动队列元素，队列长度也可以动态变化。