>栈和队列的定义和特点

栈和队列是限定插入和删除只能在表的端点进行的线性表。（栈和队列是线性表的子集）

栈----后进先出

 数制转换，表达式求值，括号匹配的检验，八皇后问题，行编辑程序，函数调用，迷宫求解，递归调用的实现

 线性表   Insert(L,i,x)          Delete(L,i)

 栈          Insert(S,n+1,x)    Delete(S,n)

 队列      Insert(S,n)           Delete(Q,1)

队列----先进先出

  栈的定义和特点

 栈（stack）是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除的线性表。

 又称为后进先出（Last In First Out）的线性表,简称LIFO结构。

 栈是仅在表尾进行插入、删除的线性表。

 表尾（即an端）称为栈顶Top;表头（即a1端）称为栈底Base。

 插入元素到栈顶（即表尾）的操作，称为入栈。“入”=压入=PUSH(x)

 从栈顶（即表尾）删除最后一个元素的操作，称为出栈。“出”=弹出=POP(y)

  队列的定义和特点

 队列（queue）是一种先进先出（First In First Out--FIFO）的线性表。在表一端插入（表尾），在另一端删除（表头）。

插入元素称为入队，删除元素称为出队；队列的存储结构为链队或顺序队（常用循环顺序队）

  栈与一般线性表的区别：仅在于运算规则不同

一般线性表：  逻辑结构：一对一    存储结构：顺序表、链表    运算规则：随机存取

栈：                逻辑结构：一对一     存储结构：顺序表、链栈    运算规则：后进先出（LIFO）

>栈的表示和操作的实现

