數(shù)據(jù)結(jié)構(gòu)
一群數(shù)據(jù)集合和數(shù)據(jù)之間的關(guān)系。
是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。
隊(duì)列
特點(diǎn)：先入先出(First in First out ---FIFO)
火車站買票。隊(duì)頭隊(duì)尾。售票員從頭開始賣票。先到的人先買到票就可以離開。
普通隊(duì)列
普通隊(duì)列.png
普通隊(duì)列有限制：
1.售票員走，浪費(fèi)隊(duì)列前面的空間。
2.隊(duì)伍走，需要移動數(shù)組，速度慢。
環(huán)形隊(duì)列
環(huán)形隊(duì)列.png
能大大優(yōu)化普通隊(duì)列
有隊(duì)列頭，有隊(duì)列尾。只有一個元素，既是隊(duì)列頭，又是隊(duì)列尾。
用途：自動排號機(jī)
環(huán)形隊(duì)列代碼
package ss;
/**
* 環(huán)形隊(duì)列Demo
* 簡單環(huán)形隊(duì)列的構(gòu)建
*
* MyQueue(int capacity) 構(gòu)造方法（隊(duì)列大?。? * clearQueue() 清空隊(duì)列
* destoryQueue() 銷毀隊(duì)列對象
* isEmpty() 隊(duì)列判空
* isFull() 隊(duì)列判滿
* getLength() 獲取隊(duì)列長度
* EnQueue(T) 入隊(duì)
* DeQueue() 出隊(duì)，返回隊(duì)列的元素
* traverseQueue() 遍歷隊(duì)列
* doSomething(T t) 具體實(shí)現(xiàn)邏輯，讓用戶具體實(shí)現(xiàn)
*
* @author Administrator
* @date 2017年10月24日 下午4:58:29
* @param <T> 隊(duì)列元素
* 因?yàn)榇娣胚M(jìn)隊(duì)列的元素我們是未知的
* 但是可以確定的是一個隊(duì)列里面的元素基本是固定的
* 所以這里使用了泛型，讓用戶真正使用的時候才去確定
*/
public abstract class MyQueue<T extends Object> {
//隊(duì)列對象
//使用Object數(shù)組和泛型是為了讓隊(duì)列可以兼容各種類型的對象；
private Object[] mQueue;
//隊(duì)列當(dāng)前長度
private int mLength;
//隊(duì)列容量
private int mCapacity;
//隊(duì)頭，出隊(duì)時出隊(duì)的位置
private int mHead;
//對尾，入隊(duì)時入隊(duì)的位置
private int mEnd;
/**
* 構(gòu)造方法
* @param capacity 隊(duì)列的容量大小
*/
public MyQueue(int capacity) {
mCapacity =capacity;
//初始化參數(shù)
mQueue=new Object[mCapacity];
clearQueue();
}
/**
* 清空隊(duì)列內(nèi)的參數(shù)
*@date 2017年10月24日 下午5:05:19
*/
private void clearQueue() {
mLength=0;
mHead=0;
mEnd=0;
}
/**
* 銷毀隊(duì)列
* 及時釋放資源
*@date 2017年10月24日 下午5:08:11
*/
public void destoryQueue(){
clearQueue();
mQueue=null;
System.gc();
}
/**
* 判斷當(dāng)前隊(duì)列是否為空
* 空：true 非空：flase
*@date 2017年10月24日 下午5:10:12
*/
public boolean isEmpty(){
return mLength==0;
}
/**
* 判斷當(dāng)前隊(duì)列是否已滿
*@date 2017年10月24日 下午5:11:58
*/
public boolean isFull(){
return mLength==mCapacity;
}
/**
* 獲取當(dāng)前隊(duì)列長度
*@date 2017年10月24日 下午5:20:27
*/
public int getLength(){
return mLength;
}
/**
* 添加元素到隊(duì)列當(dāng)中（入隊(duì)）
* 從隊(duì)尾開始入隊(duì)
* @param t 需要入隊(duì)的對象
* @return 入隊(duì)是否成功
*@date 2017年10月24日 下午5:24:12
*/
public boolean EnQueue(T t){
if(isFull()){
return false;
}
mQueue[mEnd] =t;
mEnd++;
mLength++;
/**
* 因?yàn)槭黔h(huán)形隊(duì)列模型，所以當(dāng)隊(duì)頭出隊(duì)以后
* 就會空出位置，隊(duì)尾自然就可以往空位置上移動
* 所以這里使用%來出來循環(huán)
*/
mEnd=mEnd%mCapacity;
return true;
}
/**
* 返回隊(duì)頭位置的元素對象(出隊(duì))
*@date 2017年10月24日 下午5:27:52
*/
public T DeQueue(){
if(isEmpty()){
return null;
}
T t =(T) mQueue[mHead];
mHead++;
mLength--;
//這里使用的原理和出隊(duì)是一樣的可以看一下上面:)
mHead = mHead%mCapacity;
return t;
}
/**
* 遍歷當(dāng)前隊(duì)列全部對象
*@date 2017年10月24日 下午5:30:25
*/
public void traverseQueue(){
for (int i = mHead; i < mHead+mLength; i++) {
doSomething((T)mQueue[i%mCapacity]);
}
}
/**
* 具體處理隊(duì)列對象的方法
* 這里使用抽象方法因?yàn)椋? * 對于對象的具體處理邏輯各不相同，所以具體實(shí)現(xiàn)交給用戶自己去完成
*@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();
}
}
因?yàn)槟秸n網(wǎng)的視頻是用c語言寫的，我在簡書上找到了java寫的，代碼來自Rayhaha附上鏈接http://t.cn/RWCfxtF
