C语言链式队列与循环队列怎么实现

这篇文章主要介绍了C语言链式队列与循环队列怎么实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言链式队列与循环队列怎么实现文章都会有所收获，下面我们一起来看看吧。

队列的实现

队列是一种先进先出（First in First Out）的线性表，简称FIFO。与栈不同，栈是一种后进先出（先进后出）的线性表。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=（a1,a2,…,an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然在队伍的最后。队列分为顺序队列和循环队列。顺序队列我们可以利用数组或者链表实现。这里，我们选择用链表实现顺序队列。

今天主要介绍链表实现的队列和循环队列

链式队列

队列主要有哪些基本操作

// 初始化队列  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  bool QueueEmpty(Queue* q); // 销毁队列  void QueueDestroy(Queue* q);

链式队列的定义

typedef int QDataType; // 链式结构：表示队列  typedef struct QListNode {     struct QListNode* _next;     QDataType _data; }QNode; // 队列的结构  typedef struct Queue {     QNode* _front;     QNode* _rear; }Queue;

链式队列的实现

1、初始化队列

void QueueInit(Queue* q) {     assert(q);     q->_front = NULL;     q->_rear = NULL; }

2、销毁队列

void QueueDestroy(Queue* q) {     assert(q);     QNode* cur = q->_front;     while (cur != NULL)     {         QNode* next = cur->_next;         free(cur);         cur = next;     }     q->_front = q->_rear = NULL; }

3、队列判空

bool QueueEmpty(Queue* q) {     assert(q);     //if (q->_front == NULL)     //{     //  return 1;     //}     //else     //{     //  return 0;     //}     return q->_front == NULL; }

4、入队操作

void QueuePush(Queue* q, QDataType data) {     assert(q);     QNode* newnode = (QNode*)malloc(sizeof(QNode));     if (newnode == NULL)     {         exit(-1);     }     newnode->_data = data;     newnode->_next = NULL;     if (q->_front == NULL)     {         q->_front = q->_rear = newnode;     }     else     {         q->_rear->_next = newnode;         q->_rear = newnode;     } }

5、出队操作

void QueuePop(Queue* q) {     assert(q);     assert(!QueueEmpty(q));     QNode* next = q->_front->_next;     free(q->_front);     q->_front = next;     if (q->_front == NULL)     {         q->_rear = NULL;     } }

6、取队头元素

QDataType QueueFront(Queue* q) {     assert(q);     assert(!QueueEmpty(q));     return q->_front->_data; }

7、取队尾操作

QDataType QueueBack(Queue* q) {     assert(q);     assert(!QueueEmpty(q));     return q->_rear->_data; }

8、队中有效元素个数

int QueueSize(Queue* q) {     assert(q);     int size = 0;     QNode* cur = q->_front;     while (cur)      {         size++;         cur = cur->_next;     }     return size; }

循环队列

循环队列的定义

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。

循环队列的空间可以重复利用，解决了普通队列的空间浪费问题

循环队列的实现

typedef struct {     int *a;     int front;     int tail;     int k; } MyCircularQueue; //提前声明判空判满 bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); //创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) {     MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));     cq->a=(int*)malloc(sizeof(int)*(k+1));     cq->front=cq->tail=0;     cq->k=k;     return cq; } //循环队列入队 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {     if(myCircularQueueIsFull(obj)){         return false;     }     obj->a[obj->tail]=value;     obj->tail++;     obj->tail%=(obj->k+1);     return true; } //循环队列出队 bool myCircularQueueDeQueue(MyCircularQueue* obj) {     if(myCircularQueueIsEmpty(obj)){         return false;     }     obj->front++;     obj->front%=(obj->k+1);     return true; } //循环队列取队头 int myCircularQueueFront(MyCircularQueue* obj) {     if(myCircularQueueIsEmpty(obj)){         return -1;     }     return obj->a[obj->front]; } //循环队列取队尾 int myCircularQueueRear(MyCircularQueue* obj) {     if(myCircularQueueIsEmpty(obj)){         return -1;     }     int i=(obj->tail+obj->k)%(obj->k+1);     return obj->a[i]; } //循环队列判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) {     return obj->front==obj->tail; } //循环队列判满 bool myCircularQueueIsFull(MyCircularQueue* obj) {     return (obj->tail+1)%(obj->k+1)==obj->front; } //销毁循环队列 void myCircularQueueFree(MyCircularQueue* obj) {     free(obj->a);     free(obj); }

关于“C语言链式队列与循环队列怎么实现”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C语言链式队列与循环队列怎么实现”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注亿速云行业资讯频道。