• 《数据结构、算法与应用C++语言描述》使用C++语言实现数组队列

    《数据结构、算法与应用C++语言描述》使用C++语言实现数组队列

    完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_15arrayQueue/

    定义

    队列的定义

    队列（queue）是一个线性表，其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾（back或rear），删除元素的那一端称为队首（front）。

    队列的抽象数据类型

    在这里插入图片描述

    数组队列实现代码

    _17queue.h

    抽象类栈。

    /*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			队列的抽象类
*/
#pragma once
#ifndef _QUEUE_H_
#define _QUEUE_H_
template<class T>
class queue
{
public:
	virtual ~queue() {}
	virtual bool empty() const = 0;//返回true,当且仅当队列为空
	virtual int size() const = 0;//返回队列中元素个数
	virtual T& front() = 0;//返回头元素的引用
	virtual T& back() = 0;//返回尾元素的引用
	virtual void pop() = 0;//删除首元素
	virtual void push(const T& theElement) = 0;//把元素theELment加入队尾
};
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    _18arrayQueue.h

    /*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组存储的队列的头文件
*/
#pragma once
#ifndef _ARRAYQUEUE_H_
#define _ARRAYQUEUE_H_
#include
#include
#include "_1myExceptions.h"
#include "_17queue.h"
#include 
/*测试函数*/
void arrayQueueTest();

using namespace std;
template<class T>
class arrayQueue : public queue<T>
{
public:
    /*成员函数*/
    arrayQueue(int initialCapacity = 10);
    ~arrayQueue() { delete[] queue; }
    bool empty() const { return theFront == theBack; }
    int size() const //返回队列的元素个数
    {
        return (queueLength - theFront + theBack) % queueLength;
    }
    void clear() { theFront = theBack = 0; }/*清空队列中的元素*/
    int capacity() const { return queueLength-1; }
    //返回第一个元素
    T& front()
    {
        if (theFront == theBack)
            throw queueEmpty();
        return queue[(theFront + 1) % queueLength];
    }
    //返回最后一个元素
    T& back()
    {
        if (theFront == theBack)
            throw queueEmpty();
        return queue[theBack];
    }
    //删除队首元素
    void pop()
    {
        if (theFront == theBack)
            throw queueEmpty();
        theFront = (theFront + 1) % queueLength;
        queue[theFront].~T();
    }
    //向队尾插入元素theElement
    void push(const T& theElement);
    /*调整队列容量大小*/
    void resizeQueue(int newLength);
    void meld(arrayQueue<T>& a, arrayQueue<T>& b);//合并队列a,b到当前队列
    void split(arrayQueue<T>& a, arrayQueue<T>& b);//将当前队列分成两个队列a,b

    /*重载操作符*/
    /*重载[]操作符*/
    T operator[](int i)
    { return queue[(theFront + i + 1) % queueLength]; }

    /*友元函数*/
    friend istream& operator>> <T>(istream& in, arrayQueue<T>& m);
    //输出但是不pop()元素
    friend ostream& operator<< <T>(ostream& out, arrayQueue<T>& m);
private:
    int theFront;       // 第一个元素的前一个位置
    int theBack;        // 最后一个元素的位置
    int queueLength;    // 队列的容量，实质上比队列容量(不包含queueFront指向的那一个位置)大1
    T* queue;           // 指向队列首地址的指针
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayQueue<T>& m)
{
    int numberOfElement = 0;
    cout << "Please enter the number of element:";
    while (!(in >> numberOfElement))
    {
        in.clear();//清空标志位
        while (in.get() != '\n')//删除无效的输入
            continue;
        cout << "Please enter the number of element:";
    }
    T cinElement;
    for (int i = 0; i < numberOfElement; i++)
    {
        cout << "Please enter the element " << i + 1 << ":";
        while (!(in >> cinElement))
        {
            in.clear();//清空标志位
            while (in.get() != '\n')//删除无效的输入
                continue;
            cout << "Please enter the element " << i + 1 << ":";
        }
        m.push(cinElement);
    }
    return in;
}
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, arrayQueue<T>& m)
{
    int size = m.size();
    for (int i = 0; i < size; i++)
        out << m.queue[(m.theFront + i + 1) % m.queueLength] << "  ";
    out << endl;
    return out;
}
/*成员函数*/
/*构造函数*/
template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity)
{
    if (initialCapacity < 1)
    {
        ostringstream s("");
        s << "Initial capacity = " << initialCapacity << "Must be > 0";
        throw illegalParameterValue(s.str());
    }
    queue = new T[initialCapacity+1];
    queueLength = initialCapacity+1;
    theFront = theBack = 0;
}

