数据结构 |
您所在的位置：网站首页 › 顺序队列与循环队列 › 数据结构 |
数据结构
|
目录 概念 循环队列的作用 题目 注意事项 题解 用顺序表的实现 用链表的实现 概念
基于队列的先进先出的原则，在确定了队列长度的前提下，另队列首尾相接而实现的一种结构。 循环队列的作用循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/design-circular-queue
设置循环队列 注意事项单纯把链表的首尾相接就可以吗？ 那么我们来想想这样一个问题：空的循环队列是什么样的？
我们规定将头指针放在首元素的位置，尾指针放到尾元素的下一个位置，那空队列就是头指针和尾指针指向同一个位置。 那么，满的循环链表又是什么样的呢？
尾指针放在a8元素的后面，恰好又与空链表的指向完全相同。 那我们怎么解决呢？ 难道在结构体放一个变量判断它是否以满吗？不是不可以，但稍微有点“笨重”。 所以我们不妨让队列多添加一个位置，这个位置不放任何元素，仅仅是为了区别空与满： 与通常队列相似，循环队列同样也可以用链表与顺序表两种方式实现 用顺序表的实现 typedef int CQDataType; typedef struct { CQDataType* cq; int head; int tail; int size; } myCircularQueueEnQueue; bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj); bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj); //构造器，设置队列长度为 k myCircularQueueEnQueue* myCircularQueueEnQueueCreate(int k) { myCircularQueueEnQueue* newCQ = (myCircularQueueEnQueue*)malloc(sizeof(myCircularQueueEnQueue)); assert(newCQ); CQDataType* newcq = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1)); assert(newcq); newCQ->size = k; newCQ->cq = newcq; newCQ->head = 0; newCQ->tail = 0; return newCQ; } //向循环队列插入一个元素。如果成功插入则返回真 bool myCircularQueueEnQueueEnQueue(myCircularQueueEnQueue* obj, int value) { if (myCircularQueueEnQueueIsFull(obj)) { return 0; } obj->cq[obj->tail] = value; obj->tail = (obj->tail + 1) % (obj->size + 1); return 1; } //从循环队列中删除一个元素。如果成功删除则返回真 bool myCircularQueueEnQueueDeQueue(myCircularQueueEnQueue* obj) { if (myCircularQueueEnQueueIsEmpty(obj)) { return 0; } //obj->head = ((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1); obj->head = (obj->head + 1) % (obj->size + 1); return 1; } //从队首获取元素。如果队列为空，返回 -1 int myCircularQueueEnQueueFront(myCircularQueueEnQueue* obj) { if (obj->head == obj->tail) { return -1; } else { return obj->cq[obj->head]; } } // 获取队尾元素。如果队列为空，返回 -1 int myCircularQueueEnQueueRear(myCircularQueueEnQueue* obj) { if (obj->head == obj->tail) { return -1; } else { return obj->cq[((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1)]; } } //检查循环队列是否为空 bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj) { return obj->head == obj->tail; } //检查循环队列是否已满 bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj) { return (obj->tail + 1) % (obj->size + 1) == obj->head; } //释放 void myCircularQueueEnQueueFree(myCircularQueueEnQueue* obj) { free(obj->cq); free(obj); } 用链表的实现 typedef int CQDataType; typedef struct CQListNode { struct CQListNode* _next; CQDataType _data; }CQNode; typedef struct { CQNode* _head; CQNode* _tail; int size; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueIsEmpty(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* CQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); assert(CQ); CQ->size = k; CQNode* head = (CQNode*)malloc(sizeof(CQNode)); assert(head); CQNode* cur = CQ->_head = CQ->_tail = head; for (int i = 0; i < k; i++)//加上面共k+1个节点 { CQNode* cq = (CQNode*)malloc(sizeof(CQNode)); assert(cq); cur->_next = cq; cq->_next = NULL; cur = cur->_next; } cur->_next = head; return CQ; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (!myCircularQueueIsFull(obj)) { obj->_tail->_data = value; obj->_tail = obj->_tail->_next; return 1; } else { return 0; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) { obj->_head = obj->_head->_next; return 1; } else { return 0; } } int myCircularQueueFront(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) return obj->_head->_data; else return -1; } int myCircularQueueRear(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) { CQNode* cur = obj->_head; while (cur->_next != obj->_tail) { cur = cur->_next; } return cur->_data; } else return -1; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->_head == obj->_tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->_tail->_next == obj->_head; } void myCircularQueueFree(MyCircularQueue* obj) { /*CQListNode* cur = obj->_head; while(cur->_next!=cur)*/ CQNode* cur = obj->_head; CQNode* next = NULL; for (int i = 0; i < obj->size; i++) { next = cur->_next; free(cur); cur = next; } free(obj); } |
【本文地址】
今日新闻 |
推荐新闻 |