数据结构笔记（第三章）

第三章：线性结构之栈和队列

栈

1.栈的定义：只允许在一端插入和删除 的线性表。 允许插入和删除的一端称为栈顶 (top)，另一端称栈底(bottom) 。

2.栈的特点：后进先出 (LIFO) 。

//栈的抽象数据类型 
template <class T>   //此程序放入stack.h  
class Stack {            //栈的类定义 
public:      
Stack( ){ };                //构造函数      
virtual void Push(T& x) = 0;                //进栈      
virtual bool Pop(T& x) = 0;           //出栈      
virtual bool getTop(T& x)const = 0; //取栈顶      
virtual bool IsEmpty( ) const= 0;      //判栈空      
virtual bool IsFull( ) const= 0;         //判栈满       
virtual int getSize( )const =0; 
}； 栈

顺序栈

基于数组的存储表示

//栈的数组存储表示 — 顺序栈 
#include <assert.h>                            //P89程序3.2 
#include <iostream.h> 
#include “stack.h”                  //P88栈的类定义 
const int stackIncrement=20;
template <class T> 
class SeqStack : public Stack<T> {     //顺序栈类定义 
private:           
T *elements;          //栈元素存放数组      
int top;                        //栈顶指针      
int maxSize;                                 //栈最大容量      
void overflowProcess();             //栈的溢出处理 
public:      
SeqStack(int sz =50);                //构造函数      
～SeqStack() { delete []elements; }   //析构函数      
void Push(const T& x);       
bool Pop(T& x);                        //出栈      
bool getTop(T& x);             //取栈顶内容      
bool IsEmpty() const { return top == -1; }      
bool IsFull() const { return top == maxSize-1; }     
int  getSize( )const {return top+1 ; }    
void makeEmpty( ){top=-1 ; }
}; 

//顺序栈的操作
template <class T> 
void SeqStack<T>::overflowProcess() {   
//私有函数：当栈满则执行扩充栈存储空间处理  
T *newArray = new T[maxSize+stackIncrement];         //创建更大的存储数 
if(newArray==NULL){cerr<<“失败”<<endl; 
exit(1); }  
for (int i = 0; i <= top; i++)           
newArray[i] = elements[i];   
maxSize += stackIncrement ;        
delete [ ]elements;       
elements = newArray;     //改变elements指针 
};  
template <class T> 
void SeqStack<T>::Push(const T& x) {    
//若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理    
if (IsFull() == true) overflowProcess();       //栈满    
elements[++top] = x;                             //栈顶指针先加1, 再进栈
};  
template <class T> 
bool SeqStack<T>::Pop(T& x) { 
//函数退出栈顶元素并返回栈顶元素的值    
if (IsEmpty() == true) return false;   
x = elements[top--];//先取值，然后栈顶指针减1       
return true;                              //退栈成功 
};   
template <class T>
bool SeqStack<T>::getTop(T& x) { //若栈不空则函数返回该栈栈顶元素的地址   
if (IsEmpty() == true) return false;  
x = elements[top];     
return true; 
};

双栈共享一个栈空间

 两个栈共享一个数组空间V[maxSize]

 设立栈顶指针数组 t[2] 和栈底指针数组 b[2]

​ t[i]和b[i]分别指示第 i 个栈的栈顶与栈底

 初始 t[0] = b[0] = -1, t[1] = b[1] = maxSize

 栈满条件：t[0]+1 == t[1] //栈顶指针相遇

 栈空条件：t[0] = b[0]或t[1] = b[1] //退到栈底

链式栈

基于链表的存储表示

链式栈不需要附加头结点，因为栈是特殊的线性表，只能在栈顶（即链表头部）插入或删除，所以 不需要附加头结点。

