广场 › 编程语言 › #yyds干货盘点#算法开启循环队列武魂

小蚂蚁 发表于 2021-12-28 23:11:32

#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 = 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; //取front位置的数据就行      
    }
    return -1;
}环队取队尾数据（对空返回-1）
int myCircularQueueRear(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {      
      return obj->a;//取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 = 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; //取front位置的数据就行      
    }
    return -1;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {      
      return obj->a;//取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);
}实际上这题我报错我不想找了太恶心了（家凌帮我找错的非常感谢）



https://blog.51cto.com/u_15443484/4853831

查看完整版本: #yyds干货盘点#算法开启循环队列武魂