常用接口及说明:
从栈的接口中可以看出,栈实际是一种特殊的vector,因此使用vector完全可以模拟实现stack
#include<vector>
#include<iostream>
using std::cout;
using std::endl;
template <class T>
class stack
{
public:
stack(){}
//参数传引:用减少拷贝开销
//加const:不期望其被修改
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()//按道理这里也是可以加上const的,但是与const T& top() const未构成函数重载(参数列表完全相同)
//导致调用不明确
{
return _c.back();
}
const T& top() const
{
return _c.back();
}
bool empty() const
{
return _c.empty();
}
size_t size() const
{
return _c.size();
}
private:
//未完全展开std
std::vector<T> _c;
};
int main()
{
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
cout << s.size() << endl;
s.pop();
cout << s.size() << endl;
while (!s.empty())
{
cout << s.top() << ' ';
s.pop();
}
return 0;
}
因为queue的接口中存在头删和尾插,因此使用vector来封装效率太低,故可以借助list来模拟实现queue,具体如下:
#include<list>
#include<iostream>
using std::cout;
using std::endl;
template <class T>
class queue
{
public:
queue(){}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& front()
{
return _c.front();
}
const T& front() const
{
return _c.front();
}
T& back()
{
return _c.back();
}
const T& back() const
{
return _c.back();
}
bool empty()
{
return _c.empty();
}
size_t size()
{
return _c.size();
}
private:
std::list<T> _c;
};
int main()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
cout << q.size() << endl;
cout << q.front() << endl;
cout << q.back() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
cout << q.size() << endl;
return 0;
}