devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

循环队列 C++ 实现_用c++设计一个环形队列,用front 和rear 分别作为队头和队尾指针,另外用一个变量ta

作者：从前慢现在也慢 | 2024-06-12 07:44:28

赞

踩

用c++设计一个环形队列,用front 和rear 分别作为队头和队尾指针,另外用一个变量ta

文章目录

循环队列

为解决假溢出问题，采用循环队列，循环队列即一种逻辑上的环状结构，但在物理空间上仍然为顺序存储，即数组

循环队列示例图
其中 f 为头指针，指向队列的第一个元素，r 为尾指针，指向队尾元素的下一个位置。


在这里插入图片描述

由于循环队列的处理有三种方法，此处先不给出具体结构体的定义；详细实现和采用的方式有关；

判断入队时队尾指针应该如何变化

一般情况，队尾指针简单后移 (rear + 1) 即可，队头指针不变

在这里插入图片描述

而当出现多次出队列以后，队尾指针到达数组最后一位时 (如下图)

在这里插入图片描述

简单的 rear + 1 将不会满足实际情况，此时，rear = (rear + 1) % MAX 将满足实际情况。并且此公式也适用于一般情况。因此可以得出结论，入队列时，在队列未满时，元素入队，队尾元素 rear = (rear + 1) % MAX ；

入队列前需要判断队列是否为满；

判断出队时队头指针应该如何变化

当队列非空时，队头元素出队列，队头指针移动；

出队列的指针变化和入队列一样 front = (front + 1) % MAX

在这里插入图片描述

出队需判断队列是否为空；

接下来讨论怎样判断队列的满或者空；

判断队列是否已满或已空

当队列已满时，有如下情况：

左图为一直入队列的情况，右图为出队列一次的情况

在这里插入图片描述

从图中可以看出，队满时，front = rear；是否能使用这个条件判断队列已满呢？再看队列为空时；

在这里插入图片描述

可见，在这种情况下不能使用 f = r 来判断队列为空，也不能判断队列已满；对此，有一些处理方式；

不同情况的实现方式

方式一

少使用一个存储单元，这样就可以避免队列满时 f = r，并且此时 f = r 可以判断队列为空；

在这里插入图片描述

此时，队满：(rear + 1) % MAX = front 队空：rear = front

结构体

typedef int Type;
#define MAX 20
typedef struct {
    Type data[MAX];
    int front, rear;
} SqQueue;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

初始化

void InitQueue(SqQueue &Q) {
    Q.front = 0;
    Q.rear = 0;
}

  • 1
  • 2
  • 3
  • 4

入队列：(Q.rear + 1) % MAX == Q.front 为满

bool EnQueue(SqQueue &Q, Type x) {
    if((Q.rear + 1) % MAX == Q.front) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

出队列：Q.front == Q.rear 时为空

bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.front == Q.rear) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAX;
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

方式二

在结构体中设置一个表示队列大小的变量 size， 入队时加一，出队时减一，指针随之变化；

结构体

typedef struct {
    Type data[MAX];
    int front, rear;
    int size;
} SqQueue;

  • 1
  • 2
  • 3
  • 4
  • 5

初始化

