C语言创建循环队列的两种方式

循环队列

队列定义

只能在表的一段插入(入队/进队),在表的另一端删除(出队/离队)。即FIFO。

逻辑表现

  • 算法上表现为将数组元素围成圈,rearfront在同一个起点表示队空,rear移动后插入数据,删除数据后front向前走。
  • 为了判断队满还是队空(因为满了后rear会走一步而和front在一起,因为设计上将在一起看作队空,所以此时满了走一步又在一起会导致无法判断队满队空),会牺牲一个储存单元,即循环队列中的data[MaxSize]和栈等算法相比较会少一个存储单元。
  • 判断队 满时只要让rear多走一步,若到front的位置即表明当前已队满。例:(Q.rear+1)%MaxSize==Q.front
  • 循环中参考时钟周期循环的方式使用取模进行运算,每次rear+1后取模MaxSize,取模即进行周期运算。入队同理。

队头(Front)

允许删除的一端,又称队首。

队尾(Rear)

允许插入的一端

结构体

data[MaxSize]front(队首),rear(队尾),数组只能存MaxSize-1个数据,比栈等算法少存一个

循环队列代码

结构体

有队首队尾和数据,如下:

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

初始化

main中声明后调用初始化函数,初始化目的将队首队尾都指向0号位置:

void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;       //初始化让队首和队尾都指向0号位置
}

判断队列是否空

判断队首和队尾是否相等即可:

bool IsEmpty(SqQueue Q){
    return Q.rear==Q.front;
}

入队

判断是否队满,保存数据后判断周期,将周期运算结果保存到rear:

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){        //判断队列是否满了
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

出队

判断是否队空,数据保存到x。将front+1后判断周期,并将周期结果保存到front

bool DelQueue(SqQueue &Q,ElemType &x){
    if(IsEmpty(Q)){
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

链表实现

声明两个结构体,分别是节点和队列(FIFO),声明节点是为了实现数据间的联系,声明队列是为了实现队列定义下节点间的联系。在链表中实现联系一般由指针体现(地址间的联系):

typedef int Elemtype;
typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode;
typedef struct LinkQueue{
    LNode *front,*rear;
}LinkQueue;

初始化

分配空间,next设为NULL以作队列的尾部标识:

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LNode*)malloc(sizeof(LNode));
    Q.front->next=NULL;
}

入队

调用后先声明新节点,数据保存后因尾插法需要将新节点next设NULL,后将前一个节点的next链接上新节点,再移动rear标记到新节点上表明先最后一个节点为新节点:

void EnQueue(LinkQueue &Q,Elemtype x){
    LNode *pnew=(LNode*)malloc(sizeof(LNode));
    pnew->data=x;
    pnew->next=NULL;
    Q.rear->next=pnew;
    Q.rear=pnew;
}

出队

front是头指针不动,要判断位置,如果要出队节点是最后一个元素,则让rearfront位置使其相等,满足队空条件,如下:

bool DeQueue(LinkQueue &Q,int &x){
    if(Q.rear==Q.front){
        return false;
    }
    LNode *q=Q.front->next;
    Q.front->next=q->next;
    if(Q.rear==q){
        Q.rear=Q.front;
    }
    free(q);
    return true;
}
赞(0)
未经允许不得转载:卓克小站 » C语言创建循环队列的两种方式

评论 抢沙发