【C++】队列_c++ 单队列定义,只能保存50个值

一.基本介绍

队列，一种先进先出（FIFO，First-In-First-Out）的线性表，通常用链表或者数组来实现。队列只允许在后端（rear）插入，在前端（front）取出删除。

与堆栈唯一的区别就是只允许新数据在尾部添加。

---

我们用数组来实现队列，需要以下4个基本变量：

---

基本思路：

front和rear开始时都指向数组头，当插入数据时rear指针加1，当删除数据时front指针加1，当front==rear时，说明队列已经为空。如果rear=maxSize-1表示队列已满。

但是我们会发现如果这样操作的话，这个队列就是一次性的，这个队列最终能存放的数只有maxSize个，当rear=maSize-1时，这个队列已经废了。

所以我们可以考虑将其改造成循环队列，也就是让数组首尾相接，这样可以循环往复的存取元素。

此时，front的含义不变，而rear指向队列中最后一个元素的下一个位置。

队列满的标志就变为：(rear+1)%maxSize==front

队列中元素存放的个数为：(rear+maxSize-front)%maxSize

---

实现如下函数：

二.代码实现

#include<iostream>
#include<cstdlib>
using namespace std;
/*
    使用循环数组列实现队列
*/

class Queue
{
    private:
        int front;
        int rear;
        int maxSize;
        int *arr;
    public:
        //构造函数
        Queue(int maxSize)
        {
            front=0;
            rear=0;
            maxSize = maxSize+1;
            arr = new int[maxSize];
        }
        
        //取出并删除队首元素
        int pop()
        {
            if(isEmpty())
            {
                cout<<"队列为空"<<endl;
                return -1;
            }
            int value = arr[front];
            //因为是循环队列，所以front的位置也需要取模计算
            front = (front+1)%maxSize;
            return value;
        }

        //添加元素到队尾
        void push(int num)
        {
            if(isFull())
            {
                cout<<"队列已满"<<endl;
                return ;
            }
            arr[rear]=num;
            rear = (rear+1)%maxSize;
        }

        //查看队首元素不删除
        int head()
        {
            if(isEmpty())
            {
                cout<<"队列为空"<<endl;
                return -1;
            }
            return arr[front];
        }
        
        //查看队尾元素
        int tail()
        {
            if(isEmpty())
            {
                cout<<"队列为空"<<endl;
                return -1;
            }
            //当rear=1时，减一就变成了-1
            return rear-1<0?arr[maxSize-1]:arr[rear-1];
        }

        //打印队列元素
        void print()
        {
            if(isEmpty())
            {
                cout<<"队列为空"<<endl;
                return ;
            }
            for(int i=front;i<front+length();i++)
            {
                int index = i%maxSize;
                cout<<"arr["<<index<<"] = "<<arr[index]<<endl;
            }
        }

        //判断队列是否为空
        bool isEmpty()
        {
            return rear==front;
        }

        //判断队列是否已满
        bool isFull()
        {
            return (rear+1)%maxSize==front;
        }

        //计算队列中元素个数
        int length()
        {
            return (rear+maxSize-front)%maxSize;
        }

};

int main()
{
    Queue q=Queue(10);
    q.push(1);
    q.push(3);
    q.push(5);
    q.pop();
    q.push(7);
    q.push(11);
    cout<<"length = "<<q.length()<<endl;;
    cout<<"head = "<<q.head()<<endl;
    cout<<"tail = "<<q.tail()<<endl;
    q.print();

    system("pause");
    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
112
113
114
115
116
117
118
119
120
121
122
123
124
125

三.结果展示