你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

数据结构：队列——队列的概念、顺序和链式存储的实现_队列的顺序存储和链式存储的实现

作者：你好赵伟 | 2024-05-08 00:07:43

踩

队列的顺序存储和链式存储的实现

基本概念

队列定义：
队列也是一种受限的线性表，只允许一端插入，另一端删除

基本操作

void InitQueue(SqQueue &Q)  			初始化队列
bool QueueEmpty(SqQueue Q)				判断队空
bool EnQueue(SqQueue &Q,ElemType e)		入队
bool DnQueue(SqQueue &Q,ElemType &e)	出队
bool GetHead(SqQueue Q,ElemType &e)		读队头元素
1
2
3
4
5

顺序队列和循环队列
1. 顺序队列
  下图表示队列的初始化、入队、出队，可以看出
```
队初始化：front=rear=0
队空：front==0&&rear==0
1
2
```
  那么队满呢？
  假设rear=maxsize表示队满，当有元素出栈时，rear仍=maxsize，但此时队列是满的，所以rear==maxsize不能作为队满的条件
  
  那么，用rear-front==maxsize 呢？当有元素出队而队中仍有元素时，队尾指针已经到达队末尾，不会有元素能进入队中，队不会满。
2. 循环队列
  由于顺序队列的不足，因此引出循环队列的概念将顺序队列臆造为一个环状的空间。如图：

队列的顺序存储（循环队列）

牺牲一个单元来区分队空和队满

入队

图解

代码

/*入队*/
bool EnQueue(SqQueue &Q,ElemType e){
    if(QueueFull(Q))return false;
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}
1
2
3
4
5
6
7

出队

图解

代码

/*出队*/
bool DnQueue(SqQueue &Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
1
2
3
4
5
6
7

栈空和栈满理解

队空：front==rear
队满：(rear+1)%maxsize==front
1
2

以下两种情况都属于栈满，该方法需要牺牲掉一个空间来区分栈空和栈满,这个空间并不是指特定的，只是在队头和队尾之间留一个空。
在这里插入图片描述

完整代码

#include "stdio.h"
#include "stdlib.h"

#define MaxSize 50

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];     //存放元素
    int front,rear;             //队头指针和队尾指针
}SqQueue;

/*初始化队列*/
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
}
/*判断队空*/
bool QueueEmpty(SqQueue Q){
    if (Q.rear==Q.front)return true;
    else return false;
}

/*判断队满*/
bool QueueFull(SqQueue Q){
    if ((Q.rear+1)%MaxSize==Q.front)return true;
    else return false;
}

/*入队*/
bool EnQueue(SqQueue &Q,ElemType e){
    if(QueueFull(Q))return false;
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

/*出队*/
bool DnQueue(SqQueue &Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

/*读队头元素*/
bool GetHead(SqQueue Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    return true;
}

/*队长*/
int Length(SqQueue Q){
    return (Q.rear-Q.front+MaxSize)%MaxSize;
}

/*遍历*/
void Proint(SqQueue Q){
    for (int i = Q.front; i < Q.rear; ++i) {       
        printf("%d  ",Q.data[i]);
    }
    printf("\n");
}

int main(){
    SqQueue Q;

    printf("***************************************\n");
    printf("********  1.初始化队  2.空队判断  ********\n");
    printf("********  3. 进 队   4. 出 队   ********\n");
    printf("********  5.读取队首  6.队满判断  ********\n");
    printf("********  7. 遍 历   8. 队 长   ********\n");
    printf("********  0. 退 出             ********\n");
    printf("***************************************\n");

    bool flag= true;
    int x;
    ElemType e;
    while(flag){
        printf("请输入命令：");
        scanf("%d",&x);
        switch (x) {
            case 1:
                InitQueue(Q);
                printf("\t空队初始化完成\n");
                break;
            case 2:
                if(QueueEmpty(Q)) printf("\t该队是空队\n");
                else printf("\t该队不是空队\n");
                break;
            case 3:
                printf("\t请输入要进队的元素：");
                int a;
                scanf("%d",&e);
                if(EnQueue(Q,e))printf("\t元素入队成功\n");
                else printf("\t元素入队失败\n");
                break;
            case 4:
                if(DnQueue(Q,e))
                    printf("\t元素出队成功,出队的元素为：%d\n",e);
                else
                    printf("\t元素出队失败\n");
                break;
            case 5:
                if(GetHead(Q,e))
                    printf("\t队首元素为：%d\n",e);
                else
                    printf("\t该队为空栈\n");
                break;
            case 6:
                if(QueueFull(Q))
                    printf("\t该队已满\n");
                else
                    printf("\t该队还未满\n");
                break;
            case 7:
                printf("\t当前队中元素有：");
                Proint(Q);
                break;
            case 8:
                printf("\t当前队长为：%d\n",Length(Q));
                break;
            case 0:
                printf("退出成功\n");
                flag= false;
                break;
            default:
                printf("命令错误，请重新输入！！！");
                break;
        }
    }
}

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

运行截图

在这里插入图片描述

增设size表示元素个数的数据成员

栈空和栈满理解

typedef struct {
ElemType data[MaxSize]; //存放元素
int front,rear; //队头指针和队尾指针
int size;//表示队中成员个数
}SqQueue;

队空：size=0
队满：size=maxsize

完整代码

#include "stdio.h"
#include "stdlib.h"

#define MaxSize 50

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];     //存放元素
    int front,rear;             //队头指针和队尾指针
    int size;
}SqQueue;

