queue(队列)

队列也是一种逻辑数据结构，其具有先进先出的特性，针对这种特性，可以实现一些较为复杂的逻辑。在实际应用中，部分程序也正需要这样一种顺序进出的数据处理方式。使用这样的逻辑处理方式，使得我们可以将更多精力放在如何处理顺序逻辑之外的事情，对于编程、开发来讲，提供了极大的方便。

同stack类似，queue也可以看成是容器的容器，内部是使用其它容器来存放具体数据。加了一个外壳，使得我们的数据操作只能是在头或尾。从尾部添加数据，从头部取数据，从而实现FIFO的特性。同stack一样，内部默认数据存放容器为deque，若要用非默认容器初始化，必须要在模板中指定容器类型。

构造函数

std::deque<int> mydeck (3,100);        // deque with 3 elements
std::list<int> mylist (2,200);         // list with 2 elements

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

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

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';

常用函数

std::deque<int> mydeck (3,100);    // deque with 3 elements
std::list<int> mylist (2,200);     // list with 2 elements

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


first.empty();   //队列是否为空
int size;
size = first.size();    //队列元素个数
int n;
n = first.front();   //返回队头元素
n = first.back();    //返回队尾元素
first.push(20);      //向队列添加元素，添加到队尾
first.pop();         //删除下一个元素，也即队头元素

队列应用

• 应用一：用队列实现栈

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

using namespace std;

//用一个队列实现栈
template<class T>
class MyNewStack{

private:
    int count;
    queue<T> myQueue;

public:
    MyNewStack() :count(0)
    {

    }

    int size()
    {
        return count;
    }

    void push(T element)
    {
        count++;
        myQueue.push(element);
    }

    T top()
    {
        return myQueue.back();
    }

    void pop()
    {
        int tmp;
        for (int i = 0; i < count - 1; i++)
        {
            tmp = myQueue.front();
            myQueue.pop();
            myQueue.push(tmp);
        }

        myQueue.pop();

    }

};

int main()

    //利用一个queue实现stack
    MyNewStack<int> myStack;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    cout << myStack.top() << endl;
    cout << myStack.top() << endl;
    myStack.pop();
    cout << myStack.top() << endl;

    myStack.push(40);
    cout << myStack.top() << endl;

    return 0;
}

• 应用二：图的广度优先遍历(BFS)

#include <iostream>
#include <queue>

using namespace std;

//无向图图的广度优先遍历(BFS) 
class GraphBFS{

    int ** data;  //邻接矩阵存储图
    int * flag;   //标记结点是否已经访问
    int N;        //结点个数

public:
    GraphBFS() :data(NULL)
    {

    }

    void setData(int **arr, int n)
    {
        data = new int*[n];
        for (int i = 0; i < n; i++)
        {
            data[i] = new int[n];           
            memcpy(data[i], (arr+i), sizeof(int)*n);
        }

        this->N = n;

        flag = new int[N];
        memset(flag, 0, sizeof(int)*N);


    }

    //广度优先遍历
    void BFSTraverse(int start)
    {
        if (data == NULL)
        {
            cout << "There is no graph data" << endl;
        }
        else
        {
            //寻找起始点
            queue<int>  myQueue;
            cout << start << endl;  //访问起始结点
            myQueue.push(start);

            while (!myQueue.empty())
            {
                int tmp = myQueue.front();
                myQueue.pop();

                //寻找邻接结点，并访问
                for (int i = tmp+1; i < N; i++)
                {
                    if (data[tmp][i] == 1 && flag[i] == 0)
                    {

                        cout << i << endl;   //访问邻接结点
                        flag[i] = 1;         //标记为已访问
                        myQueue.push(i);
                    }
                }

            }
        }

    }

};


int main()
{
    //图的广度遍历
    int data[6][6] = {
        0, 1, 1, 1, 0, 0,
        1, 0, 0, 1, 0, 0,
        1, 0, 0, 0, 0, 0,
        1, 1, 0, 0, 1, 0,
        0, 0, 0, 1, 0, 1,
        0, 0, 0, 0, 1, 0
    };

    GraphBFS graphBFS;
    graphBFS.setData((int**)data, 6);
    graphBFS.BFSTraverse(0);

    return 0;
}