//链式栈 (LinkedStack)类的定义
template <class T> 
class LinkedStack : public Stack<T> { //链式栈类定义    
private:   LinkNode<T> *top;                         //栈顶指针   
void output(ostream& os, StackNode <T> *ptr); //递归输出栈的所有元素 
public:      
LinkedStack( ) : top(NULL) { }               //构造函数;说明链式栈无无附加头结点 
~LinkedStack( ) { makeEmpty( ); }           //析构函数   
void Push(T x);                   //进栈      
bool Pop(T& x);                 //退栈      
bool getTop(T& x) const;             //取栈顶                
bool IsEmpty( ) const { return top == NULL; }      
int getSize( )const;                     //求栈中元素个数      
void makeEmpty();   //清空栈的内容      
friend ostream& operator << (ostream& os,            
LinkedStack<T>& s) { }                          
//输出栈元素的重载操作 <<           
//书上的参数SeqStack应为LinkedStack 
}; 

//链式栈类操作-求个数 
template <class T>  
int LinkedStack<T>::getSize( )const{  
LinkNode<T> *p=top; 
int k=0; 
while(p!=NULL) {k++; p=p->link;} //p94书上的while语句里用的top应为p。 
return k; 
} 

//链式栈类操作-置空 
template <class T> 
void LinkedStack<T>::makeEmpty( ) {  
//逐次删去链式栈中的元素直至栈顶指针为空。     
LinkNode<T> *p;  
while (top != NULL)            //逐个结点释放         
{ p = top;  top = top->link;  delete p; } 
}; 
 
//链式栈类操作-进栈 
template <class T> 
void LinkedStack<T>::Push(const T& x) { 
//将元素值x插入到链式栈的栈顶,即链头。     
top = new StackNode<T> (x, top);     
//创建新结点//同时插入到top前面，然后top指向新 结点即新栈顶   
//类似于P76InsertAfter里link=new Term(c,e,link);      
assert (top != NULL);       //创建失败退出 
//assert断言机制，若参数条件满足继续执行否则 
//出错处理，终止执行 
}; 
 
//链式栈类操作-出栈 
template <class T> 
bool LinkedStack<T>::Pop(T& x) { //删除栈顶结点, 返回被删栈顶元素的值。      
if (IsEmpty() == true) return false;   //栈空返回     
LinkNode<T> *p = top;  //暂存栈顶元素   
top = top->link;       //退栈顶指针   
x = p->data;   
delete p;          //释放结点      
return true;  
}; 

//链式栈类操作-获取栈顶元素值 
template <class T> bool 
LinkedStack<T>::getTop(T& x) const {    
if (IsEmpty() == true) return false;   //栈空返回   
x = top->data;                       //返回栈顶元素的值      
return true;  
}; 
 
//链式栈类操作-输出 
template <class T> 
ostream& operator << (ostream& os, LinkedStack<T>& s) { //从栈顶开始逐个输出 
os<<“栈中元素个数=”<<s.getSize( )<<endl; 
StackNode<T> *p=s.top;         //书上S.top应为s.top 
int i=0;   
while(p!=NULL) {  
os<<++i<<“:”<<p->data<<endl;  
p=p->link;} 
return os; 
}  

//链式栈类操作-递归输出 
template <class T> 
void LinkedStack<T>::output(ostream& os,      
StackNode<T> *ptr) {     
int i=1；     //递归输出栈中所有元素（沿链逆向输出）  
if (ptr != NULL) {     
if (ptr->link != NULL)                
output(os, ptr->link, i++);    
os << i << “ : ” << ptr->data << endl;                    
//递归结束条件ptr->link != NULL，                  
//输出最后一个元素，然后沿链逐个返回输出 
  } 
};

栈的应用：括号匹配

如从左向右扫描，则每个右括号将与最近遇到的未匹配的左括号匹配。

把从左向右扫描到的左括号放入栈中，在后续扫描中遇到右括号时，就将它与栈顶的左括号 （如果存在）相匹配，同时在栈顶删除该左括号。
分析可能出现的不匹配的情况

