最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天微资讯！【C 数据结构】循环队列

来源：博客园


(资料图片仅供参考)

循环队列

  • 预先分配好数组空间
#define BUFFER_SIZE 1024// 在栈区分配空间int buf[N];// 在堆区分配空间int* buf;buf = (int*)malloc(BUFFER_SIZE * sizeof(int));
  • 定义队头指针和队尾指针
int front, back;
循环队列

思路：front 始终指向队头元素位置的前一个位置，back 始终指向队尾元素位置。

  • 出队操作就是先将 front后移 front = (front + 1) % BUFFER_SIZE然后将队头buf[front]出队。
  • 入队操作就是先将 back后移 back = (back + 1) % BUFFER_SIZE然后入队 buf[back]=x

1 初始化

  • 开始，队中没有元素。front = back = 0
void init(){    front = back = 0;}

2 队空和队满判断

队空条件和队满条件相同，都是 front == back

  • 解决方法：
    • 方法一：附设一个存储队中元素个数的变量 size
    • 方法二：少用一个元素空间，使 (back + 1) % BUFFER_SIZE == front为队满条件
  • 方法一：
int isEmpty(){    return front == back;// 或 size == 0}int isFull(){    return size == BUFFER_SIZE;}
  • 方法二：
int isEmpty(){    return front == back;}int isFull(){    return (back + 1) % BUFFER_SIZE == front;}

3 入队操作和出队操作

  • 方法一：
#define inf 0x3f3f3f3fint pop_front(){    if(front == back) return inf;        front = (front + 1) % BUFFER_SIZE;    return buf[front];}int push_back(int x){    if(size == BUFFER_SIZE) return 0;        back = (back + 1) % BUFFER_SIZE;    buf[back] = x;        return 1;}
  • 方法二：
#define inf 0x3f3f3f3fint pop_front(){    if(front == back) return inf;        front = (front + 1) % BUFFER_SIZE;    return buf[front];}int push_back(int x){    if((back + 1) % BUFFER_SIZE == front) return 0;        back = (back + 1) % BUFFER_SIZE;    buf[back] = x;        return 1;}

完整实现代码

myQueue.h

#define N 50#define INF 0x3f3f3f3ftypedef struct {    int* buf;    int front;///< 队头指针    int back;///< 队尾指针    int size;///< 队列实际尺寸}myQueue;extern void initQueue(myQueue*);extern int isEmpty(const myQueue*);extern int isFull(const myQueue*);extern int queueSize(const myQueue*);extern int pop_front(myQueue*); extern int push_back(myQueue*, int);

myQueue.c

#include "../include/myQueue.h"#include /// @brief 初始化循环队列/// @param que 要初始化的队列对象的指针void initQueue(myQueue* que){    que->buf = (int*)malloc(N * sizeof(int));    que->front = 0;    que->back = 0;    que->size = 0;}/// @brief 判断队列是否为空int isEmpty(const myQueue* que){    return que->front == que->back;}/// @brief 判断队列是否满了int isFull(const myQueue* que){    return que->size == N;}/// @brief 得到队列的长度int queueSize(const myQueue* que){    return que->size;    }/// @brief 出队int pop_front(myQueue* que){    if(!que->size) return INF;    que->front = (que->front + 1) % N;    que->size --;    return que->buf[que->front];}/// @brief 入队int push_back(myQueue* que, int x){    if(que->size == N) return 0;    que->back = (que->back + 1) % N;    que->buf[que->back] = x;    que->size ++;    return 1;}

关键词：