概念：队列是限定只能在表的一端进行插入在另一端进行删除操作。在表中，允许插入的一端称为“队列尾”，允许删除的另一端称为“对列尾”
顺序队列：
定义：概念：队列的顺序存储结构为顺序队列，顺序队列实际上是运算受限的顺序表
顺序队列的表示：1.和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素 2.由于队列的队头和队尾的位置时变化的，设置俩个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值再队列初始化时均应置为0，表示队列为空
顺序队列的基本操作：1.入队时：将新元素插入rear所指的位置，然后将rear加1 2.出队时：删去front所指的元素，然后将front加1并返回被删除元素 注意： 1.当头尾指针相等时，队列为空 2.在非空队列里，队头指针始终指向队头元素，指针始终指向下一个元素的下一个
顺序队列的溢出现象：1.“下”溢现象，当队列为空时，作出队运算产生的溢出现象，“下溢”常用作程序控制转移的条件 2.“真上溢”现象，当队列满时，做入队运算产生空间溢出的现象。“真上溢”是一种出错状态，要设法避免 3.“假上溢”：由于入队和出队操作中，头尾指针只指向后增加不减小，致使出队元素的空间永远无法重新利用。当队列实际的元素个数远远小于空间的规模，但可能由于队尾指针已超越空间的上界，没有空间。
循环队列：为充分利用空间，克服“假上溢”现象的方法是：将空间想象为一个首尾相接的圆环，存储在其中的队列称为循环队列。
循环队列的基本操作：循环队列中进行出队，入队操作时，头尾指针仍要加1，向后移动，只不过当队尾指针指向空间上界时，其加1操作的结果是指向向量的下界0，即循环回到头部，这种循环意义下加1操作可以描述为：
1.未超越循环队列的长度时，指针加1 if(i+1==queueSize) i= 0; else i++; 2.超越循环队列的长度时，利用“模运算”，将指针指向头部 i = (i+1)%queueSize;
循环队列的边界条件处理：循环队列由于入队时队尾指针向前追赶队首指针；出队时队首指针向前追赶队尾指针，队首队尾指针指向相同位置时，无法区分是队空还是队满，无法通过件front==rear来判别队列是空还是满。 1.单独设置一个布尔变量以区别队列的空和满 2.浪费一个元素的空间。规定入队操作前，先测试队尾指针在循环意义下加1后是否等于头指针，若相等则认为满队 3.使用一个计数器记录队列中元素的总数，通过队列长度和队列的容量大小，判断是否越界。
#define _CRT_SECURE_NO_WARNINGS #include<iostream.h> template <class T> class SeqQueue // 顺序循环队列类 { private: T *element; //动态数组存储队列的数据元素 int size; int front,rear; public: SeqQueue(int size=64); //构造指定容量的空队列 ~SeqQueue(); bool isEmpty(); //判断是否为空 void enqueue(T x); //入队 T dequeue(T x); //出队，返回队头元素。若队列空则抛出异常 friend ostream& operator <<(ostream& out, SeqQueue<T>&que); }; template<class T> SeqQueue<T>::SeqQueue(int size) { this->size = size<64?64:size; element = new T [this->size]; front = rear =0; } template <class T> SeqQueue<T>::~SeqQueue() { delete []element; } template<class T> bool SeqQueue<T>::isEmpty() { return front == rear; } template <class T> void SeqQueue<T>::enqueue(T x) //入队 { if(front == (rear+1)%size) { T *temp =element; element = new T [size*2]; // 重新申请一个容量更大的数组 int i=front, j=0; while(i!=rear) { element[j]=temp[i]; i=(i+1)%size; j++; } front = 0; rear = j; size *=2; } element[rear] = x; rear = (rear+1)%size; } template<class T> T SeqQueue<T>::dequeue() { if(!isEmpty()) { T x =element[front]; front = (front + 1)%size; return x; } throw "空队列，不能执行出队操作"; } template<class T> ostream& operator <<(ostream& out, SeqQueue<T>&que) { out<<"SeqQueue:("; int i=que.front; while(i!que.rear) { out<<que.element[i]<<" "; i=(i+1)%que.size; } out<<")"<<endl; return out; }
链式队列：链式队列和单链表一样，可以附加一个头结点，真正的队头元素并非在队头指针所指的结点中，而在队头指针所指的后继结点中。也可以用不带头结点的单链表实现。
#include<iostream.h> #include "Node.h" template<class T> class LinkedQueue { private: Node<T> *front,*rear; public: LinkedQueue(); ~LinkedQueue(); bool isEmpty(); void enqueue(T x); T dequeue(); friend ostream&operator<<(ostream& out,LinkedQueue<T>&que); }; template<class T> LinkedQueue<T>::LinkedQueue() { front = rear =NULL; } template <class T> LinkedQueue<T>::~LinkedQueue() { Node<T> *p=front,*q; while(p!=NULL) { q=p; p=p->next; delete q; } front = rear=NULL; } template<class T> bool LinkedQueue<T>::isEmpty () { return front==NULL&&rear==NULL; } template<class T> void LinkedQueue<T>::enqueue(T x) { Node<T> *q =new Node<T>(x); if(isEmpty()) front =q; else rear->next=q; rear = q; } template<class T> T LinkedQueue<T>::dequeue() { if(!isEmpty()) { T x=front->data; Node<T> *p=front; front = front->next; delete p; if(front==NULL) rear = NULL; return x; } throw "空队列不能执行出队操作"; } template <class T> ostream& operator<<(ostream& out,LinkedQueue<T>&que) { out<<" LinkedQueue: ("; Node<T> *p=que.front; while(p!=NULL) { out<<p->data; p=p->next; if(p!=NULL) cout<<","; } out<<")"<<endl; return out; }
打印杨辉三角：
#define _CRT_SECURE_NO_WARNINGS #include<stdlib.h> #include<iostream> #include "SeqQueue.h" void yanghui(int n) { int s,e; //打印出杨辉三角的前n行 SeqQueue<int> *sq = new SeqQueue<int> (n+2); for(int i = 1;i<=n;i++) cout<<' '; cout<<'1'<<endl; //在中心位置输出杨辉三角的1 sq->enqueue(0); //添加行界值 sq->enqueue(1); sq->enqueue(1); //第一行值输入队列 int k = 1; while(k<n) { //通过循环队列输出前n-1行的值 for(i = 1;i<=n-k;i++) cout<<' ';//输出n-k个空格以保持杨辉三角 sq->enqueue(0); //行界值“0”入队列 do{ s=sq->dequeue(); e=sq->getHead(); if(e) cout<<e<<' ';//若e为非行界值，则打印输出e的值并加一空格 else cout<<endl; // 否则回车换行，为下一行输出做准备 sq->enqueue(s+e); }while(e!=0) k++; } } int main() { int s; cout<<"请输入整数："<<endl; cin>>s; yanghui(s); return 0; }