1．到目前左括号少即：到来的是右括号而栈中无左括号在等待（栈是空的）

2．到结束右括号少。即：栈中还有左括弧没等到和它相匹配的右括弧

算法的设计思想

1)凡出现左括弧，则进栈；

2)凡出现右括弧，首先检查栈是否空若栈空，则表明“右括弧”多了，不匹配，否则“左括弧出栈”；

3）表达式检验结束时，若栈空，则匹配正确 否则说明左括弧多了,不匹配。

void PrintMatchedPairs(char* expression){   
Stack<int> s(maxLength);   
int j, length=strlen(expression);   
for ( int i=1; i<length; i++) {      
if ( expression[i-1]==‘(’ )  s.Push(i);   
else if ( expression[i-1]==‘)’ ) {           
if ( s.Pop(j)==true )             
cout<<j<<“与”<<i<<“匹配”<<endl;           
else             
cout<<“没有与”<<i<<“匹配的左括号”<<endl;         
}   
while ( s.IsEmpty( )==false ) {     
s.Pop(j);     
cout <<“没有与”<<j<<“匹配的左括号”<<endl; } 
}

栈的应用：表达式求值

一个表达式由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成。

 算术表达式有三种表示：

 中缀(infix)表示 <操作数> <操作符> <操作数>，如 A+B；

 前缀(prefix)表示 <操作符> <操作数> <操作数>，如 +AB；

 后缀(postfix)表示 <操作数> <操作数> <操作符>，如 AB+；

表达式

中缀表达式 a + b * ( c - d ) - e / f

后缀表达式 a b c d - * + e f / -

前缀表达式 - + a * b – c d / e f

结论

1）操作数之间的相对次序不变

2）运算符之间的的相对次序不同

3）前缀式的运算规则为：

连续出现的两个操作数和在它们之前且紧靠它们的运算符 构成一个最小表达式；

4）后缀式的运算规则为：

运算符在式中出现的顺序恰为表达式的运算顺序； 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小 表达式；

算术表达式运算规则

运算规则：

先左后右，先乘除后加减，先括弧内后括弧外 。

例如：4+2*3-10/5=4+6-10/5=10-10/5= 10-2=8

​ 4 2 3 * + 10 5 / - = 8

实现方法讲解:

• 中缀表达式直接求值法

  借助于栈：OPND栈和OPTR栈

  操作数入OPND栈，算符入OPTR栈

• 中缀变后缀表达式求值：

  运算符顺序变化，需存储“等待中” 的运算符

  需将当前运算符与等待中最后一个运算符比较

如何从中缀表达式求得后缀式？

利用堆栈存储“等待中”的运算符实现中缀变后缀表达式,为了实现这种转换，需要考虑各操作符在栈 内和栈外的优先级

 对原表达式中出现的每一个运算符是否即刻 进行运算取决于在它后面出现的运算符

 如果它的优先数“高或等于”后面的运算， 则它的运算先进行，

 否则就得等待在它之后出现的所有优先数高 于它的“运算”都完成之后再进行。

从原表达式求得后缀式的规则为 :

1) 设立运算符栈；

2) 设表达式的结束符为“#”，预设运算符栈 的栈底为“#”；

3) 若当前字符是操作数，则直接发送给后缀式；

4) 若当前字符为运算符且优先数高于栈顶运算 符，则进栈，否则退出栈顶运算符发送给后 缀式；

5) 若当前字符是结束符，则自栈顶至栈底依次 将栈中所有运算符发送给后缀式；

注意：

一般作为相同运算符，先出现的比后出现的 优先级高；

先出现的运算符优先级低于“(”，高于“)”；

优先权相等的仅有“(”和“)”、“#”。

 #：作为表达式结束符，通常在表达式之前 加一“#”使之成对，当出现“#”=“#”时，表 明表达式求值结束，“#”的优先级最低。
