C++容器适配器

容器适配器是用基本容器实现的一些新容器,这些容器可以用于描述更高级的数据结构。

容器适配器有三种:stack、queue 和 priority_queue:
  • stack 可以与数据结构中的栈对应,它具有先进后出的特性;
  • queue则可以理解为队列,它具有先进先出的特性;
  • priority_queue 则是带优先级的队列,其元素可以按照某种优先级顺序进行删除。

【例 1】
#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack< int > s;
    int a;
    while(cin >> a)
    {
        s.push(a);
    }
    while( !s.empty() )
    {
        a = s.top();
        s.pop();
        cout<< a <<endl;
    }
    return 0;
}
我们在主函数中定义了一个 stack 容器实体 s,用一个 while 循环向容器 s 中添加数据,再利用一个 while 循环将元素都出栈并打印显示。

对于 stack,push() 为入栈操作即向栈中添加元素,pop() 为出栈操作即删除栈顶元素,top() 函数则为返回栈顶元素但是并不删除它,empty() 函数则用于判断栈是否为空,若为空则返回 true,否则返回 false。

默认情况下,stack 容器衍生自 deque,当我们定义一个 stack 容器实例时:
stack < int > s;
它其实等价于:
stack < int, deque<int> > s;
如果我们想从 vector 衍生出 stack 容器,则需要按照如下方式进行定义:
stack < int, vector<int> > s;

【例 2】
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue < int > q;
    int a;
    while(cin >> a)
    {
        q.push(a);
    }
    while( !q.empty() )
    {
        a = q.front();
        q.pop();
        cout<< a <<endl;
    }   
    return 0;
}
本例是 queue 容器的一个示例程序。对于 queue 容器而言,它同样默认是衍生自 deque 容器的。

与 stack 容器相同,queue 同样有 push()、pop() 函数用于插入和删除元素。不同之处在于,stack 只能操作栈顶,而 queue 是在队列尾部插入元素,在队列头部删除元素。stack 容器用 top() 函数访问栈顶元素,而 queue 没有栈顶这么一说,因而也就没有 top() 函数了,我们想访问队列头的元素可以使用 front() 函数,该函数只是访问并不删除元素。empty() 函数同样可以用于判断队列 queue 是否为空。

【例 3】
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue < int > p;
    int a;
    while(cin >> a)
    {
        p.push(a);
    }
    while( !p.empty() )
    {
        a = p.top();
        p.pop();
        cout << a <<" ";
    }   
    cout << endl;
    return 0;
}
本例是 priority_queue 容器的示例程序,使用 priority_queue 容器我们只需要包含头文件<queue>就可以了。

同样,priority_queue 容器可以用 push() 和 pop() 函数来插入和删除元素,priority_queue 容器提供了 top() 函数用于访问下一个元素,访问但不删除。对于整型的优先队列而言,默认是按照数据从大到小的顺序删除元素的。程序运行情况如下:

1 89 23 43 54 32 65 0 8 18 67↙
89 67 65 54 43 32 23 18 8 1 0