欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列详解——循环队列(顺序结构),链队列,循环队列(只有尾指针),字符队列(顺序结构)

程序员文章站 2022-06-06 20:58:23
...

准备写队列以下几种类型:循环队列(顺序结构),链队列,循环队列(只有尾指针),字符队列(顺序结构)


一、循环队列

循环队列存储结构

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;
}