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

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

定义

队列的定义

队列（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

_6chainNode.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日22点06分
Last Version:			V1.0
Descriptions:			链表的结点
*/
#pragma once
#ifndef _CHAINNODE_H_
#define _CHAINNODE_H_
template <class T>
struct chainNode
{//数据成员T element;chainNode<T>* next;//方法chainNode() {}chainNode(const T& element){this->element = element;this->next = nullptr;}chainNode(const T& element, chainNode<T>* next){this->element = element;this->next = next;}
};
#endif

_21linkedQueue.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			链表存储的队列的头文件
*/
#pragma once
#ifndef _LINKEDQUEUE_H_
#define _LINKEDQUEUE_H_
#include<sstream>
#include<iostream>
#include "_1myExceptions.h"
#include "_6chainNode.h"
#include "_17queue.h"
/*测试函数*/
void linkedQueueTest();using namespace std;
template<class T>
class linkedQueue : public queue<T>
{
public:/*成员函数*/linkedQueue(int initialCapacity = 10){theFront = theBack = nullptr;queueSize = 0;}~linkedQueue();bool empty() const { return queueSize == 0; }//返回队列的元素个数int size() const { return queueSize; }/*清空队列中的元素*/void clear();/*返回第一个元素*/T& front() { return theFront->element; }/*返回最后一个元素*/T& back() { return theBack->element; }/*删除队首元素*/void pop(){chainNode<T>* next = theFront->next;delete theFront;theFront = next;queueSize--;}/*向队尾插入元素theElement*/void push(const T& theElement){if (queueSize == 0)theFront = theBack = new chainNode<T>(theElement, nullptr);else{theBack->next = new chainNode<T>(theElement, nullptr);theBack = theBack->next;}       queueSize++;}//void meld(arrayQueue<T>& a, arrayQueue<T>& b);//合并队列a,b到当前队列//void split(arrayQueue<T>& a, arrayQueue<T>& b);//将当前队列分成两个队列a,b/*重载操作符*//*重载[]操作符*/T operator[](int i){chainNode<T>* currentNode = theFront;for (int j = 0; j < i; j++)currentNode = currentNode->next;return currentNode->element;}/*友元函数*/friend istream& operator>> <T>(istream& in, linkedQueue<T>& m);//输出但是不pop()元素friend ostream& operator<< <T>(ostream& out, linkedQueue<T>& m);
private:chainNode<T>* theFront;       // 指向第一个元素的指针chainNode<T>* theBack;        // 指向最后一个元素的指针int queueSize;    // 队列的容量，实质上比队列容量(不包含queueFront指向的那一个位置)大1
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, linkedQueue<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;
}
//输出但是不pop()元素
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, linkedQueue<T>& m)
{chainNode<T>* currentNode = m.theFront;while(currentNode != nullptr){cout << currentNode->element << " ";currentNode = currentNode->next;}out << endl;return out;
}
/*成员函数*/
/*析构函数*/
template<class T>
linkedQueue<T>::~linkedQueue()
{chainNode<T>* nextNode = theFront;while (nextNode != nullptr){nextNode = nextNode->next;delete theFront;theFront = nextNode;}
}
/*清空队列中的元素*/
template<class T>
void linkedQueue<T>::clear()
{chainNode<T>* nextNode = theFront;while (nextNode != nullptr){nextNode = nextNode->next;delete theFront;theFront = nextNode;}queueSize = 0;theFront = theBack = nullptr;
}#endif

_21linkedQueue.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_21linkedQueue.h头文件中的所有函数
*/
#include <iostream>
#include <time.h>
#include "_21linkedQueue.h"
using namespace std;
/*测试函数*/
void linkedQueueTest()
{cout << endl << "*********************************linkedQueueTest()函数开始*************************************" << endl;linkedQueue<int> a;//测试输入和输出cout << endl << "测试友元函数*******************************************" << endl;cout << "输入输出************************" << endl;cin >> a;cout << "linkedQueue 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 << "push()**************************" << endl;cout << "before push linkedQueue a is:" << a;a.push(99);a.push(22);cout << "after push linkedQueue 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 linkedQueue a is:" << a;a.pop();a.pop();cout << "after pop linkedQueue a is:" << a;cout << "clear()*************************" << endl;a.clear();cout << "after clear linkedQueue a is:" << a;cout << endl << "测试成员函数性能***************************************" << endl;cout << "push()**************************" << endl;linkedQueue<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 << "*********************************linkedQueueTest()函数结束*************************************" << endl;
}

main.cpp

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

_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 <string>
#include<iostream>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