void InitQueue(SqQueue &Q) {
    Q.front = 0;
    Q.rear = 0;
    Q.size = 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5

入队列代码： size = MAX 时队列已满，不能入队列；

bool EnQueue(SqQueue &Q, Type x) {
    if(Q.size == MAX) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    Q.size++;
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

出队列：size = 0 为空，不能出队列；

bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.size == 0) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAX;
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

方式三

在结构体中设置标志 tag， tag = 0 &&Q.front == Q.rear 表示队列为空， tag = 1 && Q.front == Q.rear 表示队列已满。初始时 tag 为 0，此后，若遇入队列后 Q.front == Q.rear 则表示队列必满，置 tag = 1;若遇到出队列后 Q.front == Q.rear 则表示队列必空；由此可写出其入队列和出队列代码；

结构体

typedef struct {
    Type data[MAX];
    int front, rear;
    int tag;
} SqQueue;

  • 1
  • 2
  • 3
  • 4
  • 5

入队列：

Q.tag == 1 && Q.front == Q.rear 表示队列已满，若队列未满，则入队列，入队列后若 Q.front == Q.rear 则队列必满，此时置 tag 为 1；

bool EnQueue(SqQueue &Q, Type x) {
    if(Q.tag == 1 && Q.front == Q.rear) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    if(Q.front == Q.rear) {			//若入栈后相等，此时队列必满
        Q.tag = 1;
    }
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

出队列：

Q.tag == 0 && Q.front == Q.rear 表示队列已空，若队列未满，则入队列，出队列后若 Q.front == Q.rear 则队列必空，此时置 tag 为 0；

bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.tag == 0 && Q.front == Q.rear) { //队列为空时
        return false;
    }
    x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAX;
    if(Q.front == Q.rear) {			//若出队列后相等，此时队列必空
        Q.tag = 0;
    }
    return true;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

判空

  1. 空一个位置

    只有空的时候会出现 Q.front == Q.rear

    bool QueueEmpty(SqQueue Q) {
    if(Q.front == Q.rear) {
        return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

  2. 设置 size

    bool QueueEmpty(SqQueue Q) {
    if(Q.size == 0) {
        return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

  3. 设置 tag

    bool QueueEmpty(SqQueue Q) {
    if(Q.front == Q.rear && Q.tag == 0) {
        return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

计算队列元素个数

  1. 方式一

    int length(SqQueue Q) {
    return (Q.rear + MAX - Q.front) % MAX;
}

    • 1
    • 2
    • 3

  2. 方式二

    int length(SqQueue Q) {
    return Q.size;
}

    • 1
    • 2
    • 3

  3. 方式三

    由于队列满时 Q.front == Q.rear，故需单独对队列满时进行处理

    int length(SqQueue Q) {
    if(Q.tag == 1 && Q.front == Q.rear) {
        return MAX;
    }
    return (Q.rear + MAX - Q.front) % MAX;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

整体实现

由于有三种不同的循环队列处理方式，因此也使用三种不同方式

方式一

数组空一个位置

测试方案

测试方案：依次入队列至如下情况，此时将不能入队列， rear = 7，front = 0；

在这里插入图片描述

出队列四次，入队列两次，此时队头为 4，队尾指针为 1；

在这里插入图片描述

出队列置队列为空，进行判空

在这里插入图片描述

#include<iostream>
using namespace std;

typedef char Type;
#define MAX 8
typedef struct {
    Type data[MAX];
    int front, rear;
} SqQueue;


void InitQueue(SqQueue &Q) {
    Q.front = 0;
    Q.rear = 0;
}

bool EnQueue(SqQueue &Q, Type x) {
    if((Q.rear + 1) % MAX == Q.front) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    return true;
}


bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.front == Q.rear) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAX;
    return true;
}


bool QueueEmpty(SqQueue Q) {
    if(Q.front == Q.rear) {
        return true;
    }
    return false;
}

int length(SqQueue Q) {
    return (Q.rear + MAX - Q.front) % MAX;
}


int main() {
    SqQueue queue;
    InitQueue(queue);
    char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    for(int i = 0; i < 7; i++) {
        EnQueue(queue, chs[i]);
    }
    if(!EnQueue(queue, 'x')) {
        cout << "队列已满，入队失败" << endl;
    }
    cout << queue.front << " " << queue.rear << endl;

    //出队四次
    Type x;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;

    cout << "队列元素个数为 " << length(queue) << endl;
    //入队两次
    EnQueue(queue, 'h');
    EnQueue(queue, 'i');
    cout << "队列元素个数为 " << length(queue) << endl;

    cout << queue.front << " " << queue.rear << endl;

    while(!QueueEmpty(queue)) {
        DeQueue(queue, x);
        cout << x << " ";
    }

    return 0;
}

/*
队列已满，入队失败
0 7
a
b
c
d
队列元素个数为 3
队列元素个数为 5
4 1
e f g h i
*/

  • 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

通过结果分析，和手动模拟一致；

方式二

结构体中设置 size

由于此类情况可以使用全部空间，对此进行检验

测试方案

测试方案：依次入队列至如下情况，此时， rear = 7，front = 0；
在这里插入图片描述

出队列四次，入队列五次，此时队列已满；将不能继续入队，指针均为 4

在这里插入图片描述

出队列置队列为空，进行判空

#include<iostream>
using namespace std;

typedef char Type;
#define MAX 8
typedef struct {
    Type data[MAX];
    int front, rear;
    int size;
} SqQueue;


void InitQueue(SqQueue &Q) {
    Q.front = 0;
    Q.rear = 0;
    Q.size = 0;
}




bool EnQueue(SqQueue &Q, Type x) {
    if(Q.size == MAX) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    Q.size++;
    return true;
}


bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.size == 0) {
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAX;
    Q.size--;
    return true;
}


bool QueueEmpty(SqQueue Q) {
    if(Q.size == 0) {
        return true;
    }
    return false;
}

int length(SqQueue Q) {
    return Q.size;
}


int main() {
    SqQueue queue;
    InitQueue(queue);
    char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    for(int i = 0; i < 7; i++) {
        EnQueue(queue, chs[i]);
    }
    cout << queue.front << " " << queue.rear << endl;

    //出队四次
    Type x;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;

    cout << "队列元素个数为 " << length(queue) << endl;
    //入队五次
    EnQueue(queue, 'h');
    EnQueue(queue, 'i');
    EnQueue(queue, 'j');
    EnQueue(queue, 'k');
    EnQueue(queue, 'l');
    cout << "队列元素个数为 " << length(queue) << endl;
    cout << queue.front << " " << queue.rear << endl;
    if(!EnQueue(queue, 'x')) {
        cout << "队列已满，入队失败" << endl;
    }

    while(!QueueEmpty(queue)) {
        DeQueue(queue, x);
        cout << x << " ";
    }

    return 0;
}
/*
0 7
a
b
c
d
队列元素个数为 3
队列元素个数为 8
4 4
队列已满，入队失败
e f g h i j k l
*/

  • 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

方式三

此处和方式二使用同样的测试方案；

#include<iostream>
using namespace std;

typedef char Type;
#define MAX 8
typedef struct {
    Type data[MAX];
    int front, rear;
    int tag;
} SqQueue;


void InitQueue(SqQueue &Q) {
    Q.front = 0;
    Q.rear = 0;
    Q.tag = 0;
}

bool EnQueue(SqQueue &Q, Type x) {
    if(Q.tag == 1 && Q.front == Q.rear) {
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX;
    if(Q.front == Q.rear) {			//若入栈后相等，此时队列必满
        Q.tag = 1;
    }
    return true;
}


bool DeQueue(SqQueue &Q, Type &x) {
    if(Q.tag == 0 && Q.front == Q.rear) { //队列为空时
        return false;
    }
    x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAX;
    if(Q.front == Q.rear) {			//若出栈后相等，此时队列必空
        Q.tag = 0;
    }
    return true;
}


bool QueueEmpty(SqQueue Q) {
    if(Q.front == Q.rear && Q.tag == 0) {
        return true;
    }
    return false;
}
int length(SqQueue Q) {
    if(Q.tag == 1 && Q.front == Q.rear) {
        return MAX;
    }
    return (Q.rear + MAX - Q.front) % MAX;
}


int main() {
    SqQueue queue;
    InitQueue(queue);
    char chs[7] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    for(int i = 0; i < 7; i++) {
        EnQueue(queue, chs[i]);
    }
    cout << queue.front << " " << queue.rear << endl;

    //出队四次
    Type x;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;
    DeQueue(queue, x);
    cout << x << endl;

    cout << "队列元素个数为 " << length(queue) << endl;
    //入队五次
    EnQueue(queue, 'h');
    EnQueue(queue, 'i');
    EnQueue(queue, 'j');
    EnQueue(queue, 'k');
    EnQueue(queue, 'l');
    cout << "队列元素个数为 " << length(queue) << endl;
    cout << queue.front << " " << queue.rear << endl;
    if(!EnQueue(queue, 'x')) {
        cout << "队列已满，入队失败" << endl;
    }

    while(!QueueEmpty(queue)) {
        DeQueue(queue, x);
        cout << x << " ";
    }

    return 0;
}
/*
0 7
a
b
c
d
队列元素个数为 3
队列元素个数为 8
4 4
队列已满，入队失败
e f g h i j k l
*/

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/707092
推荐阅读
相关标签

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

  

闽ICP备14008679号