|
隊列是嵌入式軟件中常用的一種數(shù)據(jù)結(jié)構(gòu)。什么是隊列呢？在生活中，我們都知道 ，買東西時要排隊，比如最近iphone6開售了，買的人比較多，黃牛倒手機也要排隊 買。先來的人排在隊伍的前面，優(yōu)先購買，購?fù)旰箅x開，后到的人只有排在隊伍的 后面，且只有等前面的人都買好了才能輪到他。這種隊伍的變化狀態(tài)稱為數(shù)據(jù)結(jié)構(gòu) 。 今天我們就來聊一聊隊列的使用及主要運算。隊列只能在一端（隊尾）進入數(shù)據(jù)加 入，在另一端（隊首）進行刪除的數(shù)據(jù)結(jié)構(gòu)。比如對于隊列（d1,d2,d3,…,dn）,d1 是隊首，如果要從隊列中刪除數(shù)據(jù)，只能從d1開始，如果要向隊列中添加新的數(shù)據(jù) ，只能在隊尾加入。 隊列可以通過一維數(shù)組實現(xiàn)，也可以通過鏈表來實現(xiàn)，我們以使用數(shù)組來說明。比 如我們可以定義一個數(shù)組a[100]表示最大長度為100的隊列。當向新建的隊列中加入 數(shù)據(jù)時，從a[0]開始，然后記錄加入的位置，當再次向隊列中加入數(shù)據(jù)時，存放在 a[1]中，依次類推。假如一直向隊列中加入數(shù)據(jù)，當向a[99]加入了數(shù)據(jù)之后，隊列 滿了。不能在之后繼續(xù)加入新的數(shù)據(jù)。假如現(xiàn)在需要從隊列中取數(shù)據(jù)，要從a[0]開 始，下次取a[1],依次類推。 這樣使用的數(shù)組，如果不進行一些其他的運算，數(shù)組最終會被用完。一般我們在使 用時，當隊尾達到數(shù)組結(jié)尾時，將隊尾重新指向數(shù)組的開始，這樣的隊列稱為循環(huán) 隊列。 在使用隊列時，主要會涉及到以下運算。 1、置空隊列：將隊列置成空的隊列。 2、判斷隊列是否空：如果隊列是空隊列，返回真，否則返回假。 3、取頭結(jié)點：讀取隊列中頭結(jié)點的值，隊列中的結(jié)點保持不變。 4、入隊：將數(shù)據(jù)插入到隊列的隊尾。 5、出隊：刪除隊列頭結(jié)點，一般與從隊列中取隊首數(shù)據(jù)同時操作。 隊列空和滿的情況分析 對于循環(huán)隊列來說，假如取數(shù)據(jù)和添加數(shù)據(jù)同時進行，會存在隊列空或者隊列滿的 情況，假如用front來表示隊首在數(shù)組中的下標，用rear表示隊尾在數(shù)組中的下標。 會存在front和rear相等的情況，在這種情況下，只用front和rear的值將無法區(qū)分 當前隊列是滿還是空。 通常我們可以設(shè)置一個標志位來表示隊滿還是隊空，當入隊時設(shè)置flag等于1，出隊 時設(shè)置flag為0，出隊時設(shè)置為0，所以當front和rear相等時，flag等于0則隊空， 否則隊滿。深圳-鄭州-廣州-長沙嵌入式技術(shù)實訓(xùn)學(xué)習(xí)，小班授課，詳情郭老師 QQ754634522 或者使用一個計數(shù)器來記錄隊列中結(jié)點的數(shù)量。當計數(shù)count等于0時隊空。 同樣我們也可以少用一個節(jié)點，將front指向的空間表示為無數(shù)據(jù)。當front等于 rear時，隊空，入隊時，當尾指針加1，等于頭指針，則說明隊列已滿。 下面我們使用第三種方法表示隊滿或隊空，來詳細分析一下隊列的運算 1、置空隊 在隊列初始化時，我們需要將隊列置為空的隊列，當然也可以通過置空隊列也刪除 隊列中的數(shù)據(jù)（不是真正意義上的刪除，只是數(shù)據(jù)無效，可以覆蓋操作）。 將數(shù)組下標0位置設(shè)置為不使用，因此頭尾指針值都是0 void set_null(sequeue *q) { q->front = 0; q->rear =0; } 2、判斷隊空 使用前面的最后一種方法，隊空的判斷條件就是頭指針等于尾指針 int empty(sequeue *q) { if(q->rear == q->front) return 1;//空隊列返回真 else return 0;//非空返回假 } 3、取頭結(jié)點 取出頭結(jié)點，并不刪除頭結(jié)點，隊列信息保持不變，如果是空隊，就提示相關(guān)信息 。 get_front(sequeue *q) { if(empty(q) { printf(“null\n”);return NULL; } else return q->data[(q->front+1)%maxsize];//返回頭結(jié)點 } 4、入隊 入隊時，將新結(jié)點插入到隊尾，隊尾指針加1，但要考慮從數(shù)組最大下標到0的情況 ，還有隊滿不能入隊的情況 int in_queue(sequeue *q,data x) { if((q->rear+1)%maxsize==q->front) return NULL; else { q->rear = (q->rear+1)%maxsize; q->data[q->rear] = x; } } 5、出隊 出隊進行與入隊相反的操作，要刪除隊列中的頭結(jié)點。 data del_queue(sequeue *q) { if(empty(q) return NULL;//返回空指針 else { q->front = (q->front+1)%maxsize; return q->data[q->front]; } } 在實際應(yīng)用中，隊列使用的比較多的地方是操作系統(tǒng)內(nèi)核，當系統(tǒng)任務(wù)比較多時， 需要等待的情況一般都會使用到隊列，在裸機開發(fā)中，我們也可以使用隊列，比如 使用隊列來處理觸摸屏坐標，當點擊速度過快，或者觸摸屏劃動操作時，需要一直 記錄劃過的坐標，這時，如果主循環(huán)處理不完，就需要構(gòu)造隊列。想學(xué)習(xí)嵌入式伙伴可以加群交流132621831 |