/*初始化队列*/
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
    Q.size=0;
}
/*判断队空*/
bool QueueEmpty(SqQueue Q){
    if (Q.size==0)return true;
    else return false;
}

/*判断队满*/
bool QueueFull(SqQueue Q){
    if (Q.size==MaxSize)return true;
    else return false;
}

/*入队*/
bool EnQueue(SqQueue &Q,ElemType e){
    if(QueueFull(Q))return false;
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    Q.size++;
    return true;
}

/*出队*/
bool DnQueue(SqQueue &Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    Q.size--;
    return true;
}

/*读队头元素*/
bool GetHead(SqQueue Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    return true;
}

/*队长*/
int Length(SqQueue Q){
    return Q.size;
}

/*遍历*/
void Proint(SqQueue Q){
    for (int i = Q.front; i < Q.rear; ++i) {       
        printf("%d  ",Q.data[i]);
    }
    printf("\n");
}

int main(){
    SqQueue Q;

    printf("***************************************\n");
    printf("********  1.初始化队  2.空队判断  ********\n");
    printf("********  3. 进 队   4. 出 队   ********\n");
    printf("********  5.读取队首  6.队满判断  ********\n");
    printf("********  7. 遍 历   8. 队 长   ********\n");
    printf("********  0. 退 出             ********\n");
    printf("***************************************\n");

    bool flag= true;
    int x;
    ElemType e;
    while(flag){
        printf("请输入命令：");
        scanf("%d",&x);
        switch (x) {
            case 1:
                InitQueue(Q);
                printf("\t空队初始化完成\n");
                break;
            case 2:
                if(QueueEmpty(Q)) printf("\t该队是空队\n");
                else printf("\t该队不是空队\n");
                break;
            case 3:
                printf("\t请输入要进队的元素：");
                int a;
                scanf("%d",&e);
                if(EnQueue(Q,e))printf("\t元素入队成功\n");
                else printf("\t元素入队失败\n");
                break;
            case 4:
                if(DnQueue(Q,e))
                    printf("\t元素出队成功,出队的元素为：%d\n",e);
                else
                    printf("\t元素出队失败\n");
                break;
            case 5:
                if(GetHead(Q,e))
                    printf("\t队首元素为：%d\n",e);
                else
                    printf("\t该队为空栈\n");
                break;
            case 6:
                if(QueueFull(Q))
                    printf("\t该队已满\n");
                else
                    printf("\t该队还未满\n");
                break;
            case 7:
                printf("\t当前队中元素有：");
                Proint(Q);
                break;
            case 8:
                printf("\t当前队长为：%d\n",Length(Q));
                break;
            case 0:
                printf("退出成功\n");
                flag= false;
                break;
            default:
                printf("命令错误，请重新输入！！！");
                break;
        }
    }
}

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

运行截图

在这里插入图片描述

增设tag数据成员

栈空和栈满理解

typedef struct {
ElemType data[MaxSize]; //存放元素
int front,rear; //队头指针和队尾指针
int tag;//用0、1来表示
}SqQueue;

队空：rear == front&&tag == 0
队满：rear == front&&tag == 1

完整代码

#include "stdio.h"
#include "stdlib.h"

#define MaxSize 50

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];     //存放元素
    int front,rear;             //队头指针和队尾指针
    int tag;
}SqQueue;

/*初始化队列*/
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
    Q.tag=0;
}
/*判断队空*/
bool QueueEmpty(SqQueue Q){
    if (Q.rear==Q.front&&Q.tag==0)return true;
    else return false;
}

/*判断队满*/
bool QueueFull(SqQueue Q){
    if (Q.rear==Q.front&&Q.tag==1)return true;
    else return false;
}

/*入队*/
bool EnQueue(SqQueue &Q,ElemType e){
    if(QueueFull(Q))return false;
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    Q.tag=1;
    return true;
}

/*出队*/
bool DnQueue(SqQueue &Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    Q.tag=0;
    return true;
}

/*读队头元素*/
bool GetHead(SqQueue Q,ElemType &e){
    if(QueueEmpty(Q))return false;
    e=Q.data[Q.front];
    return true;
}

/*队长*/
int Length(SqQueue Q){
    return (Q.rear-Q.front+MaxSize)%MaxSize;
}

/*遍历*/
void Proint(SqQueue Q){
    for (int i = Q.front; i < Q.rear; ++i) {       
        printf("%d  ",Q.data[i]);
    }
    printf("\n");
}

