队列详解——循环队列（顺序结构），链队列，循环队列（只有尾指针），字符队列（顺序结构）

准备写队列以下几种类型：循环队列（顺序结构），链队列，循环队列（只有尾指针），字符队列（顺序结构）

---

一、循环队列

循环队列存储结构

typedef int QElemType;
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

实现循环语句

可以把循环队列想象成一个圈

因为循环队列假如是数据能占所有位置，那么队满或者对空的语句都是front==rear，这样就不能判断了，所以需要空出一个位置出来即mansize-1个位置

插入队列实现循环语句：Q.rear=(Q.rear+1)%maxsize;

删除队头实现循环语句：Q.front=(Q.front+1)%maxsize;

判断队列满：(Q.rear+1)%maxsize==Q,front;

判空：Q.front==Q.rear;

注意：Q.front和Q.rear是指下标，例如取第一个元素值：Q.base[Q.front];

demo

#include <stdio.h>
#define Maxsize 100
typedef int QElemType;
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;
int count=0;
SqQueue QueueInit(SqQueue s)
{
    s.base=(QElemType *)malloc(Maxsize*sizeof(QElemType));
    if(!s.base)
        printf("error");
    else{
        s.front=s.rear=0;
    }
    return s;
}

SqQueue InsertQueue(SqQueue s,QElemType e)
{
    if((s.rear+1)%Maxsize==s.front)
        printf("error");
    else{
        s.base[s.rear]=e;
        s.rear=(s.rear+1)%Maxsize;
    }
    count++;
    return s;
}

SqQueue OutQueue(SqQueue s)
{
    int e;
    if(s.rear==s.front)
        printf("error");
    else{
        e=s.base[s.front];
        s.front=(s.front+1)%Maxsize;
    }
    printf("%d",e);
    count--;
    return s;
}

int main()
{
    SqQueue s,p;
    int e,i;
    s=QueueInit(s);
    for(i=0;i<4;i++)
    {
        s=InsertQueue(s,i+1);
    }
    p=s;
    for(i=0;i<count;i++)
    {
        printf("%d ",p.base[p.front]);
        p.front=(p.front+1)%Maxsize;
    }
    printf("\n");
    s=OutQueue(s);
    printf("\n");
    p=s;
    for(i=0;i<count;i++)
    {
        printf("%d ",p.base[p.front]);
        p.front=(p.front+1)%Maxsize;
    }
    return 0;
}

---

二、链队列

存储结构

typedef int QElemType;
typedef struct QLNode{
    QElemType data;
    struct QLNode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

demo

#include <stdio.h>
#include <malloc.h>
typedef int QElemType;
typedef struct QLNode{
    QElemType data;
    struct QLNode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

void InitQueue(LinkQueue *Q)
{   //printf("ss");
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
   // printf("ss");
    Q->front->next=NULL;
}

void InsertQueue(LinkQueue *Q,int e)
{
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    p->data=e;
    p->next=NULL;
    Q->rear->next=p;
    Q->rear=p;

}

void OutQueue(LinkQueue *Q)
{
    QueuePtr p;
    int e;
    if(Q->front==Q->rear)
        printf("error");
    p=Q->front->next;
    e=p->data;
    Q->front->next=p->next;
    printf("%d",e);
    if(Q->rear==p)
        Q->rear=Q->front;
    free(p);

}

int main()
{
    LinkQueue Q;
    QueuePtr p;
    int i;
    //printf("s");
    InitQueue(&Q);
    //printf("s");
    for(i=0;i<4;i++)
    {
        InsertQueue(&Q,i+1);
    }
   // printf("s");
    p=Q.front->next;
    for(i=0;i<4;i++)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    OutQueue(&Q);
    printf("\n");
    p=Q.front->next;
     for(i=0;i<3;i++)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    return 0;
}

---

三、循环队列（只有尾指针）

这个问题即用链式存储结构

存储结构

typedef int QElemType;
typedef struct Lnode{
    int data;
    struct Lnode *next;
}Node,*SqQueue;

---

demo

#include <stdio.h>
#include <malloc.h>
#define Maxsize 100
typedef int QElemType;
typedef struct Lnode{
    int data;
    struct Lnode *next;
}Node,*SqQueue;
int count=0;
SqQueue QueueInit(SqQueue rear)
{
    rear=(SqQueue)malloc(sizeof(Node));
    if(!rear)
        printf("error");
    else{
        rear->next=rear;
    }
    return rear;
}

SqQueue InsertQueue(SqQueue rear,QElemType e)
{
    SqQueue p;
    p=(SqQueue)malloc(sizeof(Node));
    p->data=e;
    p->next=rear->next;
    rear->next=p;
    rear=p;
    count++;
    return rear;
}

SqQueue OutQueue(SqQueue rear)
{
    int e;
    SqQueue p;
    if(rear==rear->next)
        printf("error");
    else{
        p=rear->next->next;
        e=p->data;
        rear->next->next=p->next;
        if(rear==p)
        {
            rear=rear->next;
        }
        free(p);
    }
    printf("%d",e);
    count--;
    return rear;
}

int main()
{
    SqQueue rear,p,q;
    int e,i;
    rear=QueueInit(rear);
    for(i=0;i<4;i++)
    {
        rear=InsertQueue(rear,i+1);
    }
    p=rear->next->next;
    for(i=0;i<4;i++)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    rear=OutQueue(rear);
    printf("\n");
    q=rear->next->next;
    for(i=0;i<3;i++)
    {
        printf("%d ",q->data);
        q=q->next;
    }
    return 0;
}

---

四、字符队列（顺序结构）

字符队列和普通没什么区别，但最重要一点就是字符输入时，会把空格或回车也放入缓存区，导致我想输入4个字符，却只能输入两个，解决办法就是加getchar();

---

demo

#include <stdio.h>
#define Maxsize 1000
typedef char QElemType;
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;
int count=0;
SqQueue QueueInit(SqQueue s)
{
    s.base=(QElemType *)malloc(Maxsize*sizeof(QElemType));
    if(!s.base)
        printf("error");
    else{
        s.front=s.rear=0;
    }
    return s;
}

SqQueue InsertQueue(SqQueue s,QElemType e)
{
    if((s.rear+1)%Maxsize==s.front)
        printf("error");
    else{
        s.base[s.rear]=e;
        s.rear=(s.rear+1)%Maxsize;
        count++;
    }

    return s;
}

SqQueue OutQueue(SqQueue s)
{
    char e;
    if(s.rear==s.front)
        printf("error");
    else{
        e=s.base[s.front];
        s.front=(s.front+1)%Maxsize;
        count--;
    }
    printf("%c",e);
    return s;
}
int main()
{
    SqQueue s,p;
    char a;
    int i;
    int l;

    s=QueueInit(s);
    for(l=0;l<4;l++)
    {
        scanf("%c",&a);
        getchar();//注意
        s=InsertQueue(s,a);
    }
    p=s;
    for(i=0;i<4;i++)
    {
        printf("%c",p.base[p.front]);
        p.front=(p.front+1)%Maxsize;
    }
    return 0;
}