#yyds干货盘点#算法开启循环队列武魂

小蚂蚁

设计循环队列

题目

我们会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。==环形队列可以使用数组实现，也可以使用循环链表实现。==

==可以认为队尾tail不是队尾，而是我们认知上队尾的后一个==

数组形式（通过下标控制来达到循环的效果）

环队结构体（数组）

typedef struct {
  int* a;
  int front;
  int tail;
  int k;//数组元素(队列长度)
} MyCircularQueue;

环队初始化

MyCircularQueue* myCircularQueueCreate(int k) {
  MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  q->a = (int*)malloc(sizeof(int)*(k+1));//队列长度为k我们要多开一个
  q->front = q->tail = 0;
  q->k = k;
  return q;
}

判断环队为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  return obj->front == obj->tail;
}

判断环队为满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
  return (obj->tail+1)%(obj->k+1) == obj->front;
}

环队入数据并入成功返回真

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  if(!myCircularQueueIsFull(obj))
  {
    obj->a[obj->tail] = value;//不是队满就下标tail的数据为value
    obj->tail++;
    obj->tail %= obj->k+1;//tail就步进一位
    return true;
  }
  return false;//队满就插不进去了
}

环队删数据并删成功返回真

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {
    obj->front++;//队不空就是出队，头标步进就行了
    obj->front %= obj->k+1;
    return true;
  }
  return false;//对空就删不了了
}

环队取队头数据（对空返回-1）

int myCircularQueueFront(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {
    return obj->a[obj->front]; //取front位置的数据就行     
  }
  return -1;
}

环队取队尾数据（对空返回-1）

int myCircularQueueRear(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {    
    return obj->a[obj->tail == 0 ? obj->k : obj->tail-1];//取tail前一个数据就行，tail为0，前一个就是k位置数据    
  }
  return -1;
}

环队销毁

void myCircularQueueFree(MyCircularQueue* obj) {
  free(obj->a);
  obj->a = NULL;
  obj->front = 0;
  obj->tail = 0;
  obj->k = 0;
  free(obj);
}

环队（数组实现）

typedef struct {
  int* a;
  int front;
  int tail;
  int k;//数组元素(队列长度)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
  MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  q->a = (int*)malloc(sizeof(int)*(k+1));//队列长度为k我们要多开一个
  q->front = q->tail = 0;
  q->k = k;
  return q;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  if(!myCircularQueueIsFull(obj))
  {
    obj->a[obj->tail] = value;//不是队满就下标tail的数据为value
    obj->tail++;
    obj->tail %= obj->k+1;//tail就步进一位
    return true;
  }
  return false;//队满就插不进去了
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {
    obj->front++;//队不空就是出队，头标步进就行了
    obj->front %= obj->k+1;
    return true;
  }
  return false;//对空就删不了了
}
int myCircularQueueFront(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {
    return obj->a[obj->front]; //取front位置的数据就行     
  }
  return -1;
}
int myCircularQueueRear(MyCircularQueue* obj) {
  if(!myCircularQueueIsEmpty(obj))
  {    
    return obj->a[obj->tail == 0 ? obj->k : obj->tail-1];//取tail前一个数据就行，tail为0，前一个就是k位置数据    
  }
  return -1;
}
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);
  obj->a = NULL;
  obj->front = 0;
  obj->tail = 0;
  obj->k = 0;
  free(obj);
}

链表形式

环队结构体（链表）

typedef int CQDataType;//环队数据类型
typedef struct CQNode
{
  CQDataType x;//环队节点数据
  struct CQNode* next;//环队节点指针
}CQNode;
typedef struct {
  CQNode* head;
  CQNode* tail;
  int k;
} MyCircularQueue;//空环队就两个裸指针

环队初始化

MyCircularQueue* myCircularQueueCreate(int k) {
  MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
  cq->k = k;
  cq->head = cq->tail = cur;
  while(k--)
  {
    CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
    CQNode* tail = cq->tail;//最后一个节点
    tail->next = newnode;//最后一个节点指向新的节点
    newnode->next = cq->head;//新的节点指向头节点
    cq->tail=newnode;
  }
  cq->head = cq->tail;
  return cq;
}

