快捷導(dǎo)航

C語言設(shè)計(jì)前中后隊(duì)列實(shí)例代碼

更新時(shí)間：2021年12月20日 12:06:44 作者：ftzchina

隊(duì)列最主要的作用就是用來管理數(shù)據(jù)流的,防止數(shù)據(jù)因?yàn)閭鬏旑l率過快得不到及時(shí)處理而丟失,下面這篇文章主要給大家介紹了關(guān)于C語言設(shè)計(jì)前中后隊(duì)列的相關(guān)資料,需要的朋友可以參考下

隊(duì)列基本概念

隊(duì)列是最常見的概念，日常生活經(jīng)常需要排隊(duì)，仔細(xì)觀察隊(duì)列會(huì)發(fā)現(xiàn)，隊(duì)列是一種邏輯結(jié)構(gòu)，是一種特殊的線性表。特殊在：

只能在固定的兩端操作線性表

只要滿足上述條件，那么這種特殊的線性表就會(huì)呈現(xiàn)出一種“先進(jìn)先出”的邏輯，這種邏輯就被稱為隊(duì)列。

由于約定了只能在線性表固定的兩端進(jìn)行操作，于是給隊(duì)列這種特殊的線性表的插入刪除，起個(gè)特殊的名稱：

隊(duì)頭：可以刪除節(jié)點(diǎn)的一端

隊(duì)尾：可以插入節(jié)點(diǎn)的一端

入隊(duì)：將節(jié)點(diǎn)插入到隊(duì)尾之后，函數(shù)名通常為enQueue()

出隊(duì)：將隊(duì)頭節(jié)點(diǎn)從隊(duì)列中剔除，函數(shù)名通常為outQueue()

取隊(duì)頭：取得隊(duì)頭元素，但不出隊(duì)，函數(shù)名通常為front()

本題就是手?jǐn)]數(shù)據(jù)結(jié)構(gòu)中基本的隊(duì)列結(jié)構(gòu)，常用的有兩種，一種是用鏈表實(shí)現(xiàn)，一種是數(shù)組實(shí)現(xiàn)。本文將會(huì)給出兩種實(shí)現(xiàn)方式

1，數(shù)組實(shí)現(xiàn)

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開始)位置后的數(shù)統(tǒng)一向后挪一個(gè)位置,隊(duì)列長度加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開始)位置后向前統(tǒng)一挪一個(gè)位置，隊(duì)列長度減一
    if(obj->len == 0)
        return -1;
    int i = 0;
    int popval = obj->value[pos]; //先將pos位置的數(shù)保存下來，不然下面的移位操作就覆蓋了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);
*/

運(yùn)行結(jié)果

?2，鏈表實(shí)現(xiàn)

1，設(shè)計(jì)鏈表結(jié)構(gòu)，鏈表維持一個(gè)頭節(jié)點(diǎn)和尾結(jié)點(diǎn)，頭節(jié)點(diǎn)始終在最前面并且頭結(jié)點(diǎn)的data存儲(chǔ)整個(gè)隊(duì)列的節(jié)點(diǎn)數(shù)，尾結(jié)點(diǎn)始終是最后一個(gè)節(jié)點(diǎn)

2，設(shè)計(jì)插入節(jié)點(diǎn)函數(shù)和刪除節(jié)點(diǎn)函數(shù)，push和pop操作只需要根據(jù)不同場景傳入不同的參數(shù)即可完成統(tǒng)一的操作

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);
*/

運(yùn)行結(jié)果：