和栈相反，队列(queue)是一种先进先出的线性表，它只允许在一端进行插入，而在另一端被删除。这和生活中的排队是类似的，最先排队的最先离开。在队列中运行被插入的一端叫做队尾，允许被删除的一端叫做队尾。
比如我们去银行办理业务的时候需要去抽号机器上取一个号码，这起始就是队列的应用。每当有一个人取号后机器就会把这个号码入队列进行排队。等窗口工作人员进行叫号办理业务。
队列可以用数组或者链表实现，使用链表实现会更加合适一些，因为如果使用数组实现在出队的时候效率会比较低。
队列的定义
因为是链表实现所以还要定义一个节点结构体，队列的结构题包含两个指针一个队头指针和一个队尾指针
typedef int QDataType;
typedef struct QListNode {QDataType data;
struct QListNode* next;//下一个节点
}QNode;
typedef struct Queue
{QNode* front;//队头
QNode* rear;//队尾
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 动态申请节点
QNode* BuyQNode(QDataType data);
// 队尾入队列
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);初始化队列比较简单，让队头和队尾指向NULL，因为此时队列里没有任何元素。
// 初始化队列
void QueueInit(Queue* q)
{assert(q);
q->front = NULL;
q->rear = NULL;
}因为这是链表实现所以还要定义个动态申请节点的函数
// 动态申请节点
QNode* BuyQNode(QDataType data)
{QNode* node = (QNode*)(malloc(sizeof(QNode)));
if (node == NULL)
{printf("申请失败\n");
exit(-1);
}
node->data = data;
node->next = NULL;
return node;
}入队列需要考虑两种情况，第一种是队列为空的情况，队列为空要把队头和队尾指针都指向第一个元素，其他情况只需要把节点插入到队尾指针后面，再让对队尾指针往后走即可。
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);
QNode* node = BuyQNode(data);
if (q->front == NULL)
{q->front = node;
q->rear = node;
}
else
{q->rear->next = node;
q->rear = q->rear->next;
}
}出队列要考虑到队列是否为空，为空是不能进行出队列操作的。出队列只需要让队头指针往后走，再释放队头节点。
// 队头出队列
void QueuePop(Queue* q)
{assert(q);
assert(!QueueEmpty(q));
QNode* cur = q->front;
q->front = q->front->next;
free(cur);
}// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);
assert(!QueueEmpty(q));
return q->front->data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);
assert(!QueueEmpty(q));
return q->rear->data;
}和链表求长度是一样的
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);
QNode* cur = q->front;
int count = 0;
while (cur != NULL)
{count++;
cur = cur->next;
}
return count;
}当队头指向NULL时说明队列为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);
return q->front == NULL;
}销毁队列遍历一边队列，把每个节点给释放掉。
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);
QNode* cur = q->front;
while (cur != NULL)
{q->front = cur->next;
free(cur);
cur = q->front;
}
q->front = NULL;
q->rear = NULL;
}循环队列也是一种队列，再队列的顺序存储结构中，除了用一组连续的存储单元依次存放队头到队尾元素外，还需要两指针 front 和 rear 分别指向队头和队尾。
我们约定，初始化空队列时，让 front 和 rear 都赋为0，也就是指向数组的0下标。每当插入元素时尾指针加1，每当删除元素时头指针加1。
因为这时一个循环队列，当 f r o n t = = r e a r front == rear front==rear时，无法判断循环是满还是空。所以可以有两种选择，一种是做一个标记判断是否为满了，而是创建队列的时候多开一个空间，浪费掉这个空间方便判断。
我们采用第二种方式，约定 f r o n = = r e a r fron == rear fron==rear表示队列为空， r e a r + 1 = = f r o n rear+1 == fron rear+1==fron表示队列满了。
还有一个问题就是这是一个循环队列，当尾指针走到最后一个位置时如何走到下标为0的位置，我们可以巧妙的用一个公式，假设队列大小为 size。
头指针向后走： ( f r o n + 1 ) % s i z e (fron+1)\%size (fron+1)%size
尾指针向后走： ( r e a r + 1 ) % s i z e (rear + 1)\%size (rear+1)%size
代码实现
typedef struct {int* arr;
int front;
int rear;
int size;//容量
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* QUeue(int k) {MyCircularQueue* obj = (MyCircularQueue*)(malloc(sizeof(MyCircularQueue)));
//创建容量为k+1大小的队列，浪费1个空间
obj->arr = (int*)(malloc(sizeof(int)*(k+1)));
obj->front = 0;
obj->rear = 0;
obj->size = k+1;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj) == true)
{return false;//满了
}
else
{obj->arr[obj->rear] = value;
obj->rear = (obj->rear+1) % (obj->size);
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
{return false;
}
else
{obj->front = (obj->front+1) % (obj->size);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj) == true)
{return -1;
}
return obj->arr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
{return -1;
}
return (obj->rear == 0) ? (obj->arr[obj->size-1]) : (obj->arr[obj->rear-1]);
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满
if (obj->front == obj->rear)
{return true;
}
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {//约定 头位相遇就是空，尾+1是头就是满
if (((obj->rear)+1)%obj->size == (obj->front))
{return true;
}
return false;
}
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);
obj->front = NULL;
obj->rear = NULL;
free(obj);
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
