Guff_9hys

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

热门标签

队列的实现，数组队列，链表队列，循环队列简单详细（附源码）_以数组形式构建一个(顺序)队列,实现进队、出队、判定队是否为空等操作

作者：Guff_9hys | 2024-08-02 09:34:04

踩

以数组形式构建一个(顺序)队列,实现进队、出队、判定队是否为空等操作

CSDN博客：队列的三种实现方式

本篇文章的读者是初学者，旨在帮助他们了解数据结构中的队列，同时也检验自己的水平，从而共同提高代码水平和效率，共勉之。
本文为读者详细介绍了队列的数组实现和链表实现，加循环队列。

1. 顺序队列

1.1 结构定义

#include<iostream>

const int MAX_SIZE = 10;
using namespace std;
typedef int QueueElementType;

// 定义顺序队列结构
struct SqQueue {
    int front;                // 队头指针
    int rear;                 // 队尾指针
    QueueElementType elements[MAX_SIZE];  // 队列元素数组
} queue;;
1
2
3
4
5
6
7
8
9
10
11
12

1.2 初始化队列

void initQueue(SqQueue& queue) {
    queue.front = 0;
    queue.rear = 0;
}
1
2
3
4

1.3 判断队列是否为空

bool isQueueEmpty(SqQueue queue) {
    if (queue.front == queue.rear) {
        // cout << "队列为空。\n";
        return true;
    }
    // cout << "队列不为空。\n";
    return false;
}
1
2
3
4
5
6
7
8

1.4 判断队列是否为满

bool isQueueFull(SqQueue queue) {
    if (queue.rear == MAX_SIZE) {
        cout << "队列已满。\n";
        return true;
    }
    cout << "队列未满。\n";
    return false;
}
1
2
3
4
5
6
7
8

1.5 清空队列

void clearQueue(SqQueue& queue) {
    queue.front = 0;
    queue.rear = 0;
}
1
2
3
4

1.6 入队

void enqueue(SqQueue& queue, QueueElementType e) {
    if (queue.rear == MAX_SIZE) {
        cout << "入队失败！队列已满。\n";
        return ;
    }
    queue.elements[queue.rear] = e;
    queue.rear++;
    return ;
}
1
2
3
4
5
6
7
8
9

1.7 出队

void dequeue(SqQueue& queue, QueueElementType& e) {
    if (isQueueEmpty(queue)) {
        cout << "出队失败！队列为空。\n";
        return ;
    }
    queue.front++;
    e = queue.elements[queue.front - 1];
    return ;
}
1
2
3
4
5
6
7
8
9

1.8 计算队列中元素个数

int queueCount(SqQueue queue) {
    return queue.rear - queue.front;
}
1
2
3

1.9 打印队列中元素

