数据结构：队列的完整实现

队列的完整实现

1. 队列的概念及其结构

1.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出（FIFO, First In First Out）的特性

• 入队列：进行插入操作的一端称为队尾，入队常被称为 push
• 出队列：进行删除操作的一端称为队头，出队常被称为 pop

1.2 组织结构

• 队列可以使用数组和链表的结构实现，使用链表的结构实现更优一些。
• 因为如果使用数组的结构，出队列时，在数组头上出数据，效率会比较低
• 而对于链表实现的队列来说，入队对应尾插操作，出队对应头删操作。在链表中，头删和尾插操作只需要 O(1) 时间复杂度，因此队列更适合使用链表来实现，本文我们采用单链表来实现。

2. 队列的实现

接口一览

//初始化 与 销毁队列
void QueueInit(Queue* pQueue);
void QueueDestroy(Queue* pQueue);
// 队尾入队列 队头出队列
void QueuePush(Queue* pQueue, QDataType data);
void QueuePop(Queue* pQueue);
// 获取队列头部元素 /获取队列尾部元素
QDataType QueueFront(Queue* pQueue);
QDataType QueueBack(Queue* pQueue);
//获取队列中有效元素个数 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueSize(Queue* pQueue);
bool QueueEmpty(Queue* pQueue);

结构定义与架构

结构：

//队列，先进先出，数组的话在头部出数据不方便，因此用链表来实现，单链表
typedef int QDataType;
 
    
    
    QDataType data;
} QNode;


 
    QNode* head;
    QNode* tail;
     size;
} Queue;