队列
（1）基本概念
1）队列的概念：队列（queue，Q）是n个元素组成的有限序列，记做Q=（a₁，a₂，…），并且只能在一端插入和另一端删除元素。当n=0时，称Q为空队列。
2）队列的特性：假设往空队列中依次插入元素a₁，a₂，…，由定义可知，删除这些元素的次序也只能是a₁，a₂，…，也就是说，队列具有先进先出（First in，first out，FIFO）的特性。
3）队列的术语：称插入元素的一端为队尾（rear），删除元素的一端为队头（front）。分别称队列的插入和删除运算为入队和出对。
4）顺序队列与循环队列：称以顺序存储方式存储的队列叫做顺序队列（sequential queue）。在这样的队列中，当rear已指到数组的最后一个元素，即rear=maxlen-1，此时若在执行入队操作，便会出现“溢出”。然而，由于此前可能执行了若干次出队操作，因而数组的前面部分可能还有闲置的元素空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为“假溢出”。显然，必须要解决这一假溢出的现象，才能保证这种结构的正确使用。
采用循环结构就可以解决假溢出的问题，具体方法是：将数组的第一个元素data[0]看作是最后一个元素data[maxlen-1]的下一个存储位置，也就是说，将数组data看做是一个循环结构。这样当执行入队或出队操作时，如果原指针rear或front的值为maxlen-1，即已经指向了数组的最后一个元素时，则执行入队或出队操作后，相应指针的值就要变为0.因此，称这种形式的队列为循环队列（circular queue）。为了区分队列的满和空状态，解决方案是少用一个元素空间，就是将仅剩一个空位置时的状态当做“满”的状态，也就是不让rear指针追上front指针。
（2）队列的运算
头文件：
#ifndef QUEUE_H
#define QUEUE_H
const int maxlen = 100;//队列的存储长度
template <class elementType>
class queue {
public:
queue();
bool empty();
bool full();
bool get_front(elementType &x);
bool append(elementType x);
bool serve();
private:
int count;
int front, rear;
elementType data[maxlen];
};
template <class elementType>
queue<elementType>::queue() {
count = 0;
front = rear = 0;
}
template <class elementType>
bool queue<elementType>::empty() {
return front == rear;
}
template <class elementType>
bool queue<elementType>::full() {
return count == maxlen - 1;
}
template <class elementType>
bool queue<elementType>::get_front(elementType &x) {
if (!empty()) {
x = data[(front + 1) % maxlen];
return true;
}
return false;
}
template <class elementType>
bool queue<elementType>::append(elementType x) {
if (!full()) {
rear = (rear + 1) % maxlen;
data[rear] = x;
++count;
return true;
}
return false;
}
template <class elementType>
bool queue<elementType>::serve() {
if (!empty()) {
front = (front + 1) % maxlen;
--count;
return true;
}
return false;
}
#endif
（3）队列的应用实例
设计算法，输出杨辉三角
杨辉三角的规律是每行的第一个和最后一个数是1，从第三行开始的其余的数是上一行对应位置的左右两个数的和。
源代码：
#include <iostream>
#include "queue.h"
using namespace std;
int main() {
int n;
queue<int> Q;
cout << "输入行数：";
cin >> n;
cout << 1 << endl;
Q.append(1);
for (int i = 2; i <= n; ++i) {
int q1 = 0, q2;
for (int j = 1; j < i; ++j) {
Q.get_front(q2);
Q.serve();
cout << q1 + q2 << " ";
Q.append(q1 + q2);
q1 = q2;
}
cout << 1 << endl;
Q.append(1);
}
cin.get(), cin.get();
}
代码运行实例截图：