InitStack(&S）        初始化操作                                ClearStack(&S)   栈置顶操作

DestroyStack(&S)  销毁栈操作                                 Push(&S,e)         入栈操作

StackEmpty(S)      判定S是否为空栈                        Pop(&S,&e)        出栈操作

StackLength(S)     求栈的长度                                  GetTop(S,&e)        取栈顶操作

栈的顺序存储----顺序栈

        空栈： top==base是栈空的标志              栈满：top-base==stacksize

        使用数组作为顺序栈的存储方式的特点：简单、方便、但易溢出（数组大小固定）

        上溢：栈已满，又要压入元素  

        下溢：栈已空，还要弹出元素（注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束）

顺序栈的表示

顺序栈的初始化

栈的链式存储----链栈

        链栈的表示

        链栈是运算受限的单链表，只能在链表头部进行操作。

        链表的头指针就是栈顶，不需要头结点，基本不存在栈满的情况，空栈相当于头指针指向空。插入和删除仅在栈顶处执行。

                                                        判断链栈是否为空

                                                                     链栈的入栈

链栈的出栈

>队列的表示和操作的实现

  队列的相关概念

    定义  只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）

    逻辑结构 与线性表相同，仍为一对一关系

    存储结构 顺序队或链队，以循环顺序队列更常见。

    运算规则 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。

    实现方式 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。

    队头(Front)  队尾（Rear）

  队列的常见应用

脱机打印输出：按申请的先后顺序依次输出

多用户系统中，多个用户排成队，分时地循环使用CPU和主存

按用户的优先级排成多个队列，每个优先级一个队列

实时控制系统中，按到达的时间先后顺序依次进行

  队列的抽象类型定义

ADT Queue{

  队列的顺序表示和实现

队列的物理存储也可以用顺序存储结构，也可以用链式存储结构。相应地，队列的存出方式也分为两种，即顺序存储和链式存储。

队列的顺序表示----用一维数组base[MAXQSIZE]

解决假上溢的方法：

1.将队中元素依次向队头移动。缺点：浪费时间，每移动一次，队中元素都要移动。

2.将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始端空着，又可以从头使用空着的空间。当front为maxqsize时，也是一样。

解决假上溢的方法----引入循环列表

base[0]接在base[MAXQSIZE-1]之后，若rear+1==M,则令rear=0; 实现方法：利用模（mod,c语言中：%）运算。

插入元素：Q.base[Q.rear]=x;   Q.rear=(Q.rear+1)%MAXQSIZE;

删除元素：x=Q.base[s.front]        Q.front={Q.front+1}%MAXQSIZE

循环队列解决队满时判断方法----少用一个元素空间：

循环队列的初始化----队列的初始化：

循环队列的操作----求队列的长度

 循环队列的操作----循环队列入队

循环队列的操作----循环队列出队

循环队列的操作----取队头元素

 队列的链式表示和实现

若用户无法估计所用队列的长度

链队列的操作----链队列初始化 

链队列的操作----销毁链队列

链队列的操作----将元素e入队

链队列的操作----链队列出队

链队列的操作----求链队列的队头元素

 >栈与递归

递归的定义

若一个对象部分地包含它自己，或者用它自己给自己定义，则称这个对象是递归的。

若一个过程直接或间接地调用自己，则称这个过程是递归的过程。

例如：递归n求n的阶乘 long Fact(long n){

                                          if(n==0) return 1;

                                          else return n*Fact(n-1);

                                      }

以下三种情况常常会用到递归：递归定义的数学函数

 

                                                  具有递归特性的数据结构

                                                  可递归求解的问题

函数调用过程 

调用前，系统完成：

（1）将实参，返回地址等传递给被调用函数

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

（3）将控制转移到被调用函数的入口

调用后，系统完成：

（1）保存被调用函数的计算结果

（2）释放被调用函数的数据区

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

递归函数调用的实现

“层次”   主函数           0层

             第一次调用   1层

               ..............

             第i次调用      i层 

“递归工作站”----递归程序运行期间使用的数据存储区

“工作记录”-------实在参数，局部变量，返回地址

递归的优缺点

优点：结构清晰，程序易读

缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。

递归-->非递归

方法一：尾递归、单向递归-->循环结构

方法二：自用栈模拟系统的运行时栈

>案例

数值的转换（算法3.20）

时间和空间复杂度都为O(log₈n)

void conversion(int N)

{//对于任意一个非负十进制整数，打印输出与其等值的八进制整数

        InitStack(S);//初始化空栈

        while(N)       //当N非零时循环

        {

                Push(S,N%8);//把N与8求余得到的八进制整数压入栈

                N=N/8;           //N更新为N与8的商

        }

        while(!StackEmpty(S))//当栈S非空时，循环

        {

                Pop(S,e);//弹出栈顶元素e

                cout<<e;//输出e

        }

}

括号的匹配（算法3.21）

时间和空间复杂度都为O(n)

Status Matching()

{//检查表达式中所含括号是否正确匹配，如果匹配，则返回true,否则返回false

//表达式中以＃结束

        InitStack(S);//初始化空栈

        flag==1;//标记匹配结果以控制循环及返回结果

        cin>>ch;//读入第一个字符

        while(ch!='＃'&&flag)//假设表达式以＃结尾
        {

                switch(ch)

                {

                        case '[':                                //若是左括号，则将其压入栈

                        case '(':

                                Push(S,ch);

                                break;

                        case ')':                                //如果是右括号，则根据当前栈顶元素的值分情况考虑

                                if(!StackEmpty(S)&&GetTop(S)=='(')

                                        Pop(S,x);               //若栈非空且栈顶元素是（，则正确匹配

                                else

                                {

                                        flag=0;                //若栈空且栈顶元素不是（，则匹配失败

                                        break;

                                }  

                          case ']':                                //如果是右括号，则根据当前栈顶元素的值分情况考虑

                                if(!StackEmpty(S)&&GetTop(S)=='(')

                                        Pop(S,x);               //若栈非空且栈顶元素是[，则正确匹配

                                else

                                {

                                        flag=0;                //若栈空且栈顶元素不是[，则匹配失败

                                        break;

                               }

              }

                cin>>ch;//继续读入下一个字符

        }

        if(StackEmoty(S)&&flag)   return true;//匹配成功

        else  return false;//匹配失败

}

表达式求值（算法3.22）

时间和空间复杂度都为O(n)

char EvaluateExpresion()

{//算术表达式求值的算符优先算法，设OPTR(寄存运算符，运算符栈）和OPND(寄存操作数和运算结果，操作符栈）

        InitStack(OPND);//初始化OPND栈

        InitStack(OPTR);//初始化OPTR栈

        Push(OPER,'＃');//将表达式起始符＃压入OPTR栈

        cin>>ch;

        while(ch!='＃'||GetTop(OPTR)!='＃')

        {

                if(!In(ch))   {Push(OPTR,ch);cin>>ch;//ch不是运算符则进OPND栈

                else 

                        switch(Precede(GetTop((OPTR),ch))//比较OPTR的栈顶元素和ch的优先级

                        {

                                case '<':

                                        Push(OPTR,ch);cin>>ch;//当前字符ch压入OPTR,读取下一字符ch

                                        break;

                                case '>':

                                        Pop(OPTR,theta);//弹出OPTR栈顶的运算符

                                        Pop(OPND,b);Pop(OPND,a);//弹出OPND栈顶的两个运算符

                                        Push(OPND,operate(a,theta,b);//将运算结果压入OPND栈

                                         break;

                                case '=':                                        //OPTR的栈顶元素是“（”且ch是“）”

                                        Pop(OPTR,x);cin>>ch;

                                        break;

                        }//switch;

                }//while

        return GetTop(OPND);//OPND栈顶元素即为表达式求值结果

        }

伴舞问题   （算法2.23）

时间和空间复杂度都为O(n)

void DancePartner(Person dancer[],int  num)

{//结构数组dancer中存放跳舞的男女，num是跳舞的人数

        InitQueue(Mdancers);//初始化男士队列

        InitQueue(Fdancers);//初始化女士队列

        for(i=0;i<num;i++)
        {

                p=dancer[i];

                if(p.sex=='F')  Enqueue(Fdancers,p);//插入女队

                else  Enqueue(Mdancers,p);               //插入男队

        }

        cout<<"The dancering parnters are:\n";

        while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers))

        {

                Dequeue(Fdancers,p);//女士出队

                cout<<p.name<<" ";//输出出队女士的姓名

                Dequeue(Mdancers,p);//男士出队

                cout<<p.name<<" ";//输出出队男士的姓名

        }

        if(!QueueEmpty(Fdancers))//女士队列非空，输出队头女士的姓名

        {

                p=GetHead(Fdancers);//取女士队头

                cout<<"The first woman to get a parnter is:"<<p.name<<end1;

        }

        else if(!QueueEmpty(Mdancers))//男士队列非空，输出队头男士的姓名

        {

                p=GetHead(Mdancers);//取男士队头

                cout<<"The first man to get a parnter is:"<<p.name<<end1;

        }

}