目录

一、循环队列

二、链队 

一、循环队列

输入格式:

在一行中输入若干个入队的数字，使用-1结束，例如：1 2 3 4 5 -1。

输出格式:

参照主函数及输出样例，当队列为空时出队或取队头元素时返回-1。

测试数据在1~99之间的整数，输出格式使用%3d，输出字符串中使用中文标点符号。

输入样例1:

1 2 3 4 5 6 -1

输出样例1:

在这里给出相应的输出。例如：

队列中的元素有：  1  2  3  4  5  6
队列的长度是：6
出队操作...
出队的元素是：1
队列中的元素有：  2  3  4  5  6
取队头元素...
队头元素是：2
队列中的元素有：  2  3  4  5  6

输入样例2:

1 2 3 4 5 6 7 8 9 10 -1

输出样例2:

在这里给出相应的输出。例如：

队列已满，元素10无法入队！
队列中的元素有：  1  2  3  4  5  6  7  8  9
队列的长度是：9
出队操作...
出队的元素是：1
队列中的元素有：  2  3  4  5  6  7  8  9
取队头元素...
队头元素是：2
队列中的元素有：  2  3  4  5  6  7  8  9

输入样例3:

1 -1

在这里给出相应的输出。例如：

队列中的元素有：  1
队列的长度是：1
出队操作...
出队的元素是：1
队列为空！
取队头元素...
队列为空，无法取队头元素！
队头元素是：-1
队列为空！

#include <stdio.h>
#include <malloc.h>
#define MAXQSIZE 10
typedef int QElemType;
typedef struct
{
    QElemType *base;
    int frot;
    int rear;
}SqQueue;

void InitQueue(SqQueue &Q); // 初始化队列
void EnQueue(SqQueue &Q, QElemType e); // 入队
void DeQueue(SqQueue &Q, QElemType &e); // 出队
int LengthQueue(SqQueue &Q); // 求队长
int QueueIsFull(SqQueue &Q); // 判断队列是否已满
void GetHeadQueue(SqQueue &Q, QElemType &e); // 取队头元素
void PrintQueue(SqQueue &Q); // 输出队列元素(已知)

int main()
{
    SqQueue Q;
    QElemType e;
    InitQueue(Q);
    scanf("%d", &e);
    while(e != -1)
    {
        EnQueue(Q, e);
        scanf("%d", &e);
    }
    PrintQueue(Q);
    printf("队列的长度是：%d\n", LengthQueue(Q));
    printf("出队操作...\n");
    DeQueue(Q, e);
    printf("出队的元素是：%d\n", e);
    PrintQueue(Q);
        printf("取队头元素...\n");
    GetHeadQueue(Q, e);
    printf("队头元素是：%d\n", e);
    PrintQueue(Q);

    return 0;
}
void PrintQueue(SqQueue &Q)
{
    if(Q.frot == Q.rear)
    {
        printf("队列为空！\n");
        return;
    }
    int i = Q.frot;
    printf("队列中的元素有：");
    for(; i<Q.rear; i++)
        printf("%3d", Q.base[i]);
    if(i > Q.rear)
    {
        for(; i<MAXQSIZE; i++)
            printf("%3d", Q.base[i]);
        for(i=0; i<Q.rear; i++)
            printf("%3d", Q.base[i]);
    }
    printf("\n");
    return;
}

void InitQueue(SqQueue &Q)
{
    Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base) 
    {
        printf("内存申请失败！\n");
        return;
    }
    Q.frot = Q.rear = 0;
    return;

}

void EnQueue(SqQueue &Q, QElemType e)
{
    if(QueueIsFull(Q))
    {
        printf("队列已满，元素%d无法入队！\n",e);
        return;
    }
    Q.base[Q.rear]=e;
    Q.rear = (Q.rear + 1)% MAXQSIZE;
    return;
}

void DeQueue(SqQueue &Q, QElemType &e)
{
    if(Q.frot == Q.rear)
    {
        printf("队列为空，无法执行出队操作！\n");
        e = -1;
        return;
    }
    e = Q.base[Q.frot];
    Q.frot = (Q.frot + 1)% MAXQSIZE;
    return;
}

int LengthQueue(SqQueue &Q)
{
    return (Q.rear - Q.frot + MAXQSIZE)% MAXQSIZE;
}

