容器适配器之queue

转载http://blog.csdn.net/thefutureisour/article/details/7751846

容器适配器

容器适配器其实就是一个接口转换装置，使得我们能用特定的方法去操作一些我们本来无法操作的东西。举一个例子，比如你的一个设备支持串口线，而你的电脑支持的是USB接口，这时候我们没必要重新买一个支持USB的设备，只需要一根串口转USB口的小玩意儿，让你的设备能够连接到USB接口上，这就是适配器。

那么C++中的容器适配器是做什么的呢？可以做一个类比，我们已有的容器(如vector、list、deque)就是设备，这个设备支持的操作很多，比如插入、删除、迭代器访问等等。而我们希望这个容器表现出来的是栈的样子：先进后出，入栈出栈等等，此时，我们没有必要重写一个新的数据结构，而只需把原有的容器重新封装一下，改变它的接口，就能把它当做栈来用了。

言归正传，理解了什么是适配器以后，其实问题就很简单了。C++中定义了3种容器适配器，它们让容器提供的接口变成了我们常用的的3种数据结构：栈（先进后出）队列（先进先出）和优先级队列（按照优先级（“<”号）排序，而不是按照到来的顺序排序）。

至于具体是怎么变的，我们可以先了解一个大概：默认情况下，栈和队列都是基于deque实现的，而优先级队列则是基于vector实现的。当然，我们也可以指定自己的实现方式。但是由于数据结构的关系，我们也不能胡乱指定。栈的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作要求，即它们都提供了push_back、pop_back和back操作。 队列queue的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front操作，因此其不能建立在vector容器上；对于优先级队列，由于它要求支持随机访问的功能，所以可以建立在vector或者deque上，不能建立在list上。

参见http://www.cplusplus.com/reference/queue/queue/

template > class queue;

FIFO queue

queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

[队列(queue)是一种容器适配器，具有先进先出(FIFO)的结构，元素从一端插入从另一端提取]

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".

[容器适配器是一个类，这个类使用一个特定的容器类对象作为内在容器，该内在容器提供了一系列的成员函数来读取它的元素]

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

[队列的内在容器可以是一个标准容器类模板或者是其他专门设计的容器类，但无论如何，内在容器都应该至少支持以下几种操作：]

empty

size

front

back

push_back

pop_front

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

[标准容器类deque和list满足这些要求。默认的内在容器是双向队列deque]

/*
//construct queue
queue(const container_type& ctnr = container_type())

ctnr
Container object.
[ctnr是一个容器类对象]
container_type is the type of the underlying container type (defined as an alias of the second class template parameter, Container; see member types).
[ctnr的数据类型container_type是内在容器的数据类型，即第二个模板参数Container]A container adaptor keeps internally a container object as data. This container object is a copy of the ctnr argument passed to the constructor, if any, otherwise it is an empty container.[queue会将一个容器对象作为数据，这个容器对象是传递到构造函数的参数ctnr，如果没有传递参数ctnr则为空容器]
*/

#include <iostream>
#include <deque>
#include <list>
#include <queue>

int main()
{
    std::deque<int> mydeck(3, 100);
    std::list<int> mylist(2, 200);

    std::queue<int> first;                              // empty queue with deque as underlying container
    std::queue<int> second(mydeck);                     // queue initialized to copy of deque with deque as underlying container

    std::queue<int, std::list<int>> third;              // empty queue with list as underlying container
    std::queue<int, std::list<int>> fourth(mylist);     // queue initialized to copy of list with list as underlying container

    std::cout << "size of first: " << first.size() << '\n';
    std::cout << "size of second: " << second.size() << '\n';
    std::cout << "size of third: " << third.size() << '\n';
    std::cout << "size of fourth: " << fourth.size() << '\n';

    system("pause");
    return 0;
}

/*
bool empty() const;
size_type size() const;
void push(const value_type& val);
void pop();
value_type& back();
value_type& front();
*/

#include <iostream>
#include <queue>

int main()
{
    std::queue<int> myque;

    for(int i=0; i<5; i++)
        myque.push(i*10);

    std::cout<<"myque contains: ";
    while(!myque.empty())
    {
        std::cout<<myque.front()<<' ';
        myque.pop();
    }

    std::cout<<'\n';

    system("pause");
    return 0;
}

原文链接: https://www.cnblogs.com/kevinq/p/4556317.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