线性队列和线性堆栈有点相似,但队列里面的数据是“先进先出”。实际应用时大多是采用循环队列,关于队列的循环实现,需要两件事情要警惕:1、检测队列是否为空;2、检测队列是否已满。下面就简单的介绍循环队列的一些基本操作
1、队列的数据节点
typedef struct _Queue { int *pData; //数据域指针 int capacity; //队列容量 int front; //队列首位置 int rear; //队列尾位置 int count; //队列数据量 }Queue;2、创建指定容量队列
Queue* createQueue(int num) { Queue *pQueue = NULL; if (0 == num) return NULL; pQueue = (Queue *)malloc(sizeof(Queue)); //开辟队列节点 assert(NULL != pQueue); memset(pQueue,sizeof(Queue)); pQueue->pData = (int *)malloc(sizeof(int)* num); //开辟数据域空间 if (NULL == pQueue->pData) { free(pQueue); //数据域开辟失败,释放队列节点空间 pQueue = NULL; return NULL; } pQueue->capacity = num; //指定容量 return pQueue; }3、判断队列空,满
bool isFull(Queue *pQueue) { return (pQueue->count == pQueue->capacity); } bool isEmpty(Queue *pQueue) { return (0 == pQueue->count); }4、入队列
线性循环队列等效认为数据域是一个环的数组空间,这样在入队列的时候,队列尾位置(实际上队列并没有严格的首尾之分)为(rear + 1) mod capacity。而不是简单的进行加1处理
bool enQueue(Queue *pQueue,int value) { if (NULL == pQueue) return false; if (isFull(pQueue)) return false; pQueue->pData[pQueue->rear] = value; pQueue->rear = (pQueue->rear + 1) % pQueue->capacity; pQueue->count++; return true; }5、出队列
bool deQueue(Queue *pQueue,int *value) { if (NULL == pQueue) return false; if (isEmpty(pQueue)) return false; *value = pQueue->pData[pQueue->front]; pQueue->count--; pQueue->front = (pQueue->front + 1) % pQueue->capacity; return true; }了解队列的特点,出队列的时候,是弹出队列前端数据
6、释放队列
采用二级指针传递是在释放内存后,将队列指针设置为NULL,便于之后的基本操作的参数判断。使用一级指针也可释放内存
bool freeQueue(Queue **ppQueue) { if ((NULL == ppQueue) || (NULL == *ppQueue)) return false; if (NULL == (*ppQueue)->pData) { free(*ppQueue); *ppQueue = NULL; return true; } free((*ppQueue)->pData); (*ppQueue)->pData = NULL; free(*ppQueue); *ppQueue = NULL; return true; }7、打印队列数据
void printQueue(Queue *pQueue) { if (pQueue) { int i = pQueue->front; int cnt = pQueue->count; while (0 != cnt) { printf("%d\n",pQueue->pData[(i++) % pQueue->capacity]); --cnt; } return; } }设计循环队列数据结构比较简单,需要注意的就是数据域循环的“环”的处理。