任意相继出现的算符θ1和θ2，都要比较优先权 关系。 一般任意两个相继出现的两个算符θ1和θ2之间 的优先关系至多有下面三种之一： θ1<θ2 θ2的优先权高于θ1 θ1=θ2 二者优先权相等 θ1>θ2 θ2的优先权低于θ1

中缀式转换为后缀式的算法 :

（isp叫做栈内(in stack priority)优先数; icp叫做栈外(in coming priority)优先数。操作符优先数相等的情况只出现在括号配对或 栈底的“#”号与输入流最后的“#”号配对时。）

操作符栈初始化，将符号‘#’进栈。然后读 入中缀表达式字符流的首字符ch。

 重复执行以下步骤，直到栈为空，停止循 环。

 若ch是操作数直接输出，读入下一个字 符ch。

 若ch是操作符，判断ch的优先级icp和位 于栈顶的操作符op的优先级isp：
 若 icp(ch) > isp(op)，令ch进栈，读入下一 个字符ch。

 若 icp(ch) < isp(op)，退栈并输出。

 若 icp(ch) == isp(op)，退栈但不输出，若 退出的是“(”号读入下一个字符ch。

 算法结束，输出序列即为所需的后缀表达式

void postfix ( expression e ) {   
stack<char> s;   
char ch, op;    
s.Push ( ‘#’ );   
cin.Get ( ch ); 
while ( ! s.IsEmpty( )) // 课本代码有问题  
//循环条件也可以为while(ch!=‘#’||s.getTop()!=‘#’) 
        if ( isdigit ( ch ) )            
        { cout << ch;  cin.Get ( ch ); }        
        else {             
        if ( isp ( s.GetTop( ) ) < icp ( ch ) ) c
             { s.Push ( ch );  cin.Get ( ch ); 
             }           
             else if ( isp ( s.GetTop( ) ) > icp ( ch ) )              
             { s.Pop(op);   
             cout << op; 
             }            
             else { s.Pop(op);                  
             if ( op == ‘(’ ) cin.Get ( ch ); }   
             }
             }

class Calculator { //模拟一个简单计算器 
public:           
  Calculator(int sz):s(sz){}; //构造函数           
  void Run();             //执行表达式计算           
  void Clear(); 
private:             
  Stack<double> s;      //栈对象定义          
  void  AddOperand(double value) ;  //进操作数栈           
  bool Get2Operands(double& left,double& right);                             
  //从栈中退出两个操作数           v
  oid DoOperator(char op); //形成运算指令,进行计算 
  }; 
void Calculator :: Run ( ) {    
   char ch;   double newoperand;    
   while ( cin >> ch,  ch != ‘#’ ) {        
     switch ( ch ) {         
       case ‘+’ :           
       case ‘-’ :            
       case ‘*’ :           
       case ‘/’ :   
       DoOperator ( ch );                             
       break;   //计算         
      default :  cin.putback ( ch );                              
                                //将字符放回输入流                   
       cin >> newoperand;  //读操作数                        
          AddOperand ( newoperand );       
          }    
       }

栈的应用：递归

递归的定义

若一个对象部分地包含它自己，或用它自己 给自己定义, 则称这个对象是递归的；若 一个过程直接地或间接地调用自己, 则称这 个过程是递归的过程。

函数间的的执行

1 .操作系统中，当一个函数调用另一个函数，需先完成：

1) 将所有的实在参数、返回地址等信息传递给被调用函数保存

2) 为被调用函数的局部变量分配存储区；

3) 将控制转移到被调用函数的入口。

2 .从被调用函数返回调用函数之前，应该完成：

1) 保存被调函数的计算结果；

2) 释放被调函数的数据区；

3) 依照被调函数保存的返回地址将控制转移到调用函数

递归函数的概念

直接或间接地调用自身的函数称为递归函数。 从递归函数的执行过程看，递归函数设计时必须 有一个出口，直接处理, 从而结束对自身的调用。

构成递归的条件

