模板模拟实现栈

一时失言乱红尘 2022-09-29 12:55 157阅读 0赞

栈的特点是先进后出，可以用vector实现栈(顺序的存储结构，存储空间是连续的）

通过先实现Vector作为底层来实现栈

#include<iostream> #include<stdio.h> #include<assert.h> using namespace std; template<typename T> class Vector { public: typedef T ValueType; typedef ValueType* Pointer; typedef const ValueType* ConstPointer; typedef ValueType* Iterator; typedef const ValueType* ConstIterator; typedef ValueType& Reference; typedef const ValueType& ConstReference; typedef size_t SizeType; Vector() :_start(0) , _end(0) , _endOfStorage(0) { } Vector(SizeType n, const T& value) { FillAndInit(n, value); } Vector(SizeType n) { FillAndInit(n, T()); } Vector(const Vector<T>& v) { _start = new T[v.Capacity()]; _end = _start + v.Size(); for (int index = 0; index < v.Size(); ++index) { _start[index] = v[index]; } } Vector<T>& operator=(const Vector<T>& v) { if (_start != v._start) { Iterator Temp = new T[v.Capacity()]; for (int index = 0; index < Size(); ++index) { Temp[index] = v[index]; } delete _start[]; _start = Temp; } } ~Vector() { if (_start != NULL) { delete [] _start; } } SizeType Capacity()const { return _endOfStorage-_start; } SizeType Size()const { return _end - _start ; } SizeType MaxSize()const { return SizeType(-1) / sizeof(T); } bool Empty()const { return 0 == Size(); } Reference operator[](size_t index) { assert(index < Size()); return _start[index]; } ConstReference operator[](size_t index)const { return _start[index]; } Reference Front() { return *(Begin()); } ConstReference Front()const { return *(Begin()); } Reference Back() { return *(End()-1); } ConstReference Back()const { return *(End() - 1); } Iterator Begin() { return _start; } ConstIterator Begin()const { return _start; } Iterator End() { return _end; } ConstIterator End()const { return _end; } Iterator Insert(Iterator position, const T& data) { CheckCapacity(); int index = position - Begin(); int end = Size() - 1; while (index <= end) { _start[end + 1] = _start[end]; --end; } _start[index] = data; ++_end; return position; } Iterator Erase(Iterator position) { int index = position - Begin(); int end = Size() - 1; while (index <end) { _start[index] = _start[index+1]; index++; } --_end; return position; } Iterator Erase(Iterator first, Iterator last) { int index = first - Begin(); int num = index; int end = Size() - 1; int cout = 0; Iterator temp = first; for (; temp <last;++temp) { while (index < end) { _start[index] = _start[index + 1]; index++; } index=num; --end; ++cout; } _end -= cout; return first; } void clear(); void Display(); void PushBack(const T& value); void PopBack(); void FillAndInit(SizeType n, const T& value) { _start = new T[n]; for (int index = 0; index < n; ++index) { _start[index] = value; } _endOfStorage += n; _end += n; _endOfStorage += n; } void CheckCapacity(); Iterator _start; Iterator _end; Iterator _endOfStorage; }; template<typename T> void Vector<T>:: Display() { int temp = Size(); if (temp == 0) { cout << "顺序为空"; } else { for (int index = 0; index < temp; ++index) { cout << _start[index] << " "; } } } template<typename T> void Vector<T>::CheckCapacity() { if (_end >=_endOfStorage) { int num = Size(); int count = Capacity() * 2 + 3; Iterator Temp = new T[count];//如果构造函数中Capacity==0不加一个常数会出错 for (int index = 0; index < num; ++index) { Temp[index] = _start[index]; } delete[] _start; _start = Temp; _end = Temp+num; _endOfStorage = _start +count; } } template<typename T> void Vector<T>::PushBack(const T& value) { CheckCapacity(); _start[Size()] = value; ++_end; } template<typename T> void Vector<T>::PopBack() { --_end; } template<typename T> void Vector<T>::clear() { Erase(Begin(), End()); }

上述先通过模板模拟实现Vector来作为stack的底层代码

接着创建一个Stack的类

template<class T, class Con = Vector<T>>
    class Stack
    {
    public:
    	
    	Stack()
    		:_c()
    	{
    
    	}
    	void Push(const T& x)
    	{
    		_c.PushBack(x);
    	}
    	void Pop()
    	{
    		_c.PopBack();
    	}
    	T& Top()
    	{
    		_c.Back();
    	}
    	const T& Top()const
    	{
    		_c.Back();
    	}
    	bool Empty()const
    	{
    		_c.clear();
    	}
    	size_t Size()const
    	{
    		_c.Size();
    	}
    protected:
    	Con _c;
    };
    int main()
    {
    	Vector<int> d;
        d.Display();
    	d.PushBack(1);
    	d.PushBack(2);
    	d.PushBack(3);
    	d.PushBack(4);
    	Stack<int, Vector<int>>l;
    	l.Push(1);
    	l.Push(2);
    	l.Push(3);
    	/*d.PushBack(5);
    	int *temp = d.Begin() + 2;
    	d.Insert(temp, 6);
    	d.PopBack();
    	d.Display();
    	cout << endl;
    	d.Erase(temp,temp+2);
    	d.Display();
    	cout << endl;
    	d.clear();
    	d.Display();
    	cout << d.Back() << endl;
    	cout << d.Front() << endl;
    	cout << d.MaxSize() << endl;
    	cout << d[3] << endl;*/
    	system("pause");
    	return 0;
    }