C語言設計前中後隊列實例代碼
隊列基本概念
隊列是最常見的概念,日常生活經常需要排隊,仔細觀察隊列會發現,隊列是一種邏輯結構,是一種特殊的線性表。特殊在:
隻能在固定的兩端操作線性表
隻要滿足上述條件,那麼這種特殊的線性表就會呈現出一種“先進先出”的邏輯,這種邏輯就被稱為隊列。
由於約定瞭隻能在線性表固定的兩端進行操作,於是給隊列這種特殊的線性表的插入刪除,起個特殊的名稱:
隊頭:可以刪除節點的一端
隊尾:可以插入節點的一端
入隊:將節點插入到隊尾之後,函數名通常為enQueue()
出隊:將隊頭節點從隊列中剔除,函數名通常為outQueue()
取隊頭:取得隊頭元素,但不出隊,函數名通常為front()
本題就是手擼數據結構中基本的隊列結構,常用的有兩種,一種是用鏈表實現,一種是數組實現。本文將會給出兩種實現方式
1,數組實現
typedef struct { int value[1000]; int len; } FrontMiddleBackQueue; FrontMiddleBackQueue* frontMiddleBackQueueCreate() { FrontMiddleBackQueue *queue = (FrontMiddleBackQueue *)malloc(sizeof(FrontMiddleBackQueue)); memset(queue,0,sizeof(FrontMiddleBackQueue)); return queue; } void insert(FrontMiddleBackQueue* obj, int pos, int val) { //在pos位置插入val,則pos(從0開始)位置後的數統一向後挪一個位置,隊列長度加1 int i = 0; for(i=obj->len; i>pos; i--) { obj->value[i] = obj->value[i-1]; } obj->value[pos] = val; obj->len++; } int pop(FrontMiddleBackQueue* obj, int pos) { //彈出pos位置的val,則pos(從0開始)位置後向前統一挪一個位置,隊列長度減一 if(obj->len == 0) return -1; int i = 0; int popval = obj->value[pos]; //先將pos位置的數保存下來,不然下面的移位操作就覆蓋瞭pos位置的值 for(i=pos; i<obj->len-1; i++) { obj->value[i] = obj->value[i+1]; } obj->len--; return popval; } void frontMiddleBackQueuePushFront(FrontMiddleBackQueue* obj, int val) { insert(obj,0,val); } void frontMiddleBackQueuePushMiddle(FrontMiddleBackQueue* obj, int val) { insert(obj,obj->len/2,val); } void frontMiddleBackQueuePushBack(FrontMiddleBackQueue* obj, int val) { insert(obj,obj->len,val); } int frontMiddleBackQueuePopFront(FrontMiddleBackQueue* obj) { return pop(obj,0); } int frontMiddleBackQueuePopMiddle(FrontMiddleBackQueue* obj) { return pop(obj,(obj->len-1)/2); } int frontMiddleBackQueuePopBack(FrontMiddleBackQueue* obj) { return pop(obj, obj->len-1); } void frontMiddleBackQueueFree(FrontMiddleBackQueue* obj) { free(obj); } /** * Your FrontMiddleBackQueue struct will be instantiated and called as such: * FrontMiddleBackQueue* obj = frontMiddleBackQueueCreate(); * frontMiddleBackQueuePushFront(obj, val); * frontMiddleBackQueuePushMiddle(obj, val); * frontMiddleBackQueuePushBack(obj, val); * int param_4 = frontMiddleBackQueuePopFront(obj); * int param_5 = frontMiddleBackQueuePopMiddle(obj); * int param_6 = frontMiddleBackQueuePopBack(obj); * frontMiddleBackQueueFree(obj); */
運行結果
2,鏈表實現
1,設計鏈表結構,鏈表維持一個頭節點和尾結點,頭節點始終在最前面並且頭結點的data存儲整個隊列的節點數,尾結點始終是最後一個節點
2,設計插入節點函數和刪除節點函數,push和pop操作隻需要根據不同場景傳入不同的參數即可完成統一的操作
typedef struct tag_Node { int data; struct tag_Node* next, *prev; }Node; typedef struct { Node* front; Node* rear; } FrontMiddleBackQueue; FrontMiddleBackQueue* frontMiddleBackQueueCreate() { FrontMiddleBackQueue* que = (FrontMiddleBackQueue *)malloc(sizeof(FrontMiddleBackQueue)); que->front = (Node *)malloc(sizeof(Node)); que->rear = (Node *)malloc(sizeof(Node)); que->front->data = 0; que->front->next = NULL; que->rear->data = 0; que->rear->next = NULL; que->front->next = que->rear; que->rear->prev = que->front; return que; } void AddNode(FrontMiddleBackQueue* obj, Node *cur, int val) { Node* addNode = (Node *)malloc(sizeof(Node)); addNode->data = val; addNode->prev = cur->prev; addNode->next = cur; cur->prev->next = addNode; cur->prev = addNode; obj->front->data++; return; } Node* GetMiddleNode(FrontMiddleBackQueue* obj, bool isAdd) { Node* tmp = obj->front->next; int len = isAdd ? (obj->front->data / 2) : ((obj->front->data - 1) / 2); for (int i = 0; i < len; i++) { tmp = tmp->next; } return tmp; } void frontMiddleBackQueuePushFront(FrontMiddleBackQueue* obj, int val) { AddNode(obj, obj->front->next, val); return; } void frontMiddleBackQueuePushMiddle(FrontMiddleBackQueue* obj, int val) { AddNode(obj, GetMiddleNode(obj, true), val); return; } void frontMiddleBackQueuePushBack(FrontMiddleBackQueue* obj, int val) { AddNode(obj, obj->rear, val); return; } int RemoveNode(FrontMiddleBackQueue* obj, Node* cur) { if (obj->front->data == 0) { return -1; } cur->next->prev = cur->prev; cur->prev->next = cur->next; obj->front->data--; int item = cur->data; free(cur); return item; } int frontMiddleBackQueuePopFront(FrontMiddleBackQueue* obj) { return RemoveNode(obj, obj->front->next); } int frontMiddleBackQueuePopMiddle(FrontMiddleBackQueue* obj) { return RemoveNode(obj, GetMiddleNode(obj, false)); } int frontMiddleBackQueuePopBack(FrontMiddleBackQueue* obj) { return RemoveNode(obj, obj->rear->prev); } void frontMiddleBackQueueFree(FrontMiddleBackQueue* obj) { while (RemoveNode(obj, obj->front->next) != -1); free(obj->front); free(obj->rear); free(obj); return; } /** * Your FrontMiddleBackQueue struct will be instantiated and called as such: * FrontMiddleBackQueue* obj = frontMiddleBackQueueCreate(); * frontMiddleBackQueuePushFront(obj, val); * frontMiddleBackQueuePushMiddle(obj, val); * frontMiddleBackQueuePushBack(obj, val); * int param_4 = frontMiddleBackQueuePopFront(obj); * int param_5 = frontMiddleBackQueuePopMiddle(obj); * int param_6 = frontMiddleBackQueuePopBack(obj); * frontMiddleBackQueueFree(obj); */
運行結果:
總結
到此這篇關於C語言設計前中後隊列的文章就介紹到這瞭,更多相關C語言設計前中後隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!