数据结构-队列

2017-06-27

基本队列

队列的存储

队列的顺序存储-数据结构

#define MaxSize 50  //定义队列中元素的最大个数
typedef int ElemType;
//这种队列存在假溢出，即存在上限，但下限有空余
typedef struct{
    ElemType data[MaxSize]; //存放队列元素
    int front,rear; //队头指针和队尾指针,队头指向当前元素第一个的前一个，队伍指向当前元素最后一个
}SqQueue;

队列的链式存储-数据结构

typedef struct LinkNode{ //链式队列结点
    ElemType data;
    LinkNode *next;
}LinkNode;
typedef struct{ //链式队列
    LinkNode *front,*rear;  //队列的队头和队尾指针，表位是队尾，负责插入，表头是队头，负责删除
}LinkQueue;

队列的初始化

队列-顺序存储-初始化

//队列初始化
SqQueue *InitQueue(){
    SqQueue *Q = (SqQueue *)malloc(sizeof(SqQueue));
    Q->front = -1;
    Q->rear = -1;
    return Q;
}

队列-链式存储-初始化

//初始化队列
LinkQueue *InitLinkQueue(){
    LinkQueue *q = (LinkQueue *)malloc(sizeof(LinkQueue));
    q->front=q->rear= (LinkNode *)malloc(sizeof(LinkNode));
    q->front->next = NULL;  //表头空元素始终存在,front->next为队列中的第一个元素
    q->rear->next = NULL;
    return q;
}

判断队列空

队列-顺序存储-队列空判断

//判断队列空
bool isSqQueueEmpty(SqQueue &Q){
    if(Q.front == Q.rear){
        return true;
    }else{
        return false;
    }
}

队列-链式存储-队列空判断

//队列判断为空
bool isLinkQueueEmpty(LinkQueue &Q){
    if(Q.front->next && Q.rear){    //只要判断Q.front->next便足够了
        return true;
    }else{
        return false;
    }
}

队列的插入

队列-顺序存储-入队

//入队
void EnSqQueue(SqQueue &Q,ElemType e){
    if(Q.rear == MaxSize-1){
        printf("队列上限已溢出");
    }else{
        Q.data[++Q.rear] = e;
    }
}

队列-链式存储-入队

//入队
void EnLinkQueue(LinkQueue &Q,ElemType e){
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    p->data = e;
    p->next = NULL;
    if(Q.front->next){  //插入第一个元素
        Q.front->next = p;
    }
    Q.rear->next = p;   //表尾插入
    Q.rear = p;
}

队列的删除

队列-顺序存储-出队

//出队
ElemType DeSqQueue(SqQueue &Q){
    ElemType e = 0;
    if(Q.front == Q.rear){
        printf("队列空");
    }else{
        e = Q.data[++Q.rear];
    }
    return e;
}

队列-链式存储-出队

//出队
ElemType DeLinkQueue(LinkQueue &Q){
    ElemType e = 0;
    if(Q.front->next && Q.rear){
        printf("队列空");
    }else{
        LinkNode *p = Q.front->next;
        e = p->data;
        Q.front->next = p->next;
        if(Q.rear == p){    //删除最后一个元素
            Q.rear = Q.front;
        }
        free(p);
    }
    return e;
}

循环队列

队列的存储-数据结构

#define MaxSize 50  //定义队列中元素的最大个数
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; //存放队列元素
    int front,rear; //队头指针和队尾指针,队头指向当前元素d的第一个，队伍指向当前元素的最后一个的后一个
    bool isEmpty;  //判断队列是满还是空的标志,也可采用留一个位置不存来判别满空
}SqCirQueue;

队列的初始化

//初始化
SqCirQueue *InitSqCirQueue(){
    SqCirQueue *p = (SqCirQueue *)malloc(sizeof(SqCirQueue));
    p->front = 0;   //队头为第一个元素的前一个
    p->rear = 0;
    p->isEmpty = true;
    return p;
}

判断队列空

//判断队空
bool isSqCirQueueEmpty(SqCirQueue &Q){
    if(Q.isEmpty && Q.front==Q.rear){
        return true;
    }else{
        return false;
    }
}

队列的插入-入队

//入队
void EnSqCirQueue(ElemType e,SqCirQueue &Q){
    Q.isEmpty = false;  //入队才可能出现满
    if(!Q.isEmpty && Q.front==Q.rear){
        printf("循环队列已满");
    }else{
        Q.data[Q.rear] = e;
        Q.rear = (Q.rear+1)%MaxSize;
    }
}

队列的删除-出队

//出队
ElemType DeSqCirQueue(SqCirQueue &Q){
    Q.isEmpty = true;   //出队才可能出现空
    ElemType e = 0;
    if(Q.isEmpty && Q.front==Q.rear){
        printf("循环队列为空");
    }else{
        e = Q.data[Q.front];
        Q.front = (Q.front+1)%MaxSize;
    }
    return e;
}