STL中的单向队列queue

转载自：http://blog.csdn.net/morewindows/article/details/6950917

stl中的queue指单向队列，使用时，包含头文件<queue>。

关键要会用queue，实际上就是掌握该类的各种操作，如下：

常用函数push(e),pop(),front(),back(),size(),empty()，与栈的常用函数较为相似。

在STL中，单向队列是以别的容器作为底层数据结构，再改变接口使之符合单向队列的特性。下面就给出单向队列的函数列表和VS2008中单向队列的源代码。

VS2008中queue单向队列的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间。

template<class _Ty, class _Container = deque<_Ty> >

class queue

{    // FIFO queue implemented with a container

public:

    typedef _Container container_type;

    typedef typename _Container::value_type value_type;

    typedef typename _Container::size_type size_type;

    typedef typename _Container::reference reference;

    typedef typename _Container::const_reference const_reference;

    queue() : c()

    {    // construct with empty container

    }

    explicit queue(const _Container& _Cont) : c(_Cont)

    {    // construct by copying specified container

    }

    bool empty() const

    {    // test if queue is empty

        return (c.empty());

    }

    size_type size() const

    {    // return length of queue

        return (c.size());

    }

    reference front()

    {    // return first element of mutable queue

        return (c.front());

    }

    const_reference front() const

    {    // return first element of nonmutable queue

        return (c.front());

    }

    reference back()

    {    // return last element of mutable queue

        return (c.back());

    }

    const_reference back() const

    {    // return last element of nonmutable queue

        return (c.back());

    }

    void push(const value_type& _Val)

    {    // insert element at beginning

        c.push_back(_Val);

    }

    void pop()

    {    // erase element at end

        c.pop_front();

    }

    const _Container& _Get_container() const

    {    // get reference to container

        return (c);

    }

protected:

    _Container c;    // the underlying container

};</span>

由以上可以看出，单向队列queue封装了别的底层数据结构（默认为deque），并改动接口以实现自身特性。

下面给出单向队列的使用范例：

//单向队列 queue支持 empty() size() front() back() push() pop()

#include <queue>

#include <vector>

#include <list>

#include <cstdio>

using namespace std;

int main()

{

    //可以使用list作为单向队列的容器，默认是使用deque的。

    queue<int, list<int>> a;

    queue<int>        b;

    int i;

    //压入数据

    for (i = ; i < ; i++)

    {

        a.push(i);

        b.push(i);

    }

    //单向队列的大小

    printf("%d %d\n", a.size(), b.size());

    //队列头和队列尾

    printf("%d %d\n", a.front(), a.back());

    printf("%d %d\n", b.front(), b.back());

    //取单向队列项数据并将数据移出单向队列

    while (!a.empty())

    {

        printf("%d ", a.front());

        a.pop();

    }

    putchar('\n');

    while (!b.empty())

    {

        printf("%d ", b.front());

        b.pop();

    }

    putchar('\n');

    return ;

}

由以上可知，stl中的单向队列queue以deque（双向队列）为默认的底层数据结构，但queue的实现也可以用list（单链表）作为底层数据结构。

PS：不可以用vector作为底层，原因在于：vector不支持pop_front()。

总之，stl中的单向队列queue：

1、包含头文件<queue>；

2、6个常用操作：size()：queue中元素个数

　　　　　　　　empty()：判空

　　　　　　　　front()：取队首元素

　　　　　　　　back()：取队尾元素

　　　　　　　　push(e)：入队尾

　　　　　　　　pop()：删队首

STL中的单向队列queue的相关教程结束。