void printQueue(SqQueue queue) {
    if (queue.front == queue.rear)
        cout << "打印失败！队列为空。\n";
    while (queue.rear - queue.front > 0) {
        cout << queue.elements[queue.front] << "  ";
        queue.front++;
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9

完整代码：

#include<iostream>

const int MAX_SIZE = 10;
using namespace std;
typedef int QueueElementType;

// 定义顺序队列结构
struct SqQueue {
    int front;                // 队头指针
    int rear;                 // 队尾指针
    QueueElementType elements[MAX_SIZE];  // 队列元素数组
} queue;

// 初始化队列
void initQueue(SqQueue& queue) {
    queue.front = 0;
    queue.rear = 0;
}

// 判断队列是否为空
bool isQueueEmpty(SqQueue queue) {
    if (queue.front == queue.rear) {
        // cout << "队列为空。\n";
        return true;
    }
    // cout << "队列不为空。\n";
    return false;
}

// 判断队列是否为满
bool isQueueFull(SqQueue queue) {
    if (queue.rear == MAX_SIZE) {
        cout << "队列已满。\n";
        return true;
    }
    cout << "队列未满。\n";
    return false;
}

// 清空队列
void clearQueue(SqQueue& queue) {
    queue.front = 0;
    queue.rear = 0;
}

// 入队，插入元素e为新的队尾元素
void enqueue(SqQueue& queue, QueueElementType e) {
    if (queue.rear == MAX_SIZE) {
        cout << "入队失败！队列已满。\n";
        return ;
    }
    queue.elements[queue.rear] = e;
    queue.rear++;
    return ;
}

// 出队，若队列不空则删除队头元素，用e返回其值
void dequeue(SqQueue& queue, QueueElementType& e) {
    if (isQueueEmpty(queue)) {
        cout << "出队失败！队列为空。\n";
        return ;
    }
    queue.front++;
    e = queue.elements[queue.front - 1];
    return ;
}

// 计算队列中元素个数
int queueCount(SqQueue queue) {
    return queue.rear - queue.front;
}

// 打印队列中元素
void printQueue(SqQueue queue) {
    if (queue.front == queue.rear)
        cout << "打印失败！队列为空。\n";
    while (queue.rear - queue.front > 0) {
        cout << queue.elements[queue.front] << "  ";
        queue.front++;
    }
    cout << endl;
}

int main() {
    SqQueue queue;
    QueueElementType element;
    initQueue(queue);
    cout << "输入元素到队列中（输入-1终止）：";
    cin >> element;
    while (element != -1) {
        enqueue(queue, element);
        cout << "输入元素到队列中（输入-1终止）：";
        cin >> element;
    }
    cout << "打印队列：";
    printQueue(queue);
    cout << "出队，打印队尾元素和队列：";
    dequeue(queue, element);
    cout << "队尾元素=" << element << ";" << "打印队列元素：";
    printQueue(queue);
    cout << "队列中元素个数=" << queueCount(queue) << endl;
    return 0;
}

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

2. 链队列

2.1 结构定义

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;
typedef int ElementType;

typedef struct QueueNode {
    ElementType data;
    struct QueueNode *next;
} QueueNode, *QueueNodePtr;

typedef struct {
    QueueNodePtr front, rear;
} LinkQueue, *LinkQueuePtr;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 初始化链队列

void initialize_queue(LinkQueuePtr &queue) {
    queue = (LinkQueuePtr)malloc(sizeof(LinkQueue));
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    if (queue != NULL && s != NULL) {
        s->next = NULL;
        queue->front = queue->rear = s;
    }
}

1
2
3
4
5
6
7
8
9

2.3 入队

void enqueue(LinkQueuePtr &queue, int x) {
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    s->next = NULL;
    s->data = x;
    queue->rear->next = s;
    queue->rear = s;
}
1
2
3
4
5
6
7

2.4 出队

void dequeue(LinkQueuePtr &queue, int &x) {
    if (queue->front == queue->rear) {
        cout << "队列为空，出队失败" << endl;
    }
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    s = queue->front->next;
    x = s->data;
    queue->front->next = s->next;
    if (s == queue->rear) {
        queue->rear = queue->front;
    }
    free(s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5 获取队头元素

int front(LinkQueuePtr &queue) {
    if (queue->front == queue->rear) {
        return 0;
    } else {
        return queue->front->next->data;
    }
}
1
2
3
4
5
6
7

2.6 打印队列中元素

void print_queue(LinkQueuePtr queue) {
    if (queue->rear == queue->front) {
        cout << "空";
    } else {
        QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
        p = queue->front->next;
        while (p) {
            cout << p->data << ' ';
            p = p->next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

完整代码：

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;
typedef int ElementType;

typedef struct QueueNode {
    ElementType data;
    struct QueueNode *next;
} QueueNode, *QueueNodePtr;

typedef struct {
    QueueNodePtr front, rear;
} LinkQueue, *LinkQueuePtr;

void initialize_queue(LinkQueuePtr &queue) {
    queue = (LinkQueuePtr)malloc(sizeof(LinkQueue));
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    if (queue != NULL && s != NULL) {
        s->next = NULL;
        queue->front = queue->rear = s;
    }
}

void enqueue(LinkQueuePtr &queue, int x) {
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    s->next = NULL;
    s->data = x;
    queue->rear->next = s;
    queue->rear = s;
}

void dequeue(LinkQueuePtr &queue, int &x) {
    if (queue->front == queue->rear) {
        cout << "队列为空，出队失败" << endl;
    }
    QueueNodePtr s = (QueueNodePtr)malloc(sizeof(QueueNode));
    s = queue->front->next;
    x = s->data;
    queue->front->next = s->next;
    if (s == queue->rear) {
        queue->rear = queue->front;
    }
    free(s);
}

int front(LinkQueuePtr &queue) {
    if (queue->front == queue->rear) {
        return 0;
    } else {
        return queue->front->next->data;
    }
}

void print_queue(LinkQueuePtr queue) {
    if (queue->rear == queue->front) {
        cout << "空";
    } else {
        QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
        p = queue->front->next;
        while (p) {
            cout << p->data << ' ';
            p = p->next;
        }
    }
}

int main() {
    LinkQueuePtr queue;
    initialize_queue(queue);
    int digit, number;
    printf("输入位数：");
    scanf("%d", &digit);
    while (digit--) {
        printf("输入数：");
        scanf("%d", &number);
        enqueue(queue, number);
    }
    cout << "队头:" << front(queue) << endl;
    print_queue(queue);
    int dequeue_digit, dequeued_number;
    printf("输入出队位数：");
    scanf("%d", &dequeue_digit);
    while (dequeue_digit--) {
        dequeue(queue, dequeued_number);
        printf("%d\n", dequeued_number);
    }
    print_queue(queue);
    return 0;
}

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

3. 循环队列

3.1 结构定义

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

#define MAX_SIZE 100
typedef int ElementType;

typedef struct {
    int front;
    int rear;
    ElementType data[MAX_SIZE];
} SqQueue, *SqQueuePtr;

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 初始化循环队列

void initialize_queue(SqQueuePtr &Q) {
    Q = (SqQueuePtr)malloc(sizeof(SqQueue));
    if (Q != NULL) {
        Q->front = 0;
        Q->rear = 0;
    }
}
1
2
3
4
5
6
7

3.3 入队

bool enqueue(SqQueuePtr &Q, int num) {
    if ((Q->rear + 1) % MAX_SIZE == Q->front) {
        return false;
    }
    Q->data[Q->rear] = num;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return true;
}
1
2
3
4
5
6
7
8

3.4 出队

bool dequeue(SqQueuePtr &Q, int &e) {
    if (Q->rear == Q->front) {
        printf("队列为空\n");
        return false;
    }
    e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return true;
}
1
2
3
4
5
6
7
8
9

3.5 获取循环队列长度

int queue_length(SqQueuePtr Q) {
    return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}

1
2
3
4

3.6 打印循环队列中元素

void print_all(SqQueuePtr &Q) {
    if (Q->front == Q->rear) {
        printf("空的\n");
    }
    int len = queue_length(Q);
    while (len--) {
        cout << Q->data[Q->front] << endl;
        Q->front = (Q->front + 1) % MAX_SIZE;
    }
}
1
2
3
4
5
6
7
8
9
10

完整代码：

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

#define MAX_SIZE 100
typedef int ElementType;

typedef struct {
    int front;
    int rear;
    ElementType data[MAX_SIZE];
} SqQueue, *SqQueuePtr;

int queue_length(SqQueuePtr Q) {
    return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}

void initialize_queue(SqQueuePtr &Q) {
    Q = (SqQueuePtr)malloc(sizeof(SqQueue));
    if (Q != NULL) {
        Q->front = 0;
        Q->rear = 0;
    }
}

bool enqueue(SqQueuePtr &Q, int num) {
    if ((Q->rear + 1) % MAX_SIZE == Q->front) {
        return false;
    }
    Q->data[Q->rear] = num;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return true;
}

bool dequeue(SqQueuePtr &Q, int &e) {
    if (Q->rear == Q->front) {
        printf("队列为空\n");
        return false;
    }
    e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return true;
}

void print_all(SqQueuePtr &Q) {
    if (Q->front == Q->rear) {
        printf("空的\n");
    }
    int len = queue_length(Q);
    while (len--) {
        cout << Q->data[Q->front] << endl;
        Q->front = (Q->front + 1) % MAX_SIZE;
    }
}

int main() {
    SqQueuePtr Q;
    initialize_queue(Q);
    int count, num;

    cout << "输入您要入队的个数：" << endl;
    scanf("%d", &count);
    while (count--) {
        cout << "输入您要入队的元素：" << endl;
        scanf("%d", &num);
        if (enqueue(Q, num)) {
            printf("入队成功：%d\n", num);
        } else {
            printf("失败\n");
        }
    }
    printf("长度:%d\n", queue_length(Q));

    int dequeue_count, e;
    cout << "您要弹出的位数：" << endl;
    scanf("%d", &dequeue_count);
    if (dequeue_count > queue_length(Q)) {
        cout << "贪得无厌";
    } else {
        while (dequeue_count--) {
            if (dequeue(Q, e)) {
                printf("删除成功：%d\n", e);
            } else {
                printf("失败\n");
            }
        }
    }

    printf("长度:%d\n", queue_length(Q));

    int insert_count, num2;
    printf("输入插入长度：");
    scanf("%d", &insert_count);

    while (insert_count--) {
        cout << "输入您要入队的元素：" << endl;
        scanf("%d", &num2);
        if (enqueue(Q, num2)) {
            printf("入队成功：%d\n", num2);
        } else {
            printf("失败\n");
        }
    }
    printf("长度:%d\n", queue_length(Q));

    print_all(Q);

    return 0;
}

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

通过以上代码，我们了解了三种队列的实现方式：顺序队列、链队列和循环队列。这三种实现方式分别适用于不同的场景，选择合适的队列类型有助于提高算法的效率。在实际应用中，根据具体情况选择最合适的队列实现方式是非常重要的。

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

队列的实现，数组队列，链表队列，循环队列 简单详细（附源码）_以数组形式构建一个(顺序)队列,实现进队、出队、判定队是否为空等操作

CSDN博客：队列的三种实现方式

1. 顺序队列

1.1 结构定义

1.2 初始化队列

1.3 判断队列是否为空

1.4 判断队列是否为满

1.5 清空队列

1.6 入队

1.7 出队

1.8 计算队列中元素个数

1.9 打印队列中元素

完整代码：

2. 链队列

2.1 结构定义

2.2 初始化链队列

2.3 入队

2.4 出队

2.5 获取队头元素

2.6 打印队列中元素

完整代码：

3. 循环队列

3.1 结构定义

3.2 初始化循环队列

3.3 入队

3.4 出队

3.5 获取循环队列长度

3.6 打印循环队列中元素

完整代码：

队列的实现，数组队列，链表队列，循环队列简单详细（附源码）_以数组形式构建一个(顺序)队列,实现进队、出队、判定队是否为空等操作