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