//
// stack.cpp
// 笔记
//
// Created by fam on 15/3/15.
//
//
//---------------------------15/03/15----------------------------
//stack
{
/*
stack概述:
stack只采用deque的底部操作，封装了deque,形成stack
这种方式是常见的adapter设计模式,stack往往不被归类为container
而是被归类为 container adapter
*/
template <class T,
class Sequence = deque<T> >
class stack
{
friend bool
operator== __STL_NULL_TMPL_ARGS (const stack&,
const stack&);
friend bool
operator< __STL_NULL_TMPL_ARGS (const stack&,
const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const{
return c.empty();}
size_type size()
const {return c.size();}
reference top() {return c.back();}
const_reference top()
const {return c.back();}
void push(const value_type& x) {c.push_back(x);}
void pop() {c.pop_back();}
};
template<class T,
class Sequence>
bool operator==(const stack<T,Sequence>& x,
const stack<T, Sequence>& y)
{
return x.c == y.c;
}
template<class T,
class Sequence>
bool operator<(const stack<T,Sequence>& x,
const stack<T, Sequence>& y)
{
return x.c<y.c;
}
//stack没有迭代器,所有的元素都必须符合先进后出的条件，所以不提供访问其他元素的迭代器
}
//queue
{
//queue
先进后出 可以用deque作为底层结构
template <class T,
class Sequence = deque<T> >
class queue
{
friend bool
operator== __STL_NULL_TMPL_ARGS (const stack&,
const stack&);
friend bool
operator< __STL_NULL_TMPL_ARGS (const stack&,
const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const{
return c.empty();}
size_type size()
const {return c.size();}
reference front() {return c.front();}
const_reference front()
const {return c.front();}
reference back(){return c.back();}
const_reference back()
const {return c.back();}
void push(const value_type& x){c.push_back(x);}
void pop() {c.pop_front();}
};
template<class T,
class Sequence>
bool operator==(const stack<T,Sequence>& x,
const stack<T, Sequence>& y)
{
return x.c == y.c;
}
template<class T,
class Sequence>
bool operator<(const stack<T,Sequence>& x,
const stack<T, Sequence>& y)
{
return x.c<y.c;
}
//queue也没有迭代器
//总结:
这两个数据结构毫无难度
}