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函數，用條件編譯可以將它屏蔽掉。

運行結果：

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