1.队列
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先
进先出FIFO(First In First Out)
- 入队列:进行插入操作的一端称为队尾
- 出队列:进行删除操作的一端称为队头
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,
出队列在数组头上出数据,效率会比较低。
2.链表实现队列
链表实现队列,需要用到链表进行连接,但队列只用链表的头和尾。
2.1队列的表示
typedef struct QListNode //链表实现队列的节点
{struct QListNode* _pNext;QDataType _data;
}QNode;typedef struct Queue // 队列的结构只有头尾的节点
{QNode* _front;QNode* _rear;
}Queue;
2.2 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
2.3 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
2.4 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}
2.5 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}
2.6 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->tail);return pq->tail->data;
}
2.7 获取队列中有效元素个数
size_t QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;
}
2.8 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->head == NULL && pq->tail == NULL;return pq->head == NULL;
}
2.9 销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}