目录
? ? ? ? (1)stack是一种容器适配器,专门用在具有后进先出操作的环境中,stack只能从容器的一端进行插入与删除操作。
? ? ? ? (2)stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为作为其底层容器,并提供一组特定的成员函数来访问其元素。
? ? ? ? (3)stack的底层容器可以使任何标准的容器类模板。这些容器类需要支持以下操作:empty()、back()、push_back()、pop_back()等。
? ? ? ? (4)标准容器vector、deque、list均符合上面需求,默认情况下stack的底层容器是deque。
//stack的使用:最小栈
class MinStack
{
public:
void push(int x)
{
//只要有元素压栈,首先将元素保存到_elem中
_elem.push(x);
//如果x小于等于_min中栈顶的元素,则也要将x压栈到_min中
if (_min.empty() || _min.top() <= x)
{
_min.push(x);
}
}
void pop()
{
//如果_min栈顶元素等于_elem栈顶元素,则删除_elem栈顶元素的同时也要删除_min栈顶元素
if (_elem.top() == _min.top())
{
_min.pop();
}
_elem.pop();
}
int top()
{
return _elem.top();
}
int getMin()
{
return _min.top();
}
private:
//保存栈中的元素
std::stack<int> _elem;
//保存栈的最小值
std::stack<int> _min;
};
? ? ? ? 以vector为底层容器模拟实现stack:
namespace lbj
{
//以vector为底层容器模拟实现stack
template <class T>
class stack
{
public:
stack() {}
void push(const T& x)
{
_s.push_back(x);
}
void pop()
{
_s.pop_back();
}
T& top()
{
return _s.back();
}
const T& top()const
{
return _s.back();
}
size_t size()const
{
return _s.size();
}
bool empty()const
{
return _s.empty();
}
private:
std::vector<T> _s;
};
}
? ? ? ? (1)queue是一种专门用于上下文先进先出操作的容器适配器,即支持push_back()和pop_back();
? ? ? ? (2)queue的底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器,但是底层容器都需要支持以下操作:empty()、size()、front()、back()、push_back()、pop_front()等;
? ? ? ? (3)标准容器类deque和list满足了上述要求。默认情况下使用标准容器deque作为queue的底层容器
? ? ? ? 以list为底层容器模拟实现queue:
namespace lbj
{
//以list为底层容器模拟实现queue:
template <class T>
class queue
{
public:
queue(){}
void push(const T& x)
{
_q.push_back(x);
}
void pop()
{
_q.pop_front();
}
T& front()
{
return _q.front();
}
const T& front()const
{
return _q.front();
}
T& back()
{
return _q.back();
}
const T& back()const
{
return _q.back();
}
size_t size()
{
return _q.size();
}
bool empty()
{
return _q.empty();
}
private:
std::list<T> _q;
};
}
? ? ? ? (1)priority_queue(优先级队列)是一容器适配器,根据严格的弱排序标准,默认情况下它的第一个元素是它所包含元素中最大的;
? ? ? ? (2)优先级队列的上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先级队列中位于开头位置的元素)
? ? ? ? (3)priority_queue的底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。只要容器可以通过随机访问迭代器进行访问,并支持以下操作:empty()、size()、front()、push_back()、pop_back()等;
? ? ? ? (4)标准容器类vector和deque均满足上述要求,没有指定的情况下默认使用vector作为priority_queue的底层容器。
????????priority_queue默认使用vector作为其底层容器,在vector上又使用了堆算法将vector中的元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。