/*向队尾插入元素theElement*/
template<class T>
void arrayQueue<T>::push(const T& theElement)
{
    //首先检查队列是否已满，如已满，则将队列容量加倍
    if ((theBack + 1) % queueLength == theFront)
        resizeQueue(2 * (queueLength-1));    
    theBack = (theBack + 1) % queueLength;
    queue[theBack] = theElement;
}
/*调整队列容量大小*/
template<class T>
void arrayQueue<T>::resizeQueue(int newLength)
{
    T* temp = new T[newLength + 1];
    int size = min((*this).size(), newLength);
    for (int i = 0; i < size; i++)
        temp[i] = queue[(theFront + i + 1) % queueLength]; 
    queueLength = newLength+1;
    theFront = newLength;
    theBack = size - 1;
    delete[] queue;
    queue = temp;
}

/*
创建一个新的队列，该表包含了a和b中的所有元素，其中a和b的元素轮流出现，表中的首
元素为a中的第一个元素。在轮流排列元素时，如果某个队列的元素用完了，则把另一个队列的其
余元素依次添加在新队列的后部。代码的复杂性应与两个输入队列的长度呈线性比例关系。
归并后的线性队列是调用对象*this
*/
template <class T>
void arrayQueue<T>::meld(arrayQueue<T>& a, arrayQueue<T>& b)
{
    (*this).clear();
    int i = 0;
    while (i < a.size() && i < b.size())
    {
        push(a[i]);
        push(b[i]);
        i++;
    }
    while (i < a.size())
    {
        push(a[i]);
        i++;
    }
    while (i < b.size())
    {
        push(b[i]);
        i++;
    }
}

/*生成两个线性队列a和b，a包含*this中索引为奇数的元素，b包含其余的元素*/
template<class T>
void arrayQueue<T>::split(arrayQueue<T>& a, arrayQueue<T>& b)
{
    a.clear();
    b.clear();
    int size = (*this).size();
    for (int i = 0; i < size; i++)
    {
        if (i % 2 == 0)
            a.push(queue[(theFront + i + 1) % queueLength]);
        else
            b.push(queue[(theFront + i + 1) % queueLength]);
    }
}
#endif

    • 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
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201

    _18arrayQueue.cpp

    /*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_18arrayQueue.h头文件中的所有函数
*/
#include 
#include 
#include "_18arrayQueue.h"
using namespace std;

