文章目錄

• 隊列
• • 1.概念
  • 2. 生活中隊列應(yīng)用
  • 3. 隊列的實現(xiàn)
  • • 初始化隊列
    • 入隊列
    • 出隊列
    • 獲取隊頭元素
    • 獲取隊尾元素
    • 獲取隊列中元素個數(shù)
    • 判斷隊列是否為空
    • 銷毀隊列
  • 2. 循環(huán)隊列

創(chuàng)新互聯(lián)建站專注于成安網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供成安營銷型網(wǎng)站建設(shè)，成安網(wǎng)站制作、成安網(wǎng)頁設(shè)計、成安網(wǎng)站官網(wǎng)定制、重慶小程序開發(fā)服務(wù)，打造成安網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供成安網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

---

隊列 1.概念

和棧相反，隊列(queue)是一種先進先出的線性表，它只允許在一端進行插入，而在另一端被刪除。這和生活中的排隊是類似的，最先排隊的最先離開。在隊列中運行被插入的一端叫做隊尾，允許被刪除的一端叫做隊尾。

2. 生活中隊列應(yīng)用

比如我們?nèi)ャy行辦理業(yè)務(wù)的時候需要去抽號機器上取一個號碼，這起始就是隊列的應(yīng)用。每當有一個人取號后機器就會把這個號碼入隊列進行排隊。等窗口工作人員進行叫號辦理業(yè)務(wù)。

3. 隊列的實現(xiàn)

隊列可以用數(shù)組或者鏈表實現(xiàn)，使用鏈表實現(xiàn)會更加合適一些，因為如果使用數(shù)組實現(xiàn)在出隊的時候效率會比較低。

隊列的定義

因為是鏈表實現(xiàn)所以還要定義一個節(jié)點結(jié)構(gòu)體，隊列的結(jié)構(gòu)題包含兩個指針一個隊頭指針和一個隊尾指針

typedef int QDataType;

typedef struct QListNode {QDataType data;
	struct QListNode* next;//下一個節(jié)點
}QNode;

typedef struct Queue
{QNode* front;//隊頭
	QNode* rear;//隊尾
}Queue;

// 初始化隊列
void QueueInit(Queue* q);
// 動態(tài)申請節(jié)點
QNode* BuyQNode(QDataType data);
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);

初始化隊列

初始化隊列比較簡單，讓隊頭和隊尾指向NULL，因為此時隊列里沒有任何元素。

// 初始化隊列
void QueueInit(Queue* q)
{assert(q);
	q->front = NULL;
	q->rear = NULL;
}

因為這是鏈表實現(xiàn)所以還要定義個動態(tài)申請節(jié)點的函數(shù)

// 動態(tài)申請節(jié)點
QNode* BuyQNode(QDataType data)
{QNode* node = (QNode*)(malloc(sizeof(QNode)));
	if (node == NULL)
	{printf("申請失敗\n");
		exit(-1);
	}
	node->data = data;
	node->next = NULL;
	return node;
}

入隊列

入隊列需要考慮兩種情況，第一種是隊列為空的情況，隊列為空要把隊頭和隊尾指針都指向第一個元素，其他情況只需要把節(jié)點插入到隊尾指針后面，再讓對隊尾指針往后走即可。

// 隊尾入隊列
void QueuePush(Queue* q, QDataType data)
{assert(q);
	QNode* node = BuyQNode(data);
	if (q->front == NULL)
	{q->front = node;
		q->rear = node;
	}
	else
	{q->rear->next = node;
		q->rear = q->rear->next;
	}
}

出隊列

出隊列要考慮到隊列是否為空，為空是不能進行出隊列操作的。出隊列只需要讓隊頭指針往后走，再釋放隊頭節(jié)點。

// 隊頭出隊列
void QueuePop(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	QNode* cur = q->front;
	q->front = q->front->next;
	free(cur);
}

獲取隊頭元素

// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}

獲取隊尾元素

// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}

獲取隊列中元素個數(shù)

和鏈表求長度是一樣的

// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q)
{assert(q);

	QNode* cur = q->front;
	int count = 0;
	while (cur != NULL)
	{count++;
		cur = cur->next;
	}
	
	return count;
}

判斷隊列是否為空

當隊頭指向NULL時說明隊列為空

// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);
	
	return q->front == NULL;
}

銷毀隊列

銷毀隊列遍歷一邊隊列，把每個節(jié)點給釋放掉。

// 銷毀隊列
void QueueDestroy(Queue* q)
{assert(q);
	QNode* cur = q->front;
	while (cur != NULL)
	{q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = NULL;
	q->rear = NULL;
}

2. 循環(huán)隊列

循環(huán)隊列也是一種隊列，再隊列的順序存儲結(jié)構(gòu)中，除了用一組連續(xù)的存儲單元依次存放隊頭到隊尾元素外，還需要兩指針 front 和 rear 分別指向隊頭和隊尾。

我們約定，初始化空隊列時，讓 front 和 rear 都賦為0，也就是指向數(shù)組的0下標。每當插入元素時尾指針加1，每當刪除元素時頭指針加1。

因為這時一個循環(huán)隊列，當 f r o n t = = r e a r front == rear front==rear時，無法判斷循環(huán)是滿還是空。所以可以有兩種選擇，一種是做一個標記判斷是否為滿了，而是創(chuàng)建隊列的時候多開一個空間，浪費掉這個空間方便判斷。

我們采用第二種方式，約定 f r o n = = r e a r fron == rear fron==rear表示隊列為空， r e a r + 1 = = f r o n rear+1 == fron rear+1==fron表示隊列滿了。

還有一個問題就是這是一個循環(huán)隊列，當尾指針走到最后一個位置時如何走到下標為0的位置，我們可以巧妙的用一個公式，假設(shè)隊列大小為 size。

頭指針向后走： ( f r o n + 1 ) % s i z e (fron+1)\%size (fron+1)%size

尾指針向后走： ( r e a r + 1 ) % s i z e (rear + 1)\%size (rear+1)%size

代碼實現(xiàn)

typedef struct {int* arr;
    int front;
    int rear;
    int size;//容量
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* QUeue(int k) {MyCircularQueue* obj = (MyCircularQueue*)(malloc(sizeof(MyCircularQueue)));

    //創(chuàng)建容量為k+1大小的隊列，浪費1個空間
    obj->arr = (int*)(malloc(sizeof(int)*(k+1)));
    obj->front = 0;
    obj->rear = 0;
    obj->size = k+1;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj) == true)
    {return false;//滿了
    }
    else
    {obj->arr[obj->rear] = value;
        obj->rear = (obj->rear+1) % (obj->size);
        return true;
    }

    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return false;
    }
    else
    {obj->front = (obj->front+1) % (obj->size);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj) == true)
    {return -1;
    }
    return obj->arr[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return -1;
    }
    return (obj->rear == 0) ? (obj->arr[obj->size-1]) : (obj->arr[obj->rear-1]);
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//約定 頭位相遇就是空，尾+1是頭就是滿
    if (obj->front == obj->rear)
    {return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {//約定 頭位相遇就是空，尾+1是頭就是滿
    if (((obj->rear)+1)%obj->size == (obj->front))
    {return true;
    }
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);
    obj->front = NULL;
    obj->rear = NULL;
    free(obj);
}

---

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：數(shù)據(jù)結(jié)構(gòu)C語言版——隊列+循環(huán)隊列實現(xiàn)-創(chuàng)新互聯(lián)
文章起源：http://weahome.cn/article/dsdhcp.html