数据结构---队列

1.队列的概念

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

2.队列的选型

队列的实现底层可以使用数组（顺序表）也可以使用链表，这个时候我们就得根据队列的性质来选择不同的数据结构；

假设我们使用数组（顺序表）来实现：

顺序表的入数据确实很方便，但是当数组（顺序表）出数据的时候是非常不好出的，要进行后面数据的挪动，时间复杂度就是O(N)了；所以这个必然不是我们的最佳选择；

再来看看用链表实现：

这里我们也可以用双链表来实现，甚至更方便找到最后一个节点，进行入数据，但是我们要知道双链表的应用场景体现在任意位置插入/删除数据；这里我们要想找到尾节点不一定需要遍历，我们只需要定义一个尾节点的指针，用来更新每一次的新尾节点

3.基于链表实现队列数据结构

Queue.h

// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{ 
 struct QListNode* _pNext; 
 QDataType _data; 
}QNode; 
// 队列的结构
typedef struct Queue{ 
 QNode* _front; 
 QNode* _rear; 
 int size;
}Queue; 
// 初始化队列
void QueueInit(Queue* q); 
// 队尾入队列
void QueuePush(Queue* q, QDataType data); 
// 队头出队列
void QueuePop(Queue* q); 
// 获取队列头部元素
QDataType QueueFront(Queue* q); 
// 获取队列队尾元素
QDataType QueueBack(Queue* q); 
// 获取队列中有效元素个数
int QueueSize(Queue* q); 
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q); 
// 销毁队列
void QueueDestroy(Queue* q);

Queue.c

// 初始化队列
void QueueInit(Queue* q) {
	assert(q);
	q->size = 0;
	q->_front = q->_rear = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
	assert(q);
	//申请节点空间
	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
	if (NewNode == NULL) {
		perror("malloc fail");
		return;
	}
	NewNode->_data = data;
	NewNode->_pNext = NULL;

	//如果队列为NULL
	if (q->_rear == NULL) {
		q->size++;
		q->_front = q->_rear = NewNode;
	}
	else {
		q->_rear->_pNext = NewNode;
		q->_rear = NewNode;
		q->size++;
	}

}
// 队头出队列
void QueuePop(Queue* q) {
	assert(q);
	assert(q->_front);
	//队列只剩下一个节点
	if (q->size == 1) {
		free(q->_front);
		q->_front = q->_rear = NULL;
		q->size--;
		return;
	}
	//多个节点
	QNode* del = q->_front;
	q->_front = q->_front->_pNext;
	free(del);
	q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q) {
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q) {
	assert(q);
	return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* pcur = q->_front;
	while (pcur) {
		QNode* next = pcur->_pNext;
		free(pcur);
		pcur = next;
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

test.c

int main() {

    Queue Ql;
    QueueInit(&Ql);
    QueuePush(&Ql, 1);
    QueuePush(&Ql, 2);
    QueuePush(&Ql, 3);
    QueuePush(&Ql, 4);
    /*while (!QueueEmpty(&Ql)) {
        printf("%d ", QueueFront(&Ql));
        QueuePop(&Ql);
    }*/
    printf("%d ", QueueBack(&Ql));
    QueueDestroy(&Ql);
    return 0;
}