/*测试函数*/
void arrayQueueTest()
{
	cout << endl << "*********************************arrayQueueTest()函数开始*************************************" << endl;
	arrayQueue<int> a;

	//测试输入和输出
	cout << endl << "测试友元函数*******************************************" << endl;
	cout << "输入输出************************" << endl;
	cin >> a;
	cout << "arrayQueue a is:" << a;
	cout << endl << "测试成员函数*******************************************" << endl;
	cout << "empty()*************************" << endl;
	cout << "a.empty() = " << a.empty() << endl;
	cout << "size()**************************" << endl;
	cout << "a.size() = " << a.size() << endl;
	cout << "capacity()**********************" << endl;
	cout << "a.capacity() = " << a.capacity() << endl;
	cout << "push()**************************" << endl;
	cout << "arrayQueue a is:" << a;
	a.push(99);
	a.push(22);
	cout << "arrayQueue a is:" << a;
	cout << "front()*************************" << endl;
	cout << "a.front() = " << a.front() << endl;
	cout << "back()**************************" << endl;
	cout << "a.back() = " << a.back() << endl;
	cout << "pop()***************************" << endl;
	cout << "before pop arrayQueue a is:" << a;
	a.pop();
	a.pop();
	cout << "after pop arrayQueue a is:" << a;
	cout << "resizeQueue()*******************" << endl;
	cout << "before resizeQueue a.capacity() = " << a.capacity()<<endl;
	a.resizeQueue(4);
	cout << "after resizeQueue a.capacity() = " << a.capacity() << endl;
	cout << "arrayQueue a is:" << a;
	cout << "a.front() = " << a.front() << endl;
	cout << "a.back() = " << a.back() << endl;
	a.push(88);
	cout << "after resizeQueue a.capacity() = " << a.capacity() << endl;
	cout << "meld()**************************" << endl;
	arrayQueue<int> b;
	cin >> b;
	cout << "arrayQueue a is:" << a;
	cout << "arrayQueue b is:" << b;
	arrayQueue<int> c;
	c.meld(a, b);
	cout << "arrayQueue c is:" << c;
	cout << "split()*************************" << endl;
	arrayQueue<int> d;
	arrayQueue<int> e;
	c.split(d, e);
	cout << "arrayQueue c is:" << c;
	cout << "arrayQueue d is:" << d;	
	cout << "arrayQueue e is:" << e;

	cout << endl << "测试成员函数性能***************************************" << endl;
	cout << "push()**************************" << endl;
	arrayQueue<int> f;
	double clocksPerMillis = double(CLOCKS_PER_SEC) / 1000;
	clock_t startTime = clock();
	for (int i = 0; i < 100000000; i++)
		f.push(i);
	double pushTime = (clock() - startTime) / clocksPerMillis;
	cout << 10000 << " push took " << pushTime << " ms" << endl;
	cout << "*********************************arrayQueueTest()函数结束*************************************" << 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

    main.cpp

    /*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数，控制运行所有的测试函数
*/
#include 
#include "_18arrayQueue.h"


int main()
{
	arrayQueueTest();
	return 0;
}

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

    _1myExceptions.h

    /*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include 
#include

using namespace std;

// illegal parameter value
class illegalParameterValue 
{
   public:
      illegalParameterValue(string theMessage = "Illegal parameter value")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal input data
class illegalInputData 
{
   public:
      illegalInputData(string theMessage = "Illegal data input")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal index
class illegalIndex 
{
   public:
      illegalIndex(string theMessage = "Illegal index")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds 
{
   public:
      matrixIndexOutOfBounds
            (string theMessage = "Matrix index out of bounds")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix size mismatch
class matrixSizeMismatch 
{
   public:
      matrixSizeMismatch(string theMessage = 
                   "The size of the two matrics doesn't match")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// stack is empty
class stackEmpty
{
   public:
      stackEmpty(string theMessage = 
                   "Invalid operation on empty stack")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// queue is empty
class queueEmpty
{
   public:
      queueEmpty(string theMessage = 
                   "Invalid operation on empty queue")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// hash table is full
class hashTableFull
{
   public:
      hashTableFull(string theMessage = 
                   "The hash table is full")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
   public:
      undefinedEdgeWeight(string theMessage = 
                   "No edge weights defined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// method undefined
class undefinedMethod
{
   public:
      undefinedMethod(string theMessage = 
                   "This method is undefined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};
#endif

    • 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
  • 相关阅读:
    基于SqlSugar的数据库访问处理的封装，支持多数据库并使之适应于实际业务开发中
    生产管理系统--制造订单
    安全生产管理系统——特殊作业管控
    Taurus.MVC 微服务框架 入门开发教程：项目部署：7、微服务节点的监控与告警。
    rabbitmq动态创建监听
    springboot 集成 PageHelper 分页失效
    三只松鼠、盐津铺子：战略相似，命运迥异
    租房行业调研-租房市场现状研究分析与发展前景预测
    Python bool 详解 （扒源码）
    vue课程75 axios是只专注于网络请求的库
  • 原文地址：https://blog.csdn.net/weixin_44410704/article/details/133915760