第六章

队列

6.1  基本概念

像栈一样，队列（queue）也是表。然而，使用队列时插入在一端进行而删除则在另一端进行，也就是先进先出（FIFO）。队列的基本操作是EnQueue（入队），它是在表的末端（叫做队尾（rear））插入一个元素；还有DeQueue（出队），它是删除（或返回）在表的开头（叫做队头（front））的元素。

队列一般有链式队列和循环队列两种。链式队列相当于我们在银行中排队，后来的人排到队伍的最后，前面的人办理完业务后就会离开，让下一个人进去；循环队列则跟循环链表很相似。

我在此只写出链式队列的代码，循环队列其实也可以继承自循环链表，就不多罗嗦了。可以看到，队列的实现也是惊人的简单。

6.2  代码实现

队列的实现如下：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   lqueue.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-8 16:49:54
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __LIST_QUEUE_H__
#define __LIST_QUEUE_H__

#include "../../slist/src/slist.h"

template<typename T>
class CLQueue : public CSList<T>
{
public:
    int EnQueue(const T data);
    T   DeQueue();
    T&  GetFront();
    T   GetFront() const;
    T&  GetRear();
    T   GetRear() const;
};

template<typename T>
inline int CLQueue<T>::EnQueue(const T data)
{
    return AddTail(data);
}

template<typename T>
inline T CLQueue<T>::DeQueue()
{
    T data = GetHead();
    RemoveHead();
    return data;
}

template<typename T>
inline T& CLQueue<T>::GetFront()
{
    return GetHead();
}

template<typename T>
inline T CLQueue<T>::GetFront() const
{
    return GetHead();
}

template<typename T>
inline T& CLQueue<T>::GetRear()
{
    return GetTail();
}

template<typename T>
inline T CLQueue<T>::GetRear() const
{
    return GetTail();
}

#endif  // __LIST_QUEUE_H__

调用如下：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   queue.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-8 17:00:40
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include "lqueue.h"
using namespace std;

int main()
{
    CLQueue<int> queue;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    queue.EnQueue(1);
    queue.EnQueue(2);
    queue.EnQueue(3);

    while (!queue.IsEmpty())
        cout << queue.DeQueue() << endl;
}

6.3  应用

队列的应用一般来说是模拟现实生活中的一些离散现象，例如银行排队、打印机任务、接线员工作等等。还有的就是使用队列来提高运行效率的算法，这些一般是在图算法中使用到。考虑到队列的应用要么是比较简单，要么是在特定的环境中进行，因此我就不给出应用的例子了，如果您有兴趣的话可以自行试试。