循环队列

1.循环队列的建立

Element.h

#define MAX_SIZE 255
#define true 1
#define false 0
typedef struct {
    int id;
    char * name;
}ElementType;

SeqQueue.h

//循环队列就是队列头尾先连的顺序存储结构
#include "Element.h" 

typedef int State;//给整型起一个别名，专门用来表示状态
#define STATE_OK 1
#define STATE_FAILE -1

//循环队列结构
//没有链，所以不需要建立节点
typedef struct {
    ElementType data[MAX_SIZE];//ElementType *base;
    int front;//对头指针
    int rear;//对尾指针
    int length;//队列长度
    //可以在这里增加一个标识位表示状态，标识当前队列是否已满
}SeqQueue;

//初始化
void InitSeqQueue(SeqQueue * seqQueue);

//以TRUE/FALSE的方式返回传入的队列是否为空
State IsSeqQueueEmpty(SeqQueue * seqQueue);

//以TRUE/FALSE的方式返回传入的队列是否已满
State IsSeqQueueFull(SeqQueue * seqQueue);

//入队
State OfferSeqQueue(SeqQueue * seqQueue,ElementType element);

//出队
State PollSeqQueue(SeqQueue * seqQueue,ElementType * element);

SeqQueue.cpp

#include <iostream>
using namespace std;
#include "SeqQueue.h"

//初始化
void InitSeqQueue(SeqQueue * seqQueue){
    if(seqQueue == NULL){
    seqQueue=(SeqQueue *)malloc(sizeof(SeqQueue));
    }
    seqQueue->length=0;
    seqQueue->front=0;
    seqQueue->rear=0;
}

//以TRUE/FALSE的方式返回传入的队列是否为空
State IsSeqQueueEmpty(SeqQueue * seqQueue){
    //对头指针与队尾指针相同，队列为空
    return seqQueue->front=seqQueue->rear ? true :false;
}

//以TRUE/FALSE的方式返回传入的队列是否已满
State IsSeqQueueFull(SeqQueue * seqQueue){
    if((seqQueue->rear+1)%MAX_SIZE==seqQueue->front){
    return true;
    }
    return false;
}

//入队
State OfferSeqQueue(SeqQueue * seqQueue,ElementType element){
    if(IsSeqQueueFull(seqQueue)){
    return STATE_FAILE;//队列已满，入队失败
    }
    seqQueue->data[seqQueue->rear]=element;
    seqQueue->rear=(seqQueue->rear+1)%MAX_SIZE;
    seqQueue->length++;
    return STATE_OK;
}

//出队
State PollSeqQueue(SeqQueue * seqQueue,ElementType * element){
    if(IsSeqQueueEmpty(seqQueue)){
    return STATE_FAILE;
    }
    //取出队头元素
    *element=seqQueue->data[seqQueue->front];
    seqQueue->front=(seqQueue->front + 1) % MAX_SIZE;
    seqQueue->length--;
    return STATE_OK;
}

main.cpp

#include "SeqQueue.h"
#include <iostream>
using namespace std;

ElementType datas[]={
    {1,"哈哈哈"},
    {2,"哇哇哇"},
    {3,"呵呵呵"},
    {4,"啦啦啦"}
};

void TestSeqQueue();

int main(){
    TestSeqQueue();

    return 0;
}

void TestSeqQueue(){
    SeqQueue seq;
    InitSeqQueue(& seq);
    OfferSeqQueue(&seq,datas[0]);
    OfferSeqQueue(&seq,datas[1]);
    OfferSeqQueue(&seq,datas[2]);
    OfferSeqQueue(&seq,datas[3]);
    for(int i=0;i<seq.length;i++){
    printf("%d\t%s\n",seq.data[i].id,seq.data[i].name);
    }

    //出队
    ElementType* element=(ElementType *)malloc(sizeof(ElementType));
    PollSeqQueue(&seq,element);
    printf("当前出队的元素：\n");
    printf("%d\t%s\n",element->name,element->id);
    printf("出队后队列的元素：\n");
    for(int i=0;i<seq.length;i++){
    printf("%d\t%s\n",seq.data[i].id,seq.data[i].name);
    }
}

2021.11.20 22:13