使用Vector模拟实现STL中的stack

stack 介绍

栈是一种容器适配器，特别为后入先出而设计的一种（LIFO ），那种数据被插入，然后再容器末端取出

栈实现了容器适配器，这是用了一个封装了的类作为他的特定容器，提供了一组成员函数去访问他的元素，元素从特定的容器，也就是堆栈的头取出袁术。

这个基础的容器可能是任何标准的容器类，和一些其他特殊设计的模板类，唯一的要求就是要支持一下的操作
实现C++ STL，栈有两个参数。

template < class T, class Container = deque > class stack;

参数示意：

T: 元素类型
Container: 被用于存储和访问元素的的类型

成员函数:

（1）stack::stack

stack ( const Container& ctnr = Container() );
用于构造一个栈适配器对象
（2）stack::empty

bool empty ( ) const;
判断是否为空
（3）stack::pop

void pop ( );
在栈的顶部移除元素
（4）stack::push

void push ( const T& x );
在栈顶添加元素
（5）stack::size

size_type size ( ) const;
计算栈对象元素个数
（6）stack::top

value_type& top ( );
const value_type& top ( ) const;
返回栈顶元素

#pragma once
#include<stdio.h>
#include<deque>
#include<iostream>
using namespace std;
template<class T,class Con = deque<T> >
class Stack
{
public:
typedef size_t SizeType;
typedef T ValueType;
public:
Stack()
//用于构造一个栈适配器对象
{}
bool Empty()const
//判断是否为空
{
return _con.empty();
}
SizeType Size()const
//计算栈对象元素个数
{
return _con.size();
}
void Pop()
//在栈的顶部移除元素
{
_con.pop_back();
}
void Push(const ValueType data)
//在栈顶添加元素
{
_con.push_back(data);
}
ValueType& Top()
//返回栈顶元素
{
return _con.back();
}
const ValueType& Top()const
{
return _con.back();
}
private:
Con _con;
};

用vector实现：

