队列：环形数组队列一个基本的环形数组队列的实现

150 阅读 0 评论 99 点赞

我是靠谱客的博主飘逸星星，这篇文章主要介绍队列：环形数组队列一个基本的环形数组队列的实现，现在分享给大家，希望可以做个参考。

一个基本的环形数组队列的实现

可以将此文件放入Stack.h文件中，方便以后需要时使用。

复制代码

//环形数组队列
#include<iostream>
using namespace std;
template<class T>
class Queue
{
public:
    Queue(int Size);
    ~Queue();
    bool queue_empty();
    bool queue_full();
    bool enqueue(T element);
    bool dequeue(T &element);//传入引用的目的是为了将出队的元素取出来
    void traverse();
private:
    T* data;
    int head;//head指向队列头，指向队列第一个元素
    int tail;//tail指向队列尾，指向队列最后一个元素的下一个位置
    int length;//队列长度
    int Size;//队列的内存空间
};

//构造函数，初始化队列
template<class T>
Queue<T>::Queue(int Size)
{
    this->Size=Size;
    head=0;
    tail=0;
    length=0;
    data=new T[Size];
}

//析构函数,释放构造函数申请的内存空间，销毁队列
template<class T>
Queue<T>::~Queue()
{
    delete []data;
}

//判空
template<class T>
bool Queue<T>::queue_empty()
{
    return length==0?true:false;
}

//判满
template<class T>
bool Queue<T>::queue_full()
{
    return length==Size?true:false;
}

//入队
template<class T>
bool Queue<T>::enqueue(T element)
{
    if(queue_full()) return false;
    data[tail]=element;
    tail++;
    tail%=Size;
    length++;
    return true;
}

//出队
template<class T>
bool Queue<T>::dequeue(T &element)
{
    if(queue_empty()) return false;
    head%=Size;
    length--;
    element=data[head];
    head++;
    return true;
}

//遍历
template<class T>
void Queue<T>::traverse()
{
    for(int i=head;i<head+length;i++)
        cout<<data[i%Size]<<" ";
    cout<<endl;
}

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
//环形数组队列
#include<iostream>
using namespace std;
template<class T>
class Queue
{
public:
    Queue(int Size);
    ~Queue();
    bool queue_empty();
    bool queue_full();
    bool enqueue(T element);
    bool dequeue(T &element);//传入引用的目的是为了将出队的元素取出来
    void traverse();
private:
    T* data;
    int head;//head指向队列头，指向队列第一个元素
    int tail;//tail指向队列尾，指向队列最后一个元素的下一个位置
    int length;//队列长度
    int Size;//队列的内存空间
};

//构造函数，初始化队列
template<class T>
Queue<T>::Queue(int Size)
{
    this->Size=Size;
    head=0;
    tail=0;
    length=0;
    data=new T[Size];
}

//析构函数,释放构造函数申请的内存空间，销毁队列
template<class T>
Queue<T>::~Queue()
{
    delete []data;
}

//判空
template<class T>
bool Queue<T>::queue_empty()
{
    return length==0?true:false;
}

//判满
template<class T>
bool Queue<T>::queue_full()
{
    return length==Size?true:false;
}

//入队
template<class T>
bool Queue<T>::enqueue(T element)
{
    if(queue_full()) return false;
    data[tail]=element;
    tail++;
    tail%=Size;
    length++;
    return true;
}

//出队
template<class T>
bool Queue<T>::dequeue(T &element)
{
    if(queue_empty()) return false;
    head%=Size;
    length--;
    element=data[head];
    head++;
    return true;
}

//遍历
template<class T>
void Queue<T>::traverse()
{
    for(int i=head;i<head+length;i++)
        cout<<data[i%Size]<<" ";
    cout<<endl;
}

这是一个指定存储空间的队列模板类，有队列最基本的操作，判空，判满，出队（出队可以取出队的元素，通过传引用的方式），入队，遍历。环形队列，意味着队列的存储空间首尾相连（是指定大小Size的空间可以实现逻辑上的首尾相连）。
出队入队返回bool是为了判断出入队是否成功，函数内部已经实现对数据的更改，不需要其他返回值。这个判断是为了可能在以后的操作中需要用到。

接下来就可以利用这个队列进行基本的操作。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include"Stack.h"//上面编写的文件
using namespace std;
//如果利用模板类操作的队列元素是string需要#include<string>
int main()
{
    int Size;
    cin>>Size;
    Queue<> myqueue(Size);//在<>内填入队列元素的数据类型
    //进行操作
    return 0;

}