增加了front和rear后的顺序队列_队列front 和 rear

有了front使得取出顺序队列首元素的操作不用再移动后面的数据元素节点，时间复杂度变为O（1）；有了rear使得链式队列的插入操作不用遍历整个队列，时间复杂度也是O（1）

头文件

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__
 
typedef void SeqQueue;
 
SeqQueue* SeqQueue_Create(int capacity);
 
void SeqQueue_Destroy(SeqQueue* queue);
 
void SeqQueue_Clear(SeqQueue* queue);
 
int SeqQueue_Append(SeqQueue* queue, void* item);
 
void* SeqQueue_Retrieve(SeqQueue* queue);
 
void* SeqQueue_Header(SeqQueue* queue);
 
int SeqQueue_Length(SeqQueue* queue);
 
int SeqQueue_Capacity(SeqQueue* queue);
 
 
#endif

模块文件

#include <malloc.h>
#include "SeqQueueV2.h"
 
typedef unsigned int TSeqQueueNode;
 
typedef struct _tag_SeqQueue{
	int capacity;
	int length;
	int front;//指向队列头部，实质是一个下标 
	int rear;//指向队列尾部，实质是一个下标 
	TSeqQueueNode* node;
}TSeqQueue;
 
 
SeqQueue* SeqQueue_Create(int capacity)
{
	TSeqQueue* ret = NULL;
	if(capacity > 0){
		ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode)*capacity);
	}
	if(ret != NULL){
		ret->capacity = capacity;
		ret->length = 0;
		ret->front = 0;//一开始的时候都为0 
		ret->rear = 0;
		ret->node = (TSeqQueueNode*)(ret+1);//通过指针运算使得node指向真正的数据元素节点 
	}
	return ret;
}
 
void SeqQueue_Destroy(SeqQueue* queue)
{
	free(queue);	
}
 
void SeqQueue_Clear(SeqQueue* queue)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	
	if(sQueue != NULL){
		sQueue->length = 0;
		sQueue->front = 0;
		sQueue->rear = 0;
	}
}
 
int SeqQueue_Append(SeqQueue* queue, void* item)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	int ret = (sQueue != NULL) && (item !=NULL) && (sQueue->length < sQueue->capacity);
	
	if(ret){
		sQueue->node[sQueue->rear] = (TSeqQueueNode)item;
		
		sQueue->rear = (sQueue->rear + 1) % sQueue->capacity;//注意这个技巧，循环使用队列中的空间 
		
		sQueue->length++;
	}
	return ret; 
}
 
void* SeqQueue_Retrieve(SeqQueue* queue)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	void* ret = SeqQueue_Header(queue);
	
	if(sQueue != NULL){
		sQueue->front = (sQueue->front + 1) % sQueue->capacity;注意这个技巧，循环使用队列中的空间 
		sQueue->length--;	
	}
	return ret;
	
}
 
void* SeqQueue_Header(SeqQueue* queue)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	void* ret = NULL;
	
	if((sQueue != NULL) && (sQueue->length > 0)){
		ret = (void*)(sQueue->node[sQueue->front]);//注意类型转换 
	}
	return ret;
	
}
 
int SeqQueue_Length(SeqQueue* queue)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	int ret = -1;
	
	if(sQueue != NULL){
		ret = (sQueue->length);
	}
	return ret;
	
}
 
int SeqQueue_Capacity(SeqQueue* queue)
{
	TSeqQueue* sQueue = (TSeqQueue*)queue;
	int ret = -1;
	
	if(sQueue != NULL){
		ret = (sQueue->capacity);
	}
	return ret;
		
}

#include <stdio.h>
#include <stdlib.h>
#include "SeqQueueV2.h"
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
 
int main(int argc, char *argv[]) 
{
    SeqQueue* queue = SeqQueue_Create(6);
    int a[10] = {0};
    int i = 0;
    
    for(i=0; i<10; i++)
    {
        a[i] = i + 1;
        
        SeqQueue_Append(queue, a + i);
    }
    
    printf("Header: %d\n", *(int*)SeqQueue_Header(queue));
    printf("Length: %d\n", SeqQueue_Length(queue));
    printf("Capacity: %d\n", SeqQueue_Capacity(queue));
    
    while( SeqQueue_Length(queue) > 0 )
    {
        printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
    }
    
    printf("\n");
    
    for(i=0; i<10; i++)
    {
        a[i] = i + 1;
        
        SeqQueue_Append(queue, a + i);
 
        printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
    }
    
    SeqQueue_Destroy(queue);
    
	return 0;
}