不能无限制地调用本身， 必须有一个出口，直接处理。

递归定义包括两项，一是边界条件：描述递归终止时问题的求解 ；二是递归函数：将问题分解为与原问题性质相同，但 规模较小的问题。只有具备了这两个要素，递归函数才能在有限次计算后得出结果。

递归设计：自顶向下、逐步分解的策略

解决递归问题的策略是把一个规模比较大的 问题分解为一个或若干规模比较小的问题， 子问题应与原问题做同样的事情，且更为简 单；分别对这些比较小的问题求解，再综合 它们的结果，从而得到原问题的解。

以下三种情况常常用到递归方法

 定义是递归的

 数据结构是递归的

 问题的解法是递归的

//含一个递归调用的递归过程的一般形式 
void  p(参数1) 
{    if(数据为递归出口)                    
操作;        
else{                  
操作;                 
p(参数2);                 
操作;         
} 
}

递归过程改为非递归过程

递归过程简洁、易编、易懂。但递归过程效率低，重复计算多，改为非递 归过程的目的是提高效率 。

 单向递归或尾递归可直接用迭代实现其非递归 过程（尾递归是单项递归的特例）

 其他情形必须借助栈实现非递归过程

//用迭代法实现单向递归 
//斐波那契数列就是单向递归 
long FibIter(long n) {      
if (n <= 1) return n;      
long twoback = 0,  oneback = 1,  current;      
for (int i = 2; i <= n; i++) {          
current = twoback + oneback;          
twoback = oneback;             
oneback = current;   
}   
return current; 
}

//用迭代法实现尾递归 
//递归调用语句只有一句且在函数尾部
void recfunc(int A[ ],  int n) {      
if (n >= 0) {           
cout << A[n] << “  ”;           
n--;           
recfunc(A, n);     
 } 
} 

void sterfunc(int A[ ], int n) { 
//消除了尾递归的非递归函数     
while (n >= 0) {          
cout << "value " << A[n] << endl;          
n--;     
    } 
}

递归与回溯

回溯法也常称为试探法。这种方法将问题的 候选解按某种顺序逐一检验，当发现当前解 不可能是解时，可以沿搜索路径回退到前一 结点，沿另一分支继续搜索,直到搜索到问题 的解，或搜完全部分支没有解存在为止。

回溯法常使用递归进行试探，或使用栈帮助向前试探。

迷宫问题

迷宫是一个矩形区域，有一个入口和一个出口，其内 部设置了许多不能穿越的墙壁，对从入口到出口的前 进道路上形成了许多障碍.若能正确的绕过障碍，则从入口到出口存在一条穿越 迷宫的路线。

前进方向：北、东北、东、东南 南、西南、西、西北 .
走步规则：首先从东开始，按照 顺时针方向搜索下一步可 能前进的位置 .

数据结构设计
1 用二维数组Maze[m+2][p+2]表示迷宫

 若元素Maze[i][j]==1,表示该位置上是障碍。

 若元素Maze[i][j]==0,表示该位置上是通路。

2 用二维数组mark[m+2][p+2]标志已走过 的路途，防止走老路。

 初始化时，所有元素都是没走过的，设为0。

 当行进到迷宫的某个位置[i][j]时，就将对应的 mark[i][j]置为1；

 当前点的下一个试探位置 从当前位置Maze[i][j]出发，可能的前进方向有8个，用一 维数组move[8]表示。其数组元素为结构类型数据:

struct offsets {     
int a, b;        //a,b是横,纵方向的偏移量    
char *dir } 