判断环队为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  return obj->head == obj->tail;
}

判断环队为满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  return obj->tail->next == obj->head;
}

环队入数据并入成功返回真

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsFull(obj))
  {
    obj->tail->x = value;
    obj->tail = obj->tail->next;
    return true;
  }
  return false;
}

环队删数据并删成功返回真

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
  {
    obj->head = obj->head->next;
    return true;
  }
  return false;
}

环队取队头数据（对空返回-1）

int myCircularQueueFront(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
    return obj->head->x;
  return -1;
}

环队取队尾数据（对空返回-1）

int myCircularQueueRear(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
  {
    CQNode*ret=obj->head;
    while(ret->next!=obj->tail)
    {
      ret=ret->next;
    }
    return ret->x;
  }
  return -1;  
}

环队销毁

void myCircularQueueFree(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  while(obj->head!=obj->tail)
  {
    CQNode*ret=obj->tail;
    obj->tail=obj->tail->next;
    free(ret);
  }
  free(obj->head);
  free(obj);
}

环队（链表实现）

typedef int CQDataType;//环队数据类型
typedef struct CQNode
{
  CQDataType x;//环队节点数据
  struct CQNode* next;//环队节点指针
}CQNode;
typedef struct {
  CQNode* head;
  CQNode* tail;
  int k;
} MyCircularQueue;//空环队就两个裸指针
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
  MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
  cq->k = k;
  cq->head = cq->tail = cur;
  while(k--)
  {
    CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
    CQNode* tail = cq->tail;//最后一个节点
    tail->next = newnode;//最后一个节点指向新的节点
    newnode->next = cq->head;//新的节点指向头节点
    cq->tail=newnode;
  }
  cq->head = cq->tail;
  return cq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsFull(obj))
  {
    obj->tail->x = value;
    obj->tail = obj->tail->next;
    return true;
  }
  return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
  {
    obj->head = obj->head->next;
    return true;
  }
  return false;
}
int myCircularQueueFront(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
    return obj->head->x;
  return -1;
}
/*int myCircularQueueRear(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
  {
    CQNode* ret = obj->head;//这个ret 是用来找tail前一个的，不可用直接返回tail，会改变原来环队的链接关系
    while(--obj->k)
    {
       obj->tail = obj->tail->next;
    }    
    ret = obj->tail;
    obj->tail = obj->tail->next;
    return obj->tail->x;
  }
  return -1;  
}*/
int myCircularQueueRear(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  if(!myCircularQueueIsEmpty(obj))
  {
    CQNode*ret=obj->head;
    while(ret->next!=obj->tail)
    {
      ret=ret->next;
    }
    return ret->x;
  }
  return -1;  
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  return obj->tail->next == obj->head;
}
void myCircularQueueFree(MyCircularQueue* obj) {
  assert(obj->head && obj->tail);
  while(obj->head!=obj->tail)
  {
    CQNode*ret=obj->tail;
    obj->tail=obj->tail->next;
    free(ret);
  }
  free(obj->head);
  free(obj);
}

实际上这题我报错我不想找了太恶心了（家凌帮我找错的非常感谢）

[C++] #yyds干货盘点#算法开启循环队列武魂

相关帖子

win10休眠时自动关闭网络怎么解决

word文档操作痕迹的查看方法

win11笔记本省电模式怎么开启 win11省电模式开启方法

路由器开启dhcp-(路由器开启DHCP)

出现Win10一直在无限循环登录界面怎么办

主机开一下熄火然后一直循环是否主板坏了

没有开关的无线键盘开启按什么键

路由器dhcp关闭有什么影响路由器的dhcp是开启好还是关闭好

开机风扇转了一下就重启无限循环解决方法

风冷散热器怎么看好坏？

小蚂蚁 LV3