数据结构
一群数据集合和数据之间的关系。
是指相互之间存在一种或多种特定关系的数据元素集合。
队列
特点：先入先出(First in First out ---FIFO)
火车站买票。队头队尾。售票员从头开始卖票。先到的人先买到票就可以离开。
普通队列
普通队列.png
普通队列有限制：
1.售票员走，浪费队列前面的空间。
2.队伍走，需要移动数组，速度慢。
环形队列
环形队列.png
能大大优化普通队列
有队列头，有队列尾。只有一个元素，既是队列头，又是队列尾。
用途：自动排号机
环形队列代码
package ss;
/**
* 环形队列Demo
* 简单环形队列的构建
*
* MyQueue(int capacity) 构造方法（队列大小）
* clearQueue() 清空队列
* destoryQueue() 销毁队列对象
* isEmpty() 队列判空
* isFull() 队列判满
* getLength() 获取队列长度
* EnQueue(T) 入队
* DeQueue() 出队，返回队列的元素
* traverseQueue() 遍历队列
* doSomething(T t) 具体实现逻辑，让用户具体实现
*
* @author Administrator
* @date 2017年10月24日 下午4:58:29
* @param <T> 队列元素
* 因为存放进队列的元素我们是未知的
* 但是可以确定的是一个队列里面的元素基本是固定的
* 所以这里使用了泛型，让用户真正使用的时候才去确定
*/
public abstract class MyQueue<T extends Object> {
//队列对象
//使用Object数组和泛型是为了让队列可以兼容各种类型的对象；
private Object[] mQueue;
//队列当前长度
private int mLength;
//队列容量
private int mCapacity;
//队头，出队时出队的位置
private int mHead;
//对尾，入队时入队的位置
private int mEnd;
/**
* 构造方法
* @param capacity 队列的容量大小
*/
public MyQueue(int capacity) {
mCapacity =capacity;
//初始化参数
mQueue=new Object[mCapacity];
clearQueue();
}
/**
* 清空队列内的参数
*@date 2017年10月24日 下午5:05:19
*/
private void clearQueue() {
mLength=0;
mHead=0;
mEnd=0;
}
/**
* 销毁队列
* 及时释放资源
*@date 2017年10月24日 下午5:08:11
*/
public void destoryQueue(){
clearQueue();
mQueue=null;
System.gc();
}
/**
* 判断当前队列是否为空
* 空：true 非空：flase
*@date 2017年10月24日 下午5:10:12
*/
public boolean isEmpty(){
return mLength==0;
}
/**
* 判断当前队列是否已满
*@date 2017年10月24日 下午5:11:58
*/
public boolean isFull(){
return mLength==mCapacity;
}
/**
* 获取当前队列长度
*@date 2017年10月24日 下午5:20:27
*/
public int getLength(){
return mLength;
}
/**
* 添加元素到队列当中（入队）
* 从队尾开始入队
* @param t 需要入队的对象
* @return 入队是否成功
*@date 2017年10月24日 下午5:24:12
*/
public boolean EnQueue(T t){
if(isFull()){
return false;
}
mQueue[mEnd] =t;
mEnd++;
mLength++;
/**
* 因为是环形队列模型，所以当队头出队以后
* 就会空出位置，队尾自然就可以往空位置上移动
* 所以这里使用%来出来循环
*/
mEnd=mEnd%mCapacity;
return true;
}
/**
* 返回队头位置的元素对象(出队)
*@date 2017年10月24日 下午5:27:52
*/
public T DeQueue(){
if(isEmpty()){
return null;
}
T t =(T) mQueue[mHead];
mHead++;
mLength--;
//这里使用的原理和出队是一样的可以看一下上面:)
mHead = mHead%mCapacity;
return t;
}
/**
* 遍历当前队列全部对象
*@date 2017年10月24日 下午5:30:25
*/
public void traverseQueue(){
for (int i = mHead; i < mHead+mLength; i++) {
doSomething((T)mQueue[i%mCapacity]);
}
}
/**
* 具体处理队列对象的方法
* 这里使用抽象方法因为：
* 对于对象的具体处理逻辑各不相同，所以具体实现交给用户自己去完成
*@date 2017年10月24日 下午5:30:41
*/
public abstract void doSomething(T t);
}
测试代码
package ss;
public class TestDemo {
public static void main(String[] args) {
MyQueue<A> a=new MyQueue<A>(5){
@Override
public void doSomething(A t) {
System.out.println(t.toString());
}
};
A a1=new A(1,"a1");
A a2=new A(2,"a2");
A a3=new A(3,"a3");
A a4=new A(4,"a4");
A a5=new A(5,"a5");
A a6=new A(6,"a6");
a.EnQueue(a1);
a.EnQueue(a2);
a.EnQueue(a3);
a.EnQueue(a4);
a.EnQueue(a5);
a.EnQueue(a6);
a.traverseQueue();
System.out.println("-----------------------------------------------------");
a.DeQueue();
a.DeQueue();
a.EnQueue(a6);
a.traverseQueue();
}
}
因为慕课网的视频是用c语言写的，我在简书上找到了java写的，代码来自Rayhaha附上链接http://t.cn/RWCfxtF