#include <iostream>
using namespace std;
#include <assert.h>
template<typename T>
class Vector
{
public:
typedef T valueType;
typedef valueType* Iteator;
typedef const valueType* const_Iterator;
typedef valueType& Reference;
typedef const valueType& const_Reference;
typedef size_t size_type;
public:
Vector()
//构造函数
:_start(0)
,_finish(0)
,_end_of_storage(0)
{}
Vector(size_type n, const T& value = T())
//构造函数，构造一个里面有n个相同值的顺序表
:_start(new T[n])
{
for(size_type idx=0; idx<n; ++idx)
_start[idx] = value;
_finish = _start+n;
_end_of_storage = _finish;
}
Vector(const Vector<T> &v)
//拷贝构造函数
{
size_type capacity = v._end_of_storage - v._start;
_start = new T[capacity];
size_type size = v._finish - v._start;
for(size_type idx=0; idx<size; ++idx)
{
_start[idx] = v._start[idx];
}
_finish = _start + size; //不能用_finish = v._finish;因为改变指向会引发错误
_end_of_storage = _start + capacity;
}
Vector<T>& operator = (const Vector<T>& v) //赋值运算符重载
{
if(this != &v)
{
size_type capacity = v._end_of_storage - v._start;
size_type size = v._finish - v._start;
if(Capacity() < size)
{
_start = new T[capacity];
for(size_type idx=0; idx<size; ++idx)
{
_start[idx] = v._start[idx];
}
_finish = _start + size; //不能用_finish = v._finish;因为改变指向会引发错误
_end_of_storage = _start + capacity;
}
}
return *this;
}
~Vector()
//析构函数
{
if(NULL != _start)
{
delete[] _start;
_start = NULL;
_finish = NULL;
_end_of_storage = NULL;
}
}
Iteator Begin()
//得到数组头的指针
{
return _start;
}
const_Iterator Begin()const
{
return _start;
}
Iteator End()
//得到数组的最后一个单元+1的指针
{
return _finish;
}
const_Iterator End()const
{
return _finish;
}
size_type Size()const
//当前使用数据的大小
{
return _finish - _start;
}
size_type Capacity()const
//当前vector分配的大小
{
return _end_of_storage - _start;
}
bool Empty()const
//判断vector是否为空
{
return Begin() == End();
}
Reference operator[](size_type index)
//得到编号位置的数据
{
assert(index<Size());
return _start[index];
}
const_Reference operator[](size_type index)const
{
assert(index<Size());
return _start[index];
}
Reference Front()
//得到数组头的引用
{
return *Begin();
}
Reference Back()
//得到数组的最后一个单元的引用
{
return *(End()-1);
}
void PushBack(const T& value)
//在数组的最后添加一个数据
{
CheckCapacity();
*_finish = value;
++_finish;
}
void PopBack()
//去掉数组的最后一个数据 
{
assert(0 != Size());
--_finish;
}
Iteator Insert(Iteator pos, const T& value)
// 在指针指向元素的前面插入一个元素
{
size_type position = pos - Begin();
CheckCapacity();
int count = Size() - position ;
int i = 0;
while(count)
{
_start[Size()-i] = _start[Size()-i-1];
i++;
count--;
}
*pos = value;
_finish++;
return &(*pos);
}
Iteator Erase(Iteator pos)
//删除指针指向的数据项
{
size_type position = pos - Begin();
assert(0 != Size());
assert(position < Size());
size_t count = Size() - position - 1;
int i = 0;
while(count)
{
_start[position+i] = _start[position+i+1];
i++;
count--;
}
_finish--;
return pos;
}
void ReSize(size_type newSize, const T& value = T())
//重新设置该容器的大小
{
if(newSize < Size())
{
_finish -= (Size() - newSize);
}
else
{
size_t count = newSize - Size();
while(count)
{
CheckCapacity();
_start[Size()] = value;
++_finish;
count--;
}
}
}
void Assign(size_t n, const T& data)
//构造一个里面有n个相同值的顺序表
{
_finish = 0;
Iteator temp = new T[n];
for(size_type idx=0; idx<n; ++idx)
_start[idx] = value;
_finish = _start+n;
_end_of_storage = _finish;
}
void Clear()const
//清空当前的vector
{
_finish = _start;
}
private:
void CheckCapacity()
{
if(_finish >= _end_of_storage)
{
int capacity = Capacity()*2 + 3;
Iteator pTemp = new T[capacity];
size_type size = _finish - _start;
memcpy(pTemp, _start, sizeof(T)*size);
if(_start != NULL)
{
delete[] _start;
}
_start = pTemp;
_finish = _start + size;
_end_of_storage = _start + capacity;
}
}
protected:
Iteator _start;
Iteator _finish;
Iteator _end_of_storage;
};
void FunTest1()
{
Vector<int> v1();
Vector<int> v2(10,4);
Vector<int> v3(v2);
Vector<int> v4;
v4 = v2;
cout<<v2.Capacity()<<endl;
cout<<v2.Size()<<endl;
Vector<int>::Iteator it = v2.Begin();
while(it != v2.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
cout<<v4.Capacity()<<endl;
cout<<v4.Size()<<endl;
it = v4.Begin();
while(it != v4.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
}
void FunTest2()
{
Vector<int> v1(3, 5);
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
v1.PushBack(5);
v1.PushBack(6);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
v1.PopBack();
v1.PopBack();
v1.PopBack();
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
Vector<int>::Iteator it = v1.Begin();
while(it != v1.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
}
void FunTest3()
{
Vector<int> v1(3, 5);
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
v1.PushBack(5);
v1.PushBack(6);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
Vector<int>::Iteator it = v1.Begin();
while(it != v1.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
v1.Erase(v1.Begin()+6);
v1.Insert(v1.Begin(), 10);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
it = v1.Begin();
while(it != v1.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
v1.Erase(v1.Begin()+2);
v1.Insert(v1.Begin(), 10);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
it = v1.Begin();
while(it != v1.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
v1.Insert(v1.Begin(), 10);
v1.Erase(v1.Begin());
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
it = v1.Begin();
while(it != v1.End())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
}
void FunTest4()
{
Vector<int> v1(3, 5);
v1.PushBack(1);
v1.PushBack(2);
v1.PushBack(3);
v1.PushBack(4);
v1.PushBack(5);
v1.PushBack(6);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
v1.ReSize(20,100);
cout<<v1.Size()<<endl;
cout<<v1.Capacity()<<endl;
}
int main()
{
FunTest1();
FunTest2();
FunTest3();
FunTest4();
system("pause");
return 0;
}

#pragma once
#include<stdio.h>
#include<deque>
#include<iostream>
using namespace std;
//Stack栈的模板类的实现
template<class T,class Con = Vector<T> >
class Stack
{
public:
typedef size_t SizeType;
typedef T ValueType;
public:
Stack()
{}
//判空
bool Empty()
{
return (_con.Size()==0);
}
void Push(const ValueType data)
{
_con.PushBack(data);
}
void Pop()
{
_con.PopBack();
}
SizeType Size()const
{
return _con.Size();
}
ValueType& Top()
{
return _con.Back();
}
const ValueType& Top()const
{
return _con.Back();
}
private:
Con _con;
};

最后

以上就是听话期待为你收集整理的使用Vector模拟实现STL中的stack的全部内容，希望文章能够帮你解决使用Vector模拟实现STL中的stack所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。