程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言連續存儲實現隊列機制

C語言連續存儲實現隊列機制

編輯:關於C語言

所謂隊列,就是如同生活中的隊列一樣,擁有以下性質:

1).每次加入一個元素時,必須在隊尾加入

2).每次拿走一個元素時,必須從對頭拿走

總結起來也就是先進先出,後進後出。

從存儲上看,隊列有兩種實現方式,一個是連續存儲,一個是離散存儲。連續存儲就類似於數組,而離散存儲就類似於鏈表,這裡我們先實現比較簡單的連續存儲:

由於隊列的操作可以在對頭也可以在隊尾,也就是說他可以在兩端操作,這樣我們就要用兩個參數來描述:head和tail。一個指向對頭,一個指向隊尾的下一個。

這裡說明一下,由於當隊列為空時head=tial,而當隊列滿時head=tail,這樣就出現了二義性。為了避免二義性,我們規定tail指向隊尾的下一個元素,這樣一來當隊列

為空的時候,head=tail,而當隊列為滿時,tail+1=head。也就是說如果我們有N個空間,那我們只能使用N-1個,要留一個給tail。在head和tail移動的時候,我們也不是

簡單地對他們加1,而是將他們加1之後對N取模,這樣就可以循環得到從0~N-1的數了。

具體的實現,請看源代碼:

/*************************************************************************
	> File Name: sequeue.c
	> Author: Baniel Gao
	> Mail: [email protected] 
	> Blog: blog.csdn.net/createchance 
	> Created Time: Fri 20 Dec 2013 11:57:32 AM CST
 ************************************************************************/
#include 
#include 

#define _DEBUG_ 1

typedef struct _sequeue_ {
	int total;
	int head;
	int tail;
	int *data;
} sequeue_st;

sequeue_st *sequeue_init(int size);
int sequeue_enqueue(sequeue_st *queue, int value);
int sequeue_isfull(sequeue_st *queue);
int sequeue_dequeue(sequeue_st *queue);
int sequeue_isempty(sequeue_st *queue);
int sequeue_free(sequeue_st *queue);
#if _DEBUG_
int sequeue_debug(sequeue_st *queue);
#endif

int main(void)
{
	sequeue_st *queue;
	int size = 10;
	int value = 100;
	
	queue = sequeue_init(size);
	while (-1 != sequeue_enqueue(queue, value))
		value++;
#if _DEBUG_
	printf("After enqueue......\n");
	sequeue_debug(queue);
#endif

	while (-1 != sequeue_dequeue(queue))
		value++;
#if _DEBUG_
	printf("After dequeue......\n");
	sequeue_debug(queue);
#endif

	sequeue_free(queue);

	return 0;
}

sequeue_st *sequeue_init(int size)
{
	sequeue_st *queue = NULL;

	queue = (sequeue_st *)malloc(sizeof(sequeue_st));
	queue->head = 0;
	queue->tail = 0;
	queue->total = size;
	queue->data = (int *)malloc(sizeof(int) * size);

	return queue;
}

int sequeue_enqueue(sequeue_st *queue, int value)
{
	if (sequeue_isfull(queue))
		return -1;
	queue->data[queue->tail] = value;
	queue->tail = (queue->tail + 1) % queue->total;

	return 0;
}

int sequeue_dequeue(sequeue_st *queue)
{
	if (sequeue_isempty(queue))
		return -1;
	queue->head = (queue->head + 1) % queue->total;

	return 0;
}

int sequeue_isempty(sequeue_st *queue)
{
	if (queue->tail == queue->head)
		return 1;
	return 0;
}

int sequeue_isfull(sequeue_st *queue)
{
	if ((queue->tail + 1) % queue->total == queue->head)
		return 1;
	return 0;
}

int sequeue_free(sequeue_st *queue)
{
	free(queue->data);
	free(queue);

	return 0;
}

int sequeue_debug(sequeue_st *queue)
{
	int index;

	puts("------------------------ DEBUG ----------------------");
	printf("total = %d\thead = %d\ttail = %d\n", queue->total, queue->head, queue->tail);
	puts("-----------------------------------------------------");
	for (index = 0; index < queue->total; index++)
		printf("%5d", queue->data[index]);
	puts("\n-----------------------------------------------------");

	return 0;
}

這裡我為了方便對隊列的控制於查看,我定義了一個debug函數,用條件編譯可以將它屏蔽掉。

運行結果:


這樣可以清楚的看到入隊和出隊的操作。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved