队列(Queue)

是一种操作受限的线性表。它只允许在线性表的一端进行插入操作,在另一端进行删除操作。允许插入的一端称作队尾(rear),允许删除的一端称作队头(front),在队尾进行插入的操作称为入队,在对头进行删除的操作称作出队。不包含任何数据的队列称为空队。

队列基本运算如下(循环队列):

const int QueueSize = 1000; // 循环队列最大长度
template<class T>
class CircleQueue {
    public:
        CircleQueue() { front = rear = 0;} // 构造函数
        void EnQueue(T x); // 入队
        T DeQueue(); // 出队
        T GetFront(); // 获取队头数据
        T GetRear(); // 获取队尾数据
        int GetLength(); // 队列长度
        bool Empty() { return front == rear; } // 判断是否为空队列
    private:
        int front,rear;
        T data[QueueSize];
};

循环队列

类似于顺序表,队列也可以采用顺序储存结构进行储存。即使用数组储存元素。由于队列操作是在队列两段进行的,因此一般需要设置队头和队尾两个指针。对于空队列,队头和队尾均为-1。随着元素的入队,队尾不断后移,出队时,队头指针也后移。为了方便操作,队列需要腾出一个元素不使用,这里队列的第一个元素为front指针所指的下一个。在这里我们规定队头指针所指的位置永远不储存队列元素。

下面是循环队列:

/*************************************************************************
    > File Name: CircleQueue.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Sat 25 Apr 2015 21:08:27 CST
 ************************************************************************/

#include<iostream>
using namespace std;

const int QueueSize = 1000; // 循环队列最大长度
template<class T>
class CircleQueue {
    public:
        CircleQueue() { front = rear = 0;} // 构造函数
        void EnQueue(T x); // 入队
        T DeQueue(); // 出队
        T GetFront(); // 获取队头数据
        T GetRear(); // 获取队尾数据
        int GetLength(); // 队列长度
        bool Empty() { return front == rear; } // 判断是否为空队列
    private:
        int front,rear;
        T data[QueueSize];
};

template<class T>
void CircleQueue<T>::EnQueue(T x) {
    if((rear+1)%QueueSize == front) throw "上溢!";
    rear = (rear + 1) % QueueSize;
    data[rear] = x;
    return;
}

template<class T>
T CircleQueue<T>::DeQueue() {
    if(Empty()) throw "空队列!";
    front = (front + 1) % QueueSize;
    return data[front];
}

template<class T>
T CircleQueue<T>::GetFront() {
    if(Empty()) throw "空队列!";
    return data[(front+1)%QueueSize];
}

template<class T>
T CircleQueue<T>::GetRear() {
    if(Empty()) throw "空队列!";
    return data[rear];
}

template<class T>
int CircleQueue<T>::GetLength() {
    return (rear - front + QueueSize) % QueueSize;
}

int main() {
    CircleQueue<int> queue;
    cout << "长度: " << queue.GetLength() << endl;
    for(int i=1; i<=10; ++i) {
        queue.EnQueue(i);
        cout << "队首元素: " << queue.GetFront() << "队尾元素: " << queue.GetRear() << "长度: " << queue.GetLength() << endl;
    }
    cout << "-----------------------------" << endl;
    for(int i=1; i<=10; ++i)  {
        cout << "队首元素: " << queue.GetFront() << "队尾元素: " << queue.GetRear() << "长度: " << queue.GetLength() << endl;
        queue.DeQueue();
    }
    cout << "长度: " << queue.GetLength() << endl;
    return 0;
}

链队列

队列的链式储存称为链队列,因此链队列可看成仅在表头删除和表尾插入的单链表。在这里我们规定队头指针所指的位置永远不储存队列元素。

下面是链队列:

/*************************************************************************
    > File Name: LinkQueue.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Sat 25 Apr 2015 21:08:27 CST
 ************************************************************************/

#include<iostream>
using namespace std;

template<class T>
struct Node {
    T data;
    Node *next;
};

template<class T>
class LinkQueue {
    public:
        LinkQueue() {
            front = rear = new Node<T>;
            rear->next = NULL;
        }
        ~LinkQueue();
        void EnQueue(T x);
        T DeQueue();
        T GetFront();
        T GetRear();
        int GetLength();
        bool Empty() { return front == rear; }
    private:
        Node<T> * front;
        Node<T> * rear;
};

template<class T>
void LinkQueue<T>::EnQueue(T x) {
    rear->next = new Node<T>;
    rear = rear->next;
    rear->data = x;
    rear->next = NULL;
    return;
}

template<class T>
T LinkQueue<T>::DeQueue() {
    if(Empty()) throw "空队列!";
    Node<T> *p = front->next;
    T x = p->data;
    front->next = p->next;
    delete p;
    if(!front->next) rear = front;
    return x;
}

template<class T>
T LinkQueue<T>::GetFront() {
    if(Empty()) throw "空队列!";
    return front->next->data;
}

template<class T>
T LinkQueue<T>::GetRear() {
    if(Empty()) throw "空队列!";
    return rear->data;
}

template<class T>
int LinkQueue<T>::GetLength() {
    Node<T> *p = front->next;
    int len = 0;
    while(p) {
        p = p->next;
        ++len;
    }
    return len;
}
template<class T>
LinkQueue<T>::~LinkQueue() {
    while(front) {
        rear = front->next;
        delete front;
        front = rear;
    }
}



int main() {
    LinkQueue<int> queue;
        cout << "长度: " << queue.GetLength() << endl;
    for(int i=1; i<=10; ++i) {
        queue.EnQueue(i);
        cout << "队首元素: " << queue.GetFront() << "队尾元素: " << queue.GetRear() << "长度: " << queue.GetLength() << endl;
    }
    cout << "-----------------------------" << endl;
    for(int i=1; i<=10; ++i)  {
        cout << "队首元素: " << queue.GetFront() << "队尾元素: " << queue.GetRear() << "长度: " << queue.GetLength() << endl;
        queue.DeQueue();
    }
    cout << "长度: " << queue.GetLength() << endl;
    return 0;
}

运行结果如下:

长度: 0
队首元素: 1队尾元素: 1长度: 1
队首元素: 1队尾元素: 2长度: 2
队首元素: 1队尾元素: 3长度: 3
队首元素: 1队尾元素: 4长度: 4
队首元素: 1队尾元素: 5长度: 5
队首元素: 1队尾元素: 6长度: 6
队首元素: 1队尾元素: 7长度: 7
队首元素: 1队尾元素: 8长度: 8
队首元素: 1队尾元素: 9长度: 9
队首元素: 1队尾元素: 10长度: 10
-----------------------------
队首元素: 1队尾元素: 10长度: 10
队首元素: 2队尾元素: 10长度: 9
队首元素: 3队尾元素: 10长度: 8
队首元素: 4队尾元素: 10长度: 7
队首元素: 5队尾元素: 10长度: 6
队首元素: 6队尾元素: 10长度: 5
队首元素: 7队尾元素: 10长度: 4
队首元素: 8队尾元素: 10长度: 3
队首元素: 9队尾元素: 10长度: 2
队首元素: 10队尾元素: 10长度: 1
长度: 0