C++数据结构的队列详解

第C++数据结构的队列详解hello，大家好，这期文章我们来分享数据结构关于队列的知识。希望对大家有所帮助，闲言少叙，现在开始。

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstInFirstOut)入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

2.队列的实现

2.1queue.h

#includestdio.h

#includestdbool.h

#includeassert.h

#includemalloc.h

typedefintQDataType;

typedefstructQueueNode

structQueueNode*next;

QDataTypedata;

}QueueNode;

typedefstructQueue

QueueNode*head;

QueueNode*tail;

}Queue;

voidQueueInit(Queue*pq);

voidQueueDestory(Queue*pq);

voidQueuePush(Queue*pq,QDataTypex);

voidQueuePop(Queue*pq);

QDataTypeQueueFront(Queue*pq);

QDataTypeQueueBack(Queue*pq);

boolQueueEmpty(Queue*pq);

intQueueSize(Queue*pq);

2.2queue.c

#includequeue.h

voidQueueInit(Queue*pq)

assert(pq);

pq-head=pq-tail=NULL;

voidQueueDestory(Queue*pq)

assert(pq);

QueueNode*cur=pq-head;

while(cur)

QueueNode*next=cur-next;

free(cur);

cur=next;

pq-head=pq-tail=NULL;

voidQueuePush(Queue*pq,QDataTypex)

assert(pq);

QueueNode*newnode=(QueueNode*)malloc(sizeof(QueueNode));

if(newnode==NULL)

printf(mallocfail\n

exit(-1);

newnode-data=x;

newnode-next=NULL;

if(pq-tail==NULL)

pq-head=pq-tail=newnode;

else

pq-tail-next=newnode;

pq-tail=newnode;

voidQueuePop(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

if(pq-head-next==NULL)

free(pq-head);

pq-head=pq-tail=NULL;

else

QueueNode*next=pq-head-next;

free(pq-head);

pq-head=next;

QDataTypeQueueFront(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-head-data;

QDataTypeQueueBack(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-tail-data;

boolQueueEmpty(Queue*pq)

assert(pq);

returnpq-head==NULL;

intQueueSize(Queue*pq)

intsize=0;

QueueNode*cur=pq-head;

while(cur)

QueueNode*next=cur-next;

++size;

cur=cur-next;

returnsize;

2.3test.c

#includequeue.h

voidTestOne()

Queueq;

QueueInit(

QueuePush(q,1);

QueuePush(q,2);

QueuePush(q,3);

QueuePush(q,4);

while(!QueueEmpty(q))

printf(%d,QueueFront(q));

QueuePop(