05、数据结构与算法C++：队列-程序员江小北

队列

食堂打饭、车站买票等等我们都需要排队，有新人加入时排在队尾，队头完成相应的操作就会从队头位置离开。在数据结构中也有类似的结构——队列。

队列 ( queue ) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出 ( First In First Out) 的线性表，简称 FIFO 。允许插入的一端称为队尾，允许删除的一端称为队头。

循环队列

队列的顺序存储结构存在着不足，当我们用数组实现队列时，出队时清除了下标为0的位置的数据元素，为了保证该位置不空，就需要将后面的位置上的数据元素依次前移，这样时间复杂就为O(n)。为了避免出现这样的问题，我们把队列的头尾相连，这就是循环队列。我们来看下循环队列的代码结构：

class Queue
{
public:
    Queue(int len=6);
    ~Queue();
    bool en_queue(int val);//入队
    bool out_queue(int& val);//出队
    void traverse_queue();//遍历
    bool is_full();//判断是否为满
    bool is_empty();//判断是否为空
private:
    int len;//数组长度
    int* pBase;//数组位置
    int front;//队头
    int rear;//队尾
};

队列操作的具体代码实现：

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

Queue::Queue(int len) :len(len), pBase(new int[len]), front(0), rear(0)
{

}
Queue::~Queue()
{
}
bool Queue::en_queue(int val)
{
    if (is_full())return false;
    pBase[rear] = val;
    rear = (rear + 1) % len;
    return true;
}
void Queue::traverse_queue()
{
    int i = front;
    while (i != rear)
    {
        cout << pBase[i] << " " ;
        i = (i + 1) % len;

    }
    cout << endl;
}
bool  Queue::is_full()
{
    return (rear + 1) % len == front ? true : false;
}
bool Queue::out_queue(int& val)
{
    if (is_empty())return false;
    val = pBase[front];
    front = (front + 1) % len;
    return true;
}
bool Queue::is_empty()
{
    return front == rear ? true : false;
}

这里需要注意的是出队后，队头front = (front + 1) % len；入队操作后，队尾rear = (rear + 1) % len。同时为了准确判断队列的空满情况，队列满时为len-1。如果需要队列满时长度为len，需要另外定义一个变量表示队列的长度用来判断空满情况。

#include<iostream>
#include "Queue.h"

using namespace std;

int main()
{
    Queue Q;
    int val;
    Q.en_queue(1);
    Q.en_queue(2);
    Q.en_queue(3);

    Q.traverse_queue();
    if (Q.out_queue(val))
    {
        cout << "出队成功，出队的元素是：" << val << endl;
    }
    else
    {
        cout << "出队失败" << endl;
    }
    Q.traverse_queue();
    system("pause");
    return 0;
}

VS上运行结果如下：

队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。
我们先定义结点：

class Node
{
public:
    Node();
    ~Node();
    friend class Queue;
private:
    int data;//数据域
    Node* pNext;//指针域
};

定义链队列：

#include "Node.h"
class Queue
{
public:
    Queue();
    ~Queue();
    bool en_queue(int val);//入队
    bool out_queue(int& val);//出队
    void traverse_queue();//遍历
    bool is_empty();//判断是否为空
private:
    Node* front;//队头
    Node* rear;//队尾
};

链队列操作的具体代码实现：

#include "Queue.h"
#include "Node.h"
#include<iostream>

using namespace std;
Queue::Queue()//初始化
{
    Node * pnew = new Node;
    front = pnew;
    rear = pnew;
    rear->pNext = NULL;
}
Queue::~Queue()
{
}
bool Queue::en_queue(int val)//入队
{
    Node* pnew = new Node;
    pnew->data = val;
    pnew->pNext = NULL;
    rear->pNext = pnew;
    rear = pnew;
    return true;
}
bool Queue::out_queue(int& val)//出队
{
    if (is_empty())return false;
    Node* p;
    p = front->pNext;
    val = p->data;
    front->pNext = p->pNext;
    if (p == rear)rear = front;
    delete p;
    return true;
}
void Queue::traverse_queue()//遍历
{
    Node* p=front;
    while (p != rear)
    {
        cout << p->pNext->data << " ";
        p = p->pNext;
    }
    cout << endl;
}
bool Queue::is_empty()//判断是否为空
{
    return rear == front ? true : false;
}

注意空队列时，front 和 rear 都指向头结点。

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

int main()
{
    Queue Q;
    int val;
    Q.en_queue(1);
    Q.en_queue(2);
    Q.en_queue(3);
    Q.en_queue(4);
    Q.en_queue(5);
    Q.traverse_queue();
    if (Q.out_queue(val))
    {
        cout << "出队成功，出队的元素是：" << val << endl;
    }
    else
    {
        cout << "出队失败" << endl;
    }
    Q.traverse_queue();
    system("pause");
    return 0;
}

VS上运行结果如下：