队列的基本概念
队列（简称队）也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系和线性表完全相同。差别是线性表允许在任意位置插入和删除，而队列只允许在一端进行插入操作而在另一端进行删除操作。
队列中允许插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作通常称为入队列，队列的删除操作通常称为出队列。
根据队列的定义，每次入队列的数据元素都放在原来的队尾之后成为新的队尾元素，每次出队列的数据元素都是队头元素。这样，最先入队列的数据元素总是最先出队列。最后入队列的数据元素总是最后出队列，所以队列也称为先进先出表。
队列的抽象数据类型
1、数据集合：队列的数据集合可以表示为a1,a2,a3,a4，每个数据元素的数据类型可以是任意类类型
2、操作集合：1、入队列操作（append()）
2、出队列操作（delete()）
3、取队列的头元素(getFront())
4、判断队列是否为空(isEmpty())
源代码------顺序存储结构
队列接口代码
package com.queue; //队列接口 public interface Queue { //入队列操作 public void append(Object object); //出队列操作 public Object delete(); //取队列头元素 public Object getFront(); //判断队列是否为空 public boolean isEmpty(); } |
队列接口实例化类
package com.queue; public class SeqQueue implements Queue { //相关属性和构造方法 //默认大小 static final int defauleSize=10; //队头 int front; //队尾 int rear; //队列元素个数统计 int count; //队列初始化大小 int maxSize; //队列数据信息 Object[] data; public void initiate(int sz){ maxSize=sz; front=rear=0; count=0; data=new Object[sz]; } public SeqQueue(){ initiate(defauleSize); } public SeqQueue(int length){ initiate(length); } @Override public void append(Object object) { // TODO Auto-generated method stub if(count>0&&front==rear){ return; } data[rear]=object; //求模运算 rear=(rear+1)%maxSize; count++; } @Override public Object delete() { // TODO Auto-generated method stub Object object=null; if(count==0){ object="404"; return object; }else{ object=data[front]; //求模运算 front=(front+1)%maxSize; count--; return object; } } @Override public Object getFront() { // TODO Auto-generated method stub Object object=null; if(count==0){ object="404"; return object; }else{ return data[front]; } } @Override public boolean isEmpty() { // TODO Auto-generated method stub return count!=0; } }
|
实验结果：
package com.queue; public class QueueTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub SeqQueue queue=new SeqQueue(); //判断队列是否为空 boolean target=queue.isEmpty(); System.out.println("队列是否为空："+target); //入队列 queue.append("c"); queue.append("c++"); queue.append("c#"); queue.append("object-c"); queue.append("php"); queue.append("java"); queue.append("ruby"); queue.append("javascript"); queue.append("ext"); queue.append("jquery"); //再次判断队列是否为空 boolean targets=queue.isEmpty(); System.out.println("再次判断队列是否为空："+targets); //出队列 Object object=queue.delete(); System.out.println("出队列的元素是："+object); //取队列头元素 Object front=queue.getFront(); System.out.println("队列头元素是:"+front); } } |
图片展示：
源代码--------链式存储结构