C語言數據結構算法基礎之循環隊列示例

Posted on by

說明

循環隊列是一種先進先出的，首尾相連的隊列。

大致的結構如下圖：

用數組來抽象的表示一下的話，如下圖：

循環隊列有兩個指針指向數據，上圖中的start和end就是那兩個指針，它們指向相同的位置，表示的是空，即隊列是空的。

隨著數據的放入，隊列一般有下面的兩種形式：

需要註意第二種形式，從圖上看end在start的前面瞭，但是因為循環關系，前後並不重要。

另外需要考慮的是隊列滿的情況：

但這種情況存在一個問題，即空隊列和滿隊列沒有辦法區分瞭，end和start都指向瞭相同的位置。

為瞭解決這個問題，一個方法是空出一個位置不放數據，當end再加一個數據就等於start的時候就認為隊列是滿的：

這時實際的數據長度就會比分配的少1。

下面是隊列中空和滿的判斷：

1. 隊列為空時：end == start

2. 隊列為滿時：(end + 1) % size == start

這裡的size是指分配的空間大小，而不是隊列長度，隊列的實際長度為(end – start + size) % size，最大長度是size-1

這也是因為要考慮循環的關系，所以要加上%size這個操作。

示例代碼

1. 首先定義結構體：

//定義循環隊列
typedef struct _LoopQueue {
	int data[8];		//存放數據
	int start;		//頭指針
	int end;		//尾指針
} LoopQueue;

2. 定義各種算法：

#define TRUE	1
#define FALSE	0
#define SIZE	8
//初始化隊列
int init(LoopQueue *lq) {
	lq->start = 0;
	lq->end = 0;
	return TRUE;
}
//判斷隊列是否為空
int isEmpty(LoopQueue *lq) {
	if (lq->start == lq->end) {
		return TRUE;
	}
	return FALSE;
}
//判斷隊列是否為滿
int isFull(LoopQueue *lq) {
	if ((lq->end + 1) % SIZE == lq->start) {
		return TRUE;
	}
	return FALSE;
}
//獲取隊列的長度
int getLength(LoopQueue *lq) {
	return (lq->end - lq->start + SIZE) % SIZE;
}
//插入數據
int pushQueue(LoopQueue *lq, int data) {
	if(isFull(lq)) {
		printf("Queue is full.\n");
		return FALSE;
	}
	lq->data[lq->end] = data;
	lq->end = (lq->end + 1) % SIZE;
	return TRUE;
}
//彈出數據
int popQueue(LoopQueue *lq, int *data) {
	if (isEmpty(lq)) {
		printf("Queue is empty.\n");
		return FALSE;
	}
	*data = lq->data[lq->start];
	lq->start = (lq->start + 1) % SIZE;
	return TRUE;
}
//顯示隊列中的數據
void printQueue(LoopQueue *lq) {
	int index;
	int count;
	count = getLength(lq);
	if (0 == count) {
		printf("No data.\n");
		return;
	}
	for (index = 0; index < count; index++) {
		printf("%d ", lq->data[index]);
	}
	printf("\n");
	return;
}

3. 測試：

int main()
{
	int index;
	int num;
	//隊列測試代碼
	LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue));
	init(lq);
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//註意這裡要放8個數據，但是實際上隻能放7個，所以最後一個會報錯
		pushQueue(lq, index);
	}
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//同上，會打印一個錯誤
		if (popQueue(lq, &num)) {
			printf("%d\n", num);
		}
	}
	printQueue(lq);
	return 0;
}

4. 最後的結果：

以上就是C語言數據結構算法基礎之循環隊列的詳細內容，更多關於C語言數據結構算法循環隊列的資料請關註WalkonNet其它相關文章！

推薦閱讀：