C++キューの実装
6301 ワード
List.hファイル
Queue.hファイル
test.cファイル
#include
using namespace std;
template
struct Nodetype{
Nodetype(const T& data = T())
: _pNext(NULL)
, _pPre(NULL)
, _data(data)
{}
Nodetype* _pNext;
Nodetype* _pPre;
T _data;
};
template
class ListIterator{
typedef Nodetype* pNode;
typedef ListIterator Self;
public:
ListIterator()
:_pCur(NULL)
{}
ListIterator(pNode pCur)
: _pCur(pCur)
{}
ListIterator(const Self& s)
: _pCur(s._pCur)
{}
Self& operator++()
{
_pCur = _pCur->_pNext;
return *this;
}
Self operator++(int)
{
Self temp(*this);
_pCur = _pCur->_pNext;
return temp;
}
Self& operator--()
{
_pCur = _pCur->_pPre;
return *this;
}
Self operator--(int)
{
Self temp(*this);
_pCur = _pCur->_pPre;
return *this;
}
bool operator!=(const Self& s)
{
return _pCur != s._pCur;
}
bool operator==(const Self& s)
{
return _pCur == s._pCur;
}
T& operator*()
{
return _pCur->_data;
}
T* operator->()
{
return *(_pCur->_data);
}
private:
pNode _pCur;
};
template
class List{
typedef Nodetype Node;
typedef Node* pNode;
public:
typedef ListIterator Iterator;
public:
List()
{
CreatListHead();
}
List(T* arr, size_t size)
{
//
CreatListHead();
for (size_t i = 0; i < size; ++i)
{
PushBack(arr[i]);
}
}
List(const List& l);
List& operator=(const List& l);
~List();
void PushBack(const T& data);
void PopBack(const T& data);
void PushFront(const T& data);
void PopFront();
void Clear();
void Print();
//pNode Insert(pNode pos, const T& data);
pNode Insert(pNode pos, const T& data){
pNode pNewNode = new Node(data);
pos->_pPre->_pNext = pNewNode;
pNewNode->_pPre = pos->_pPre;
pos->_pPre = pNewNode;
pNewNode->_pNext = pos;
return pNewNode;
}
//pNode Erase(pNode pos);
pNode Erase(pNode pos){
pNode pCur = pos->_pNext;
pos->_pPre->_pNext = pos->_pNext;
pos->_pNext->_pPre = pos->_pPre;
delete pos;
return pCur;
}
size_t size()const;
bool Empty()const
{
if (pHead->_pNext == pHead)
return true;
return false;
}
Iterator Begin()
{
return Iterator(pHead->_pNext);
}
Iterator End()
{
return Iterator(pHead);
}
T& Front()
{
return pHead->_pNext->_data;
}
private:
void CreatListHead()
{
pHead= new Node;
pHead->_pNext = pHead;
pHead->_pPre = pHead;
}
pNode pHead;
};
template
void List::PushBack(const T& data){
pNode pTail = pHead->_pPre;
pNode pNewNode = new Node(data);
pTail->_pNext = pNewNode;
pNewNode->_pPre = pTail;
pNewNode->_pNext = pHead;
pHead->_pPre = pNewNode;
}
template
void List::PopBack(const T& data){
if (Empty())
return;
pNode pProTail = pHead->_pPre->_pPre;
delete pProTail->_pNext;
pProTail->_pNext = pHead;
pHead->_pPre = pProTail;
}
template
void List::PushFront(const T& data){
pNode pNewNode = new Node(data);
pNewNode->_pNext = pHead->_pNext;
pHead->_pNext->_pPre = pNewNode;
pHead->_pNext = pNewNode;
pNewNode->_pPre = pHead;
}
template
void List::PopFront(){
if (Empty())
return;
pNode pTail = pHead->_pNext;
pHead->_pNext = pTail->_pNext;
pTail->_pNext->_pPre = pHead;
delete pTail;
}
template
size_t List::size()const{
pNode pCur = pHead->_pNext;
size_t count = 0;
while (pCur != pHead){
count++;
pCur = pCur->_pNext;
}
return count;
}
template
void List::Clear(){
pNode pDel = pHead->_pNext;
while (!Empty()){
pDel = pHead->_pNext;
pHead->_pNext = pDel->_pNext;
delete pDel;
}
}
template
List::~List(){
Clear();
delete pHead;
pHead = NULL;
}
template
List::List(const List& l){
pHead = new Node();
pHead->_pNext = pHead;
pHead->_pPre = pHead;
pNode pCur = (l.pHead)->_pNext;
while (pCur != l.pHead)
{
this->PushBack(pCur->_data);
pCur = pCur->_pNext;
}
}
template
List& List::operator=(const List& l){
if (this != &l)
{
this->Clear();
pNode pCur = (l.pHead)->_pNext;
while (pCur != l.pHead)
{
this->PushBack(pCur->_data);
pCur = pCur->_pNext;
}
}
return *this;
}
template
void List::Print()
{
pNode pCur = pHead->_pNext;
while (pCur != pHead)
{
cout << pCur->_data << " ";
pCur = pCur->_pNext;
}
cout << endl;
}
Queue.hファイル
#include
using namespace std;
#include"List.h"
template class Container = List>
class Queue{
public:
Queue()
{}
void Push(const T& data)
{
_con.PushBack(data);
}
void Pop()
{
_con.PopFront();
}
void print()
{
_con.Print();
}
bool Empty()const
{
return _con.Empty();
}
size_t size()const
{
return _con.size();
}
T& Front()
{
return _con.Front();
}
private:
Container _con;
};
test.cファイル
#include
using namespace std;
#include"Queue.h"
void test(){
Queue q;
q.Push(1);
q.print();
cout << q.size() << endl;
q.Push(2);
q.print();
cout << q.size() << endl;
q.Push(3);
q.print();
cout << q.size() << endl;
cout << q.Front() << endl;
q.Push(4);
q.print();
cout << q.size() << endl;
q.Push(5);
q.print();
cout << q.size() << endl;
q.Pop();
q.print();
cout << q.size() << endl;
q.Pop();
q.print();
cout << q.size() << endl;
q.Pop();
q.print();
cout << q.size() << endl;
q.Pop();
q.print();
cout << q.size() << endl;
q.Pop();
q.print();
cout << q.size() << endl;
q.Empty();
q.print();
cout << q.size() << endl;
}
int main(){
test();
return 0;
}