offsets move[8]={
{-1,0,"N"},{-1,1,"NE"}, {0,1,"E"}, { 1,1,"SE"}, {1,0,"S"},{1,-1,"SW" 
{0,-1,"W"},{-1,1,"NW"}
}

//解决迷宫问题的递归算法 
int SeekPath(int x,int y)
{      
int i,g,h; char *d;   //d,h记录位置信息，d记录方向      
if(x==m && y==n)  return 1;           
for(i=0;i<8;i++)
 {           
   g=x+move[i].a;   h=y+move[i].b;     d=move[i].dir; 
   if(Maze[g][h]==0&&mark[g][h]==0)  
   {                
        mark[g][h]=1;            
        if(SeekPath(g,  h))
        {              
          cout<<“(“<<g<<“,”<<h<<“),”<<“direction”<<move[i].dir<< “,”;       
          return 1;   
        }
   }         
 }//回溯，换方向再试      
if(x==1&&y==1) cout<<“no path in Maze”<<endl;      
Return 0; 
}

n皇后问题

在 n 行 n 列的国际象棋棋盘上，若两个皇后位于 同一行、同一列、同一对角线上，则称为它们为 互相攻击。n 皇后问题是指找到这 n 个皇后的互 不攻击的布局。

8皇后问题：在8X8格的国际象棋上摆放八个皇后，使 其不能互相攻击，即任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法？

解题思路

安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 )

在第 j 列安放一个皇后： 如果在列、对角线方向有其它皇后，则 出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇 后不动，递归安放第 i+1行皇后。

设置数组 col [n] ：col[i] 标识第 i 列是否安放了皇后

void Queen(int i) {     
if (i>n) 输出棋盘布局；     
else     
for (int j = 1;  j <= n;  j++) {          
 if (第 i 行第 j 列没有攻击) {              
 在第 i 行第 j 列安放皇后；               
 Queen(i+1);             
   }         
  }      
} 

//算法求精 
void queen(int k)    {  
if(k>n) {sum++ ;               
//在这里打印出来 ；              
cout<<"the solution of "<<sum <<endl;              
for(int i=1;i<=n;i++)             
{for(int j=1;j<=n;j++)            
if (x[i]==j) cout<<"* " ;               
else cout<<"0 ";                 
cout<<endl ;    }             
cout<<endl;    
} else  
for(int j=1;j<=n;j++)  
{   x[k]=j;      
if(place(k))    
queen(k+1);   }} 
place(int t)  
//检查 第 t个皇后在第T行的当前位置上是否满足约束条件 
{  
for(int i=1;i<t;i++)    
if((x[i]==x[t])|| (abs(i-t)==abs(x[i]-x[t])) ) return false ;  
return true; 
} 
Int sum=0; 
int main() 
{ 
int n; 
cout<<"请输入皇后的数目"<<endl; 
cin>>n; 
int *x=new int[n+1] ; //记录每行的皇后放在哪一列  
for(int i=0;i<=total;i++) x[i]=0; 
queen(1) ; 
cout<<"the result of nqueen is :"<<sum<<endl; 
delete [] x ; 
return 0; 
}

队列

队列是只允许在一端删除，在另一端插入 的线性表

允许删除的一端叫做队头(front)，允许插 入的一端叫做队尾(rear)。

特性：先进先出(FIFO, First In First Out)

//队列的抽象数据类型 
template <class E> 
class Queue { 
public:      
Queue() { };       //构造函数      
～Queue() { };       //析构函数      
virtual bool EnQueue(const E& x) = 0;  //进队列      
virtual bool DeQueue(E& x) = 0;       //出队列      
virtual bool getFront(E& x) = 0;       //取队头        
virtual bool IsEmpty() const = 0;       //判队列空      
virtual bool IsFull() const = 0;       //判队列满 }; 

//队列的数组存储表示 
template <class E> class SeqQueue : public Queue<E> {    //队列类定义 protected:      
int rear, front;         //队尾与队头指针      
E *elements;         //队列存放数组      
int maxSize;         //队列最大容量 
……. 
// 函数 
}；

队列的进队和出队原则

 进队时先将新元素按 rear 指示位置加入， 再将队尾指针加一 rear = rear + 1。

 队尾指针指示实际队尾的后一位置。

