队列基本操作 |
您所在的位置:网站首页 › 队列排列路 › 队列基本操作 |
1.队列的概念 只允许在一端插入数据操作,在另一端进行删除数据操作的特殊线性表;进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列);队列具有先进先出(FIFO)的特性。 2.顺序队列 (1)队头不动,出队列时队头后的所有元素向前移动 (2)队头移动,出队列时队头向后移动一个位置 3.循环队列 4.链式队列 链式队列:特殊的单链表,只在单链表上进行头删尾插的操作 ***【1.定义一个队列结构体】***】 由于是链式队列,所以先定义一个存放数据域和指针域的结构体队列结构体中定义一个队头指针和队尾指针 typedef int QElemType; //typedef struct BTNode* QElemType; typedef struct QNode { QElemType data; struct QNode *_pNext; }QNode; typedef struct LQueue { QNode *pFront; QNode *pRear; }LQueue;【2.创建新结点】 //创建新结点 static QNode *BuyLQNode(QElemType data) { QNode *pLQNode = (QNode *)malloc(sizeof(QNode)); if (NULL == pLQNode) { printf("申请空间失败!\n"); assert(pLQNode); } pLQNode->data = data; pLQNode->_pNext = NULL; return pLQNode; }【3.初始化队列】 让队列的队头,队尾分别指向空 void LQueueInit(LQueue *q) { assert(q); q->pFront = q->pRear = NULL; }【4.入队列】 【5.出队列】 【6.返回队头元素】 直接返回队头元素 QElemType LQueueTop(LQueue *q) { assert(q); return q->pFront->data; }【7.返回队尾元素】 直接返回队尾元素 QElemType LQueueBack(LQueue *q) { assert(q); return q->pRear->data; }【8.计算队列长度】 定义一个变量count将队列从头到尾遍历,每访问一个元素count加1一下最后count的值就是队列长度 int LQueueSize(LQueue *q) { int count = 0; QNode *pCur; assert(q); pCur = q->pFront; while (pCur) { pCur = pCur->_pNext; count++; } return count; }【9.队列判空操作】 int LQueueEmpty(LQueue *q) { return NULL == q->pFront; }5.完整代码块 /*****************************************/ //LQueue.h typedef int QElemType; //typedef struct BTNode* QElemType; typedef struct QNode { QElemType data; struct QNode *_pNext; }QNode; typedef struct LQueue { QNode *pFront; QNode *pRear; }LQueue; //初始化 void LQueueInit(LQueue *q); //入队列 void LQueuePush(LQueue *q, QElemType data); //出队列 void LQueuePop(LQueue *q); //返回队头元素 QElemType LQueueTop(LQueue *q); //返回返回队列长度 int LQueueSize(LQueue *q); //队列是否为空 int LQueueEmpty(LQueue *q); /************************************************/ //LQueue.c #include #include #include //创建新结点 static QNode *BuyLQNode(QElemType data) { QNode *pLQNode = (QNode *)malloc(sizeof(QNode)); if (NULL == pLQNode) { printf("申请空间失败!\n"); assert(pLQNode); } pLQNode->data = data; pLQNode->_pNext = NULL; return pLQNode; } //初始化 void LQueueInit(LQueue *q) { assert(q); q->pFront = q->pRear = NULL; } //入队列 void LQueuePush(LQueue *q, QElemType data) { assert(q); if (NULL == q->pFront) { q->pFront = q->pRear = BuyLQNode(data); return; } q->pRear->_pNext = BuyLQNode(data); q->pRear = q->pRear->_pNext; } //出队列 void LQueuePop(LQueue *q) { assert(q); QNode *pDel; if (NULL == q->pFront) { return; } if (q->pFront == q->pRear) { q->pRear = NULL; } pDel = q->pFront; q->pFront = q->pFront->_pNext; free(pDel); } //返回队头元素 QElemType LQueueTop(LQueue *q) { assert(q); return q->pFront->data; } //返回队尾元素 QElemType LQueueBack(LQueue *q) { assert(q); return q->pRear->data; } //返回返回队列长度 int LQueueSize(LQueue *q) { int count = 0; QNode *pCur; assert(q); pCur = q->pFront; while (pCur) { pCur = pCur->_pNext; count++; } return count; } //队列是否为空 int LQueueEmpty(LQueue *q) { return NULL == q->pFront; } |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |