devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

队列的顺序存储实现_使用顺序存储实现一个循环队列,队列的容量为1024(可存储1024个元素)。实现下面的

作者：爱喝兽奶帝天荒 | 2024-08-13 13:07:50

赞

踩

使用顺序存储实现一个循环队列,队列的容量为1024(可存储1024个元素)。实现下面的

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

队列

队列是限定只允许在表的一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针(rear)的指针指向队尾元素（最后被插入的元素）所在的位置；允许删除的一端称为队头（队首），通常用一个称为队头指针（front）指向队头元素的前一个位置。

一、队列定义

在这里插入图片描述
在这里插入图片描述

1. 队列的基本操作

在这里插入图片描述

2.普通队列存在的弊端

在这里插入图片描述
如上图，假设需要将元素1 到元素12 全部入队，
当t元素1 到 元素10入队到队列中时，发现队列已经满了，
在这里插入图片描述
此时元素1,2，3依次出队，头指针移动位置
在这里插入图片描述
此时如果使用的是普通队列，想往队列中入队元素是无法入队的，因
为队尾指针已经到了数组的最后一个位置；如果再入队，队尾指针加1，即图中下标为10的位置，明显不存在该位置，入队会发生错误；

即使队头处有空位置，也无法入队元素，这种情况就是假溢出；
所以普通队列的这种方法浪费了内存；

所以下面我们使用循环队列来解决假溢出的问题；

3.循环队列

所谓循环队列，就是将队列存储空间的最后一个位置接到第一个位置，形成逻辑上的环状空间，供队列使用；
在这里插入图片描述
在这里插入图片描述

设计首尾指针的不同方案：

方案一：队尾指针指向队尾下一个元素；

在这里插入图片描述
队空公式 ：frontrear，
但是在下图中， 队满的情况下，队尾元素为数组下标为[2]的元素，而下标为[3]的元素为头指针所指元素，但是由于尾指针指向队尾元素下一个元素，所以此时frontrear也成立，那么 front==rear 的时候，到底是队空还是队满呢？
所以这种情况存在歧义；
在这里插入图片描述

所以我们采用牺牲一个存储单元的情况； 队满表示为:
(rear+1)%MAXSIZE==front;
在这里插入图片描述

方案一改进：

在这里插入图片描述

方案二：队尾指针指向队尾元素：

在这里插入图片描述
在这里插入图片描述

方案二改进：
在这里插入图片描述

二、队列的顺序存储实现

1.循环队列的数组实现，队尾指针指向队尾的下一个元素，没有length的辅助变量。

代码如下（示例）：

        程序名：seqqueue1.c，此程序演示循环队列的数组实现，队尾指针指向队尾的下一个元素，没有length的辅助变量。
 */

#include <stdio.h>
#include <string.h>

#define MAXSIZE 10       // 循环队列的最大长度，最多可以存放MAXSIZE-1个元素。

typedef int ElemType;

typedef struct
{
        ElemType data[MAXSIZE];         //用数组存储循环队列中的元素。
        int front;                      //头指针，指向队头元素。
        int rear;                       //尾指针，指向队尾元素的下一个元素。

}SeqQueue,*PSeqQueue;

//循环队列初始化操作
void InitQueue(PSeqQueue QQ);

//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee);

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ);

// 清空循环队列。
void Clear(PSeqQueue QQ);

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ);

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ);

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ);

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee);


int main()
{
        SeqQueue qq;
        
        InitQueue(&qq);

        printf("队列的长度为:%d\n",Length(&qq));

        printf("向队列中插入元素:1,2,3,4,5,6,7,8,9,10。\n");
        ElemType ee;

        ee=1;InQueue(&qq,&ee);
        ee=2;InQueue(&qq,&ee);
        ee=3;InQueue(&qq,&ee);
        ee=4;InQueue(&qq,&ee);
        ee=5;InQueue(&qq,&ee);
        ee=6;InQueue(&qq,&ee);
        ee=7;InQueue(&qq,&ee);
        ee=8;InQueue(&qq,&ee);
        ee=9;InQueue(&qq,&ee);
        ee=10;InQueue(&qq,&ee);

        //向队列中插入多余的元素，看是否会溢出
        ee=11;InQueue(&qq,&ee);
        ee=12;InQueue(&qq,&ee);
        printf("队列的长度为:%d\n",Length(&qq));

        printf("打印队列所有元素:\n");
        PrintQueue(&qq);

        printf("QQ->rear=%d,QQ->front=%d\n",qq.rear,qq.front);

        //将队列中出队
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);


        return 0;
}

//循环队列初始化操作
void InitQueue(PSeqQueue QQ)
{
        Clear(QQ);
}

//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ)
{

        Clear(QQ);
}

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }


        if( ((QQ->rear+1)%MAXSIZE)==QQ->front ){printf("队列已满。\n");return 0;}
        //if( Length(QQ)>=MAXSIZE-1 ){printf("队列已满。\n");return 0;}


        //将元素ee的值复制给队列中的数组  
        memcpy(&QQ->data[QQ->rear],ee,sizeof(ElemType));

        QQ->rear=(QQ->rear+1)%MAXSIZE;

        return 1;
}

//元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( QQ->rear==QQ->front ){printf("队列为空,出队失败。\n");return 0; }

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        QQ->front=(QQ->front+1)%MAXSIZE;

        return 1;
}

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return 0;}


        int len=(QQ->rear-QQ->front+MAXSIZE)%MAXSIZE;

        return len;
}

// 清空循环队列。
void Clear(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}

        memset(QQ->data,0,sizeof(QQ->data));
        QQ->front=QQ->rear=0;

}
// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;

        if( QQ->rear==QQ->front )return 1;
        return 0;

}

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;
        if( ((QQ->rear+1)%MAXSIZE)==QQ->front )return 1;
        return 0;
}

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}

        int ii=QQ->front;

        while(ii!= QQ->rear)
        {
                printf("%-3d ",QQ->data[ii]);
                ii=(ii+1)%MAXSIZE;
        }
        printf("\n");
}

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if(IsEmpty(QQ)==1){printf("队列为空。\n");return 0;}

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        return 1;
}
              

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210

2.循环队列的数组实现，队尾指针指向队尾的下一个元素，增加了length的辅助变量。

代码如下（示例）：

/*
        程序名：seqqueue1.c，此程序演示循环队列的数组实现，队尾指针指向队尾的下一个元素，增加了length的辅助变量。
 */

#include <stdio.h>
#include <string.h>

#define MAXSIZE 10       // 循环队列的最大长度，最多可以存放MAXSIZE-1个元素。

typedef int ElemType;

typedef struct
{
        ElemType data[MAXSIZE];         //用数组存储循环队列中的元素。
        int front;                      //头指针，指向队头元素。
        int rear;                       //尾指针，指向队尾元素的下一个元素。
        int length;                     //队列的实际长度                //xxx

}SeqQueue,*PSeqQueue;

//循环队列初始化操作
void InitQueue(PSeqQueue QQ);

//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee);

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ);

// 清空循环队列。
void Clear(PSeqQueue QQ);

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ);

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ);

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ);

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee);


int main()
{
        SeqQueue qq;
               
        InitQueue(&qq);
        
        printf("队列的长度为:%d\n",Length(&qq));
        
        printf("向队列中插入元素:1,2,3,4,5,6,7,8,9,10。\n");
        ElemType ee;
        
        ee=1;InQueue(&qq,&ee);
        ee=2;InQueue(&qq,&ee);
        ee=3;InQueue(&qq,&ee);
        ee=4;InQueue(&qq,&ee);
        ee=5;InQueue(&qq,&ee);
        ee=6;InQueue(&qq,&ee);
        ee=7;InQueue(&qq,&ee);
        ee=8;InQueue(&qq,&ee);
        ee=9;InQueue(&qq,&ee);
        ee=10;InQueue(&qq,&ee);
        
        //向队列中插入多余的元素，看是否会溢出
        ee=11;InQueue(&qq,&ee);
        ee=12;InQueue(&qq,&ee);
        printf("队列的长度为:%d\n",Length(&qq));
        
        printf("打印队列所有元素:\n");
        PrintQueue(&qq);
        
        printf("QQ->rear=%d,QQ->front=%d\n",qq.rear,qq.front);
        
        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);
        
        //将队列中出队
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        
        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        
        
        return 0;
}       

//循环队列初始化操作
void InitQueue(PSeqQueue QQ)
{
        Clear(QQ);
}
//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ)
{

        Clear(QQ);
}

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }


        if( IsFull(QQ)==1 ){printf("队列已满。\n");return 0;}
        //if( Length(QQ)>=MAXSIZE-1 ){printf("队列已满。\n");return 0;}


        //将元素ee的值复制给队列中的数组  
        memcpy(&QQ->data[QQ->rear],ee,sizeof(ElemType));

        QQ->rear=(QQ->rear+1)%MAXSIZE;
        QQ->length++;                           //长度加1

        return 1;
}

//元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( QQ->length==0 ){printf("队列为空,出队失败。\n");return 0; }

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));

        QQ->front=(QQ->front+1)%MAXSIZE;
        QQ->length--;                           //队列减1

        return 1;
}

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return 0;}


        int len=(QQ->rear-QQ->front+MAXSIZE)%MAXSIZE;

        return len;
}

// 清空循环队列。
void Clear(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}

        memset(QQ->data,0,sizeof(QQ->data));
        QQ->front=QQ->rear=QQ->length=0;

}
// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;

        if( QQ->length==0 )return 1;
        return 0;

}

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;
        if(QQ->length==MAXSIZE-1 )return 1;
        return 0;
}

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}

        int ii=QQ->front;

        while(ii!= QQ->rear)
        {
                printf("%-3d ",QQ->data[ii]);
                ii=(ii+1)%MAXSIZE;
        }
        printf("\n");
}

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if(IsEmpty(QQ)==1){printf("队列为空。\n");return 0;}

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        return 1;
}
         

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
'
运行

3.循环队列的数组实现，队尾指针指向队尾元素，没有length的辅助变量。

代码实现如下：

/*
        程序名：seqqueue3.c，此程序演示循环队列的数组实现，队尾指针指向队尾元素，没有length的辅助变量。
 */

#include <stdio.h>
#include <string.h>

#define MAXSIZE 10       // 循环队列的最大长度，最多可以存放MAXSIZE-1个元素。

typedef int ElemType;

typedef struct
{
        ElemType data[MAXSIZE];         //用数组存储循环队列中的元素。
        int front;                      //头指针，指向队头元素。
        int rear;                       //尾指针，指向队尾元素的下一个元素。

}SeqQueue,*PSeqQueue;

//循环队列初始化操作
void InitQueue(PSeqQueue QQ);

//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee);

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ);

// 清空循环队列。
void Clear(PSeqQueue QQ);

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ);

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ);

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ);

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee);


int main()
{
        SeqQueue qq;
        
        InitQueue(&qq);

        printf("队列的长度为:%d\n",Length(&qq));

        printf("向队列中插入元素:1,2,3,4,5,6,7,8,9,10。\n");
        ElemType ee;

        ee=1;InQueue(&qq,&ee);
        ee=2;InQueue(&qq,&ee);
        ee=3;InQueue(&qq,&ee);
        ee=4;InQueue(&qq,&ee);
        ee=5;InQueue(&qq,&ee);
        ee=6;InQueue(&qq,&ee);
        ee=7;InQueue(&qq,&ee);
        ee=8;InQueue(&qq,&ee);
        ee=9;InQueue(&qq,&ee);
        ee=10;InQueue(&qq,&ee);

        //向队列中插入多余的元素，看是否会溢出
        ee=11;InQueue(&qq,&ee);
        ee=12;InQueue(&qq,&ee);
        printf("队列的长度为:%d\n",Length(&qq));

        printf("打印队列所有元素:\n");
        PrintQueue(&qq);

        printf("QQ->rear=%d,QQ->front=%d\n",qq.rear,qq.front);

        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);

        //将队列中出队
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);

        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);

        printf("元素（11、12、13、14、15）入队。\n");
  ee=11;  InQueue(&qq, &ee);
  ee=12;  InQueue(&qq, &ee);
  ee=13;  InQueue(&qq, &ee);
  ee=14;  InQueue(&qq, &ee);
  ee=15;  InQueue(&qq, &ee);

        printf("打印队列所有元素:\n");
        PrintQueue(&qq);
        return 0;
}

//循环队列初始化操作
void InitQueue(PSeqQueue QQ)
{
        Clear(QQ);
}
//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ)
{

        Clear(QQ);
}


// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( ((QQ->rear+2)%MAXSIZE)==QQ->front ){printf("队列已满。\n");return 0;}
        //if( Length(QQ)>=MAXSIZE-1 ){printf("队列已满。\n");return 0;}

        QQ->rear=(QQ->rear+1)%MAXSIZE;
        //将元素ee的值复制给队列中的数组  
        memcpy(&QQ->data[QQ->rear],ee,sizeof(ElemType));
        return 1;
}

//元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( (QQ->rear+1)%MAXSIZE == QQ->front ){printf("队列为空,出队失败。\n");return 0; }

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        QQ->front=(QQ->front+1)%MAXSIZE;

        return 1;
}

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return 0;}
        int len=(QQ->rear-QQ->front+1+MAXSIZE)%MAXSIZE;
        return len;
}

// 清空循环队列。
void Clear(PSeqQueue QQ)
{
	        if(QQ==NULL){printf("队列不存在。\n");return ;}
        memset(QQ->data,0,sizeof(QQ->data));
        QQ->front=0;
        QQ->rear=MAXSIZE-1;
}

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;

        if( (QQ->rear+1)%MAXSIZE==QQ->front )return 1;
        return 0;

}

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;
        if( ((QQ->rear+2)%MAXSIZE)==QQ->front )return 1;
        return 0;
}

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}
        int ii=QQ->front;
        while( ii != QQ->rear)
        {
                printf("%-3d ",QQ->data[ii]);

                ii=(ii+1)%MAXSIZE;
        }
        printf("%-3d",QQ->data[ii]);

        printf("\n");

}

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if(IsEmpty(QQ)==1){printf("队列为空。\n");return 0;}

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        return 1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
'
运行

4.循环队列的数组实现，队尾指针指向队尾元素，增加了length的辅助变量。

代码实现如下：

/*
        程序名：seqqueue4.c，此程序演示循环队列的数组实现，队尾指针指向队尾元素，增加了length的辅助变量。
 */

#include <stdio.h>
#include <string.h>

#define MAXSIZE 10       // 循环队列的最大长度，最多可以存放MAXSIZE-1个元素。

typedef int ElemType;

typedef struct
{
        ElemType data[MAXSIZE];         //用数组存储循环队列中的元素。
        int front;                      //头指针，指向队头元素。
        int rear;                       //尾指针，指向队尾元素的下一个元素。
        int length;

}SeqQueue,*PSeqQueue;

//循环队列初始化操作
void InitQueue(PSeqQueue QQ);

//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee);

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ);

// 清空循环队列。
void Clear(PSeqQueue QQ);

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ);

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ);

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ);

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee);


int main()
{
        SeqQueue qq;
             InitQueue(&qq);

        printf("队列的长度为:%d\n",Length(&qq));

        printf("向队列中插入元素:1,2,3,4,5,6,7,8,9,10。\n");
        ElemType ee;

        ee=1;InQueue(&qq,&ee);
        ee=2;InQueue(&qq,&ee);
        ee=3;InQueue(&qq,&ee);
        ee=4;InQueue(&qq,&ee);
        ee=5;InQueue(&qq,&ee);
        ee=6;InQueue(&qq,&ee);
        ee=7;InQueue(&qq,&ee);
        ee=8;InQueue(&qq,&ee);
        ee=9;InQueue(&qq,&ee);
        ee=10;InQueue(&qq,&ee);

        //向队列中插入多余的元素，看是否会溢出
        ee=11;InQueue(&qq,&ee);
        ee=12;InQueue(&qq,&ee);
        printf("队列的长度为:%d\n",Length(&qq));

        printf("打印队列所有元素:\n");
        PrintQueue(&qq);

        printf("QQ->rear=%d,QQ->front=%d\n",qq.rear,qq.front);

        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);

        //将队列中出队
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);

        GetHead(&qq,&ee);
        printf("取队头元素：%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);
        if(OutQueue(&qq,&ee)!=0)printf("出队元素为:%d\n",ee);

        printf("元素（11、12、13、14、15）入队。\n");
  ee=11;  InQueue(&qq, &ee);
  ee=12;  InQueue(&qq, &ee);
  ee=13;  InQueue(&qq, &ee);
  ee=14;  InQueue(&qq, &ee);
		
		  ee=15;  InQueue(&qq, &ee);

        printf("队列的长度为:%d\n",Length(&qq));
        printf("打印队列所有元素:\n");
        PrintQueue(&qq);
        return 0;
}

//循环队列初始化操作
void InitQueue(PSeqQueue QQ)
{
        Clear(QQ);
}
//销毁循环队列QQ。
void DestroyQueue(PSeqQueue QQ)
{

        Clear(QQ);
}


// 元素入队，返回值：0-失败；1-成功。
int InQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( QQ->length==MAXSIZE-1 ){printf("队列已满。\n");return 0;}
        //if( Length(QQ)>=MAXSIZE-1 ){printf("队列已满。\n");return 0;}

        QQ->rear=(QQ->rear+1)%MAXSIZE;
        //将元素ee的值复制给队列中的数组  
        memcpy(&QQ->data[QQ->rear],ee,sizeof(ElemType));
        QQ->length++;
        return 1;
}

//元素出队，返回值：0-失败；1-成功。
int OutQueue(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if( QQ->length==0 ){printf("队列为空,出队失败。\n");return 0; }

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        QQ->front=(QQ->front+1)%MAXSIZE;
        QQ->length--;
        return 1;
}

// 求循环队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return 0;}
        return QQ->length;
}

// 清空循环队列。
void Clear(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}
        memset(QQ->data,0,sizeof(QQ->data));
        QQ->front=0;
        QQ->rear=MAXSIZE-1;
        QQ->length=0;
}

// 判断循环队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;

        if( QQ->length==0 )return 1;
        return 0;

}

// 判断循环队列是否已满，返回值：1-已满，0-未满或失败。
int IsFull(PSeqQueue QQ)
{
        if(QQ==NULL)return 0;
        if( QQ->length==MAXSIZE-1 )return 1;
        return 0;
}

// 打印循环队列中全部的元素。
void PrintQueue(PSeqQueue QQ)
{
        if(QQ==NULL){printf("队列不存在。\n");return ;}

        int ii=QQ->front;
        while( ii != QQ->rear)
        {
                printf("%-3d ",QQ->data[ii]);

                ii=(ii+1)%MAXSIZE;
        }
        printf("%-3d",QQ->data[ii]);

        printf("\n");

}

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PSeqQueue QQ, ElemType *ee)
{
        if(QQ==NULL || ee==NULL){printf("队列不存在或者数据元素不存在。\n");return 0; }

        if(IsEmpty(QQ)==1){printf("队列为空。\n");return 0;}

        memcpy(ee,&QQ->data[QQ->front],sizeof(ElemType));
        return 1;
}
		


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
'
运行
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号