 出队时按队头指针指示位置取出元素，再将 队头指针进一 front = front + 1，

 队头指针指示实际队头位置。

 队满时再进队将溢出出错（假溢出） ；

 解决假溢出的办法之一：将队列元素存放数 组首尾相接，形成循环（环形）队列。

循环队列

 队列存放数组被当作首尾相接的表处理。

 为了防止队头、队尾指针加1产生假溢出，可用语言 的取模(余数)运算实现。

 队列初始化：front = rear = 0;  队头指针进1: front = (front+1) % maxSize;

 队尾指针进1: rear = (rear+1) % maxSize;

 队空条件：front == rear;

 队满条件：(rear+1) % maxSize == front （看示例）

通过牺牲一个存储空间来实现（课本上的方案）

//队列的数组存储表示----循环队列 
template <class E> class SeqQueue : public Queue<E> {    //队列类定义 protected:      
int rear, front;         //队尾与队头指针      
E *elements;         //队列存放数组      
int maxSize;         //队列最大容量 
public:      
SeqQueue(int sz = 10);    //构造函数 
～SeqQueue() { delete[ ] elements; }  //析构函数      
bool EnQueue(const E &x);         //新元素进队列      
bool DeQueue(E& x);      //退出队头元素      
bool getFront(E& x);       //取队头元素值      
void makeEmpty() { front = rear = 0; }        
bool IsEmpty() const { return front == rear; }       
bool IsFull() const           
{ return ((rear+1)% maxSize == front); }       
int getSize() const           
{ return (rear-front+maxSize) % maxSize; }  
}; 

//循环队列操作的定义 
template <class E> 
SeqQueue<E>::SeqQueue(int sz): front(0), rear(0), maxSize(sz) { //构造函数   
elements = new E[maxSize];         
assert ( elements != NULL ); 
}; 
template <class E> 
bool SeqQueue<E>::EnQueue(const E& x) {
//若队列不满, 则将x插入到该队列队尾, 否则返回      
if (IsFull() == true) return false;         
elements[rear] = x;                    //先存入      
rear = (rear+1) % maxSize;       //尾指针加一      
return true;    
};  
template <class E> 
bool SeqQueue<E>::DeQueue(E& x) {  
//若队列不空则函数退队头元素并返回其值      
if (IsEmpty() == true) return false;
x = elements[front];                  //先取队头      
front = (front+1) % maxSize;   //再队头指针加一      
return true; 
}; 
template <class E> 
bool SeqQueue<E>::getFront(E& x) const { //若队列不空则函数返回该队列队头元素的
if (IsEmpty() == true) return false;    //队列空   
x = elements[front];      //返回队头元素   
return true; 
};

链式队列

 队头在链头，队尾在链尾。

 链式队列在进队时无队满问题，但有队空问 题。

