数据结构-->队列

朋友们，感谢你们到访本人博客！！现在我将为大家介绍队列！！

那么什么是队列呢？

---> 队列：只允许在一端进行插入数据的操作，在另一端进行删除数据的操作；队列遵循 先进先出 原则！ 同时，队头是指 插入数据的一端，而队尾是指 删除数据的一端！！

为了方便形象化的理解，特此附上图示样解  ::>

而我们如何实现队列，会更加优化一些呢！！答案是 用单链表 

前段时间，学习的链表如今就派上用场了！！至此，特别强调一下，前几期的链表博客有部分错误，现已修正好了，对好友而言感到十分抱歉！！毕竟本人也是刚刚学习数据结构！！

---

OK ！ 让我们开始动手书写代码吧！！

头文件  “Queue.h”

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

typedef struct QueueNode
{
  QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
  QNode* tail;
  int size;
}Queue;

//初始化
void QInitial(Queue* pq);

//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq, QDataType x);

//出队列
void QPop(Queue* pq);

//队列头部元素
QDataType QFront(Queue* pq);

//队列尾部元素
QDataType QBack(QNode* pq);

//对列元素个数
void Queueize(Queue* pq);

//布尔判空
bool QEmpty(Queue* pq);

实现环节 “Queue.c”

#include "Queue.h

//初始化
void QInitial(Queue* pq)
{
	pq ->head = NULL;
  pq ->tail = NULL;
  pq ->size = 0;
}

//销毁
void QDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq ->head;
  while(cur)
  {
		QNode* next = pq ->head ->next;
    free(pq ->head);
    cur = next;
  }
  
  pq ->head = NULL;
}

//入队列
void QPush(Queue* pq, QDataType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if(newnode == NULL)
  {
  	perror("malloc::fail");
    return ;
  }
  
  newnode ->data = x;
  newnode ->next = NULL;
  
  if(pq ->head == NULL)
  {
  	assert(pq ->tail == NULL);
    pq ->head = pa ->tail = NULL;
  }
  else
  {
    pq ->tail ->next = newnode;
    pq ->tail = newnode;
  }
  pq ->size++;
}

//出队列
void QPop(Queue* pq)
{
  assert(pq);
  if(pq ->head ->next == NULL)
  {
  	free(pq ->head);
    pq ->head = NULL;
  }
  else
  {
  	QNode* next = pq ->head ->next;
    free(pq ->head);
    pq ->head = NULL;
    pq ->head = next;
  }
  pq ->size--;
}

//队列头部元素
QDataType QFront(Queue* pq)
{
	assert(pq);
  
  return pq ->head ->data;
}

//队列尾部元素
QDataType QBack(QNode* pq)
{
	assert(pq);
  
  return pq ->tail ->data = NULL;
}

//对列元素个数
QDataType Queueize(Queue* pq)
{
	assert(pq);
  
  return pq ->size;
}

//布尔判空
bool QEmpty(Queue* pq)
{
	assert(pq);
  
  return pq ->size == 0;
}

测试环节 “Test.c”

#include "Queue.h"

int main()
{
  Queue q;
  
  QInitial(&q);
  QPush(&q, 21);
  QPush(&q, 24);
  QPush(&q, 27);
  QPush(&q, 23);
  QPush(&q, 22);
  
  while(!QEmpty(&q))
  {
    printf("%d ", QFront(&q));
    QPop(&q);
  }
  
  QDestroy(&q);
	return 0;
}

头文件 “Queue.h”

测试环节 “Test.c”

实现环节 “Queue.c”

如此，我们的队列就已经设计好了！！

不过，仍然需要我们注意几点 ：>

首先， 是关于指针 QNode 的二次分装，这其实是一个规范写法，更容易让逻辑清晰与严谨，防止出错！！

如果，我们不分装 QNode 指针 ，这会让我们再传指针时候，会更加的难以展开逻辑！！而且极易不好把控

因此，强烈建议按照上面的书写，方便实现队列，还是单链表式的队列！！

再者，入队列的操作，有些精华所在！！容易忽视一些情况！！而这，更能体现出一名程序员的代码素养！

好了，老友们！！今天的队列博客就到这里了！！下一期，我们将共同展开栈和队列的有关OJ题训练！！

感谢阅读！！敬请期待！！