队列的概念及结构

队列和栈略有不同，队列是先进后出的一种数据结构，通常使用链表来表示，当然有一种特殊的循环队列使用顺序表来进行表示的。
队列只允许从后进入，从前弹出，就像我们生活中排队一样，下面来看下队列的结构模型：

如上图，队列是只有队头才能删除元素（出队），队尾才能插入元素（入队），由此可以得出数据结构为：

typedef int QDataType;
//定义结点的结构体
typedef struct QNode
{QDataType val; strcut QNode* next;
}QNode；
//定义队列的结构体
typedef struct Queue
{QNode* head;  //队头指针QNode* tail;   //队尾指针
}Queue;

队列代码实现

初始化

void QueueInit(Queue* Q)
{Q->head = Q->tail = NULL;
}

创建节点

QNode* CreateQNode(QDataType data)
{QNode* node = (QNode*)malloc(sizeof(QNode));node->next = NULL;node->data = data;return node;
}

入队

void QueuePush(Queue* Q, QDataType data)
{QNode* node = CreateQNode(data);if (!Q->head){Q->head = Q->tail = node;}Q->tail->next = node;Q->tail = node;
}

出队

void QueuePop(Queue* Q)
{if (!Q->head){return;}QNode* next = Q->head->next;free(Q->head);Q->head = next;if (!Q->head){Q->tail = NULL;}
}

获取队首元素

QDataType QueueHeadElement(Queue* Q)
{return Q->head->data;
}

获取队尾元素

QDataType QueueTailElement(Queue* Q)
{return Q->tail->data;
}

队列元素个数

int QueueSize(Queue* Q)
{int count = 0;QNode* cur = Q->head;while (cur){cur = cur->next;count++;}return count;
}

判空

int QueueEmpty(Queue* Q)
{if (!Q->head){return 1;}return 0;
}

销毁

void QueueDestroy(Queue* Q)
{QNode* next;while (Q->head){next = Q->head->next;free(Q->head);Q->head = next;}
}