 队空条件为 front == NULL

//队列的链接存储表示 — 链式队列 
//链式队列类的定义 
template <class E> struct LinkNode {                   //队列结点类定义  private:      
E data;             //队列结点数据     
LinkNode<E> *link;          //结点链指针 
public:     
LinkNode(const E& d , LinkNode<E>*  next =null) : data(d), link(next) { } 
};   
template <class E> 
class LinkedQueue {  
private:       
LinkNode<E> *front, *rear;   //队头、队尾指针 
public:      
LinkedQueue() : rear(NULL), front(NULL) { }     
~LinkedQueue(MakeEmpty());        
bool EnQueue(const E& x);     
bool DeQueue(E& x);        
bool GetFront(E& x);        
void MakeEmpty();                 
bool IsEmpty() const { return front == NULL; } 
}; 
template <class E> 
void LinkedQueue<E>::makeEmpty() {      //析构函数     
LinkNode<E> *p;     
while (front != NULL) {              //逐个结点释放         
p = front;  
front = front->link;  
delete p;     } 
};  
template <class E>  
bool LinkedQueue<E>::EnQueue(const E& x) { //将新元素x插入到队列的队尾 
// 分空表和非空表两种情况。 
if (front == NULL)  {              //创建第一个结点        
front = rear = new LinkNode<E> (x);           
if (front == NULL) return false; } //分配失败       
else {                                      //队列不空, 插入           
rear->link = new LinkNode<E> (x);           
if (rear->link == NULL) return false;           
rear = rear->link;      }      
return true; 
}; 
template <class E> //如果队列不空，将队头结点从链式队列中删去 
bool LinkedQueue<E>::DeQueue(E& x) {      
if (IsEmpty() == true) return false;        //判队空      
LinkNode<E> *p = front;        
x = front->data;  
front = front->link;         
delete p;   
return true;     
}; 
template <class E>  
bool LinkedQueue<E>::GetFront(E& x) { //若队列不空，则函数返回队头元素的值      
if (IsEmpty() == true) return false;       
x = front->data;  
return true; 
};

队列的应用：打印杨辉三角形

算法逐行打印二项展开式 (a + b)i 的系数

每行的第i个元素，等于上一行的第i个元素和 它的前驱项相加的结果

//利用队列打印二项展开式系数的算法 
#include <stdio.h> 
#include <iostream.h> 
#include "queue.h" 
void YANGHVI(int n) {      
 Queue q(n+2);                     //队列初始化      
 q.MakeEmpty();      
 q.EnQueue(1);  q.EnQueue(1); 
 int s = 0, t;  
 for (int i = 1; i <= n; i++) {            //逐行计算           
 cout << endl;                
 q.EnQueue(0); //各行间插入一个0               
 for (int j = 1; j <= i+2; j++)        
 {//处理第i行的i+2(包括0)个系数。               
  q.DeQueue(t);              
  q.EnQueue(s + t);                 
  s = t;               
  if (j != i+2) cout << s << ' ';            
     }      
 }}

优先级队列

每次从队列中取出的是具 有最高优先权的元素

//优先级队列的类定义 
#include <assert.h> 
#include <iostream.h> 
#include <stdlib.h> 
template <class E> 
class PQueue { private:     
E *pqelements;        //存放数组     
int count;                  //队列元素计数     
int maxPQSize;                //最大元素个数     
void adjust();                  //调整 
public:      
PQueue(int sz = 50);     
~PQueue() { delete [ ] pqelements; }     
bool Insert(E x);     
bool RemoveMin(E& x);      
bool GetFront(E& x);      
void MakeEmpty() { count = 0; }     
bool IsEmpty() const { return count == 0; }     
bool IsFull() const             
{ return count == maxPQSize; }      
int Length() const { return count; } 
}; 

//优先级队列部分成员函数的实现 
template <class E>  PQueue<E>::PQueue(int sz) {       
maxPQSize = sz;  count = 0;       
pqelements = new E[maxPQSize];       
assert (pqelements != NULL);  } 
template <class E>  
bool PQueue<E>::Insert(E x) {      
if (IsFull() == true) return false;   //判队满断言      
pqelements[count++] = x;              //插入 
adjust();   
return true; 
} 
template <class E>  
void PQueue<E>::adjust() {      
E temp = pqelements[count-1];      //将最后元素暂存再从后向前找插入位置      
for (int j = count-2;  j >= 0;  j--)          
if (pqelements[j] <= temp) break;           
else pqelements[j+1] = pqelements[j];      
pqelements[j+1] = temp; 
} 
template <class E>  
bool PQueue<E>::RemoveMin(E& x) {      
if (IsEmpty()) return false;     
x = pqelements[0];       //取出0号元素      
for (int i = 1; i < count; i++)          
pqelements[i-1] = pqelements[i];           //从后向前逐个移动元素填补空位      
    count--;      
return true; }  
template <class E> bool PQueue<E>::GetFront (E& x) {      
if (IsEmpty() == true) return false;      
x = pqelements[0];        
return true; 
}