int QueueIsFull(SqQueue &Q)
{
    if((Q.rear+1)%MAXQSIZE==Q.frot) return 1;
    return 0;
}

void GetHeadQueue(SqQueue &Q, QElemType &e)
{
    if(Q.frot==Q.rear)
    {
        printf("队列为空，无法取队头元素！\n");
        e = -1;
        return;
    }
    e = Q.base[Q.frot];
    return;
}

二、链队 

输入格式:

在一行中输入若干个入队的数字，使用-1结束，例如：1 2 3 4 5 -1。

输出格式:

参照主函数及输出样例。

测试数据在1~99之间的整数，输出格式使用%3d。

输入样例:

1 2 3 4 5 -1

输出样例:

队列中的元素有：  1  2  3  4  5
队列的长度是：5
出队操作...
元素1正在出队...
队列中的元素有：  2  3  4  5
获取队头元素...
队头元素是：2
队列中的元素有：  2  3  4  5
正在销毁队列...
队列已销毁！

#include <stdio.h>
#include <malloc.h>
typedef int QElemType;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode, *QNodeLink;
typedef struct
{
    QNodeLink frot;
    QNodeLink rear;
}LinkQueue;

void InitLinkQueue(LinkQueue &Q); // 构造一个空队列
void DestroyQueue(LinkQueue &Q); // 销毁链式队列
void EnQueue(LinkQueue &Q, QElemType e); // 入队操作
void DeQueue(LinkQueue &Q, QElemType &e); // 出队操作
int LengthQueue(LinkQueue &Q); // 队列的长度(已知)
void GetHeadQueue(LinkQueue &Q, QElemType &e); // 取队头元素
void PrintQueue(LinkQueue &Q); // 打印队列(已知)
        
int main()
{
    LinkQueue Q;
    QElemType e;
    InitLinkQueue(Q);
    scanf("%d", &e);
    while(e != -1)
    {
        EnQueue(Q, e);
        scanf("%d", &e);
    }
    PrintQueue(Q);
    printf("队列的长度是：%d\n", LengthQueue(Q));
    printf("出队操作...\n");
    DeQueue(Q, e);
    printf("元素%d正在出队...\n", e);
    PrintQueue(Q);
    printf("获取队头元素...\n");
    GetHeadQueue(Q, e);
    printf("队头元素是：%d\n", e);
    PrintQueue(Q);
    printf("正在销毁队列...\n");
    DestroyQueue(Q);

    return 0;
}

int LengthQueue(LinkQueue &Q) // 队列的长度
{
    QNodeLink p = Q.frot;
    int len = 0;
    while(p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

void PrintQueue(LinkQueue &Q) // 打印队列
{
    if(Q.frot == Q.rear)
    {
        printf("队列为空！\n");
        return;
    }
    QNodeLink p = Q.frot->next;
    printf("队列中的元素有：");
    while(p)
    {
        printf("%3d", p->data);
        p = p->next;
    }
    printf("\n");
    return;
}

void InitLinkQueue(LinkQueue &Q)
{
    Q.frot = Q.rear = (QNodeLink)malloc(sizeof(QNode));
    if(!Q.frot)
    {
        printf("内存申请失败！\n");
        return;
    }
    Q.frot->next = NULL;  //头指针置空
    return;
}

void DestroyQueue(LinkQueue &Q)
{
    while(Q.frot)
    {
        Q.rear = Q.frot->next;
        free(Q.frot);
        Q.frot = Q.rear;
    }
    printf("队列已销毁！\n");
    return;
}

void EnQueue(LinkQueue &Q, QElemType e)
{
    QNodeLink p = (QNodeLink)malloc(sizeof(QNode));
    if(!p)
    {
        printf("内存申请失败！\n");
        return;
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return;
}

void DeQueue(LinkQueue &Q, QElemType &e)
{
    if(Q.frot==Q.rear)
    {
        printf("队列为空！\n");
        e = -1;
        return;
    }
    QNodeLink p = Q.frot->next;
    e = p->data;
    Q.frot->next = p->next;
    free(p);
    if(p==Q.rear) Q.rear = Q.frot;
    return;
}

void GetHeadQueue(LinkQueue &Q, QElemType &e)
{
    if(Q.frot == Q.rear)
    {
        printf("队列为空！\n");
        e = -1;
        return;
    }
    QNodeLink p = Q.frot->next;
    e = p->data;
    return;
}