第六章

队列

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  应用

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