int main(){
    SqQueue Q;

    printf("***************************************\n");
    printf("********  1.初始化队  2.空队判断  ********\n");
    printf("********  3. 进 队   4. 出 队   ********\n");
    printf("********  5.读取队首  6.队满判断  ********\n");
    printf("********  7. 遍 历   8. 队 长   ********\n");
    printf("********  0. 退 出             ********\n");
    printf("***************************************\n");

    bool flag= true;
    int x;
    ElemType e;
    while(flag){
        printf("请输入命令：");
        scanf("%d",&x);
        switch (x) {
            case 1:
                InitQueue(Q);
                printf("\t空队初始化完成\n");
                break;
            case 2:
                if(QueueEmpty(Q)) printf("\t该队是空队\n");
                else printf("\t该队不是空队\n");
                break;
            case 3:
                printf("\t请输入要进队的元素：");
                int a;
                scanf("%d",&e);
                if(EnQueue(Q,e))printf("\t元素入队成功\n");
                else printf("\t元素入队失败\n");
                break;
            case 4:
                if(DnQueue(Q,e))
                    printf("\t元素出队成功,出队的元素为：%d\n",e);
                else
                    printf("\t元素出队失败\n");
                break;
            case 5:
                if(GetHead(Q,e))
                    printf("\t队首元素为：%d\n",e);
                else
                    printf("\t该队为空栈\n");
                break;
            case 6:
                if(QueueFull(Q))
                    printf("\t该队已满\n");
                else
                    printf("\t该队还未满\n");
                break;
            case 7:
                printf("\t当前队中元素有：");
                Proint(Q);
                break;
            case 8:
                printf("\t当前队长为：%d\n",Length(Q));
                break;
            case 0:
                printf("退出成功\n");
                flag= false;
                break;
            default:
                printf("命令错误，请重新输入！！！");
                break;
        }
    }
}
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

运行截图

在这里插入图片描述

队列的链式存储

队列的链式存储，类似于单链表，入队——头插法，出队——删除首元结点。
假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列。这样就不会出现存储分配不合理和“溢出”现象

队列的存储类型（比较特殊）

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode *front,*rear;
}liQueue;
1
2
3
4
5
6
7
8

完整代码

#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode *front,*rear;
}liQueue;

/*初始化队列*/
void InitQueue(liQueue &Q){
   Q.rear=Q.front=(LinkNode*) malloc(sizeof(LinkNode));
   Q.front->next=NULL;
}
/*判断队空*/
bool QueueEmpty(liQueue Q){
    if (Q.rear==Q.front)return true;
    else return false;
}


/*入队*/
bool EnQueue(liQueue &Q,ElemType e){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=e;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
    return true;
}

/*出队*/
bool DnQueue(liQueue &Q,ElemType &e){
    if (QueueEmpty(Q))return false;
    LinkNode *p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if (Q.rear==p)
        Q.rear==Q.front;
    free(p);
    return true;
}

/*读队头元素*/
bool GetHead(liQueue Q,ElemType &e){
    if (QueueEmpty(Q))return false;
    e=Q.front->next->data;
    return true;
}

/*队长*/
int Length(liQueue Q){
    int i=0;
    LinkNode *p=Q.front->next;
    if (p!=Q.rear){
        p=p->next;
        i++;
    }
    return ++i;
}

/*遍历*/
void Proint(liQueue Q){
    LinkNode *p=Q.front->next;
    while (p!=NULL){
        printf("%d  ",p->data);
        p=p->next;
    }
    printf("\n");
}

int main(){
    liQueue Q;

    printf("***************************************\n");
    printf("********  1.初始化队  2.空队判断  ********\n");
    printf("********  3. 进 队   4. 出 队   ********\n");
    printf("********  5.读取队首  6. 队 长  ********\n");
    printf("********  7. 遍 历   0. 退 出   ********\n");
    printf("***************************************\n");

    bool flag= true;
    int x;
    ElemType e;
    while(flag){
        printf("请输入命令：");
        scanf("%d",&x);
        switch (x) {
            case 1:
                InitQueue(Q);
                printf("\t空队初始化完成\n");
                break;
            case 2:
                if(QueueEmpty(Q)) printf("\t该队是空队\n");
                else printf("\t该队不是空队\n");
                break;
            case 3:
                printf("\t请输入要进队的元素：");
                int a;
                scanf("%d",&e);
                if(EnQueue(Q,e))printf("\t元素入队成功\n");
                else printf("\t元素入队失败\n");
                break;
            case 4:
                if(DnQueue(Q,e))
                    printf("\t元素出队成功,出队的元素为：%d\n",e);
                else
                    printf("\t元素出队失败\n");
                break;
            case 5:
                if(GetHead(Q,e))
                    printf("\t队首元素为：%d\n",e);
                else
                    printf("\t该队为空栈\n");
                break;
            case 6:
                printf("\t当前队长为：%d\n",Length(Q));
                break;
                break;
            case 7:
                printf("\t当前队中元素有：");
                Proint(Q);
                break;
            case 0:
                printf("退出成功\n");
                flag= false;
                break;
            default:
                printf("命令错误，请重新输入！！！");
                break;
        }
    }
}

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

运行截图

在这里插入图片描述

参考资料

《王道：数据结构考研复习指导》

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/551880