第三章 栈和队列

3.1 栈
一.栈的定义:  栈是限定在一端进行插入、删除操作的线性表
二.栈的特点:  后进先出
三.栈的基本运算
1.        push(&s,e);2.pop(&s,&e);3.gettop(s,&e);4.stackempty(s);
5.initstack(&s);
四.存储结构
typedef struct{
selemtype  *base;  //栈底指针
selemtyoe  *top; //栈项指针
int stacksize;   //栈的最大容量
} sqstack;
五.栈空、栈满条件  栈空.top==s.base
       栈满.top-s.base=＝stacksize
六.基本运算的实现
(1) status push(sqstack &s,selemtype e){
   if (s.top - s.base == stacksize) 栈满，追加存储空间;
   *s.top++=e;//入栈,栈顶指针＋1
   return (ok);
   }
(2) status pop(sqstack &s,selemtype &e){
    if (s.top==s.base) return error;
    s.top--; e = *s.top; //出栈  return (ok);
   };
(4) status stackempty(sqstack s){
   //判栈空否？空:返回true;否则:返回false
    if (s.top==s.base) return(true);
    else  return(false);
   }
(5) status initstack(sqstack &s){ //构造一个空栈
s.base=(selemtype)malloc(stack_init_size*sizeof(elemtype));
   if (!s.base) exit(overflow); //分配失败
   s.top=.s.base;  s.stack=stack_init_size;    
   return(ok);
}
【例一】        车厢调度问题。n节车厢，‘S’—软座，‘H’—硬座。将软座排在硬座这前。
for (j=1;j<=n;j++)
  { cin>>ch;
  if (ch==’H’) push(s,ch); // ‘H’硬座车厢进栈
  else cout<<ch;
}
while (!stackempty(s))
  { pop(s,ch); cout<<ch; }
3.2 栈的应用举例
一、        括号匹配
二、        行编辑  
三、        表达式求值
  1.表达式的表示 前缀 *3-72； 中缀 3*(7-2)；后缀 372-*；
  2.表达式求值＊（以后缀为例）
  initstack(S)；
  while ((w=getchar())!=’#’){
   if (w!=运算符 ) push(s,w) // 操作数进栈
   else { pop(s,a); pop(s,b); push(s,operate(b,w,a));}
   //计算结果入栈
  }

3.3 栈与递归过程
3.3.1 递归过程及实现
一.        什么是递归—自己调用自己
二.        递归函数设计
例1 求n!
posint fact(nonegist n){ //求n!
  if (n==0) f=1;  
else f=n*fact(n-1);
return(f);
}// fact
例2 hanio问题
void hanoi(int n,char x,y,z){
//将X上的n个圆盘移到塔座Z上,Y可用作辅助塔座
  if (n==1) move(x,1,z); //将编号为1的圆盘从X移到Z
  else { hanoi(n-1,x,z,y);
   move(x,n,z);
   hanoi(n-1,y,x,z);
   }  
} //hanoi
三.        递归的条件
（1）终止性 （2）收敛性
四.递归过程与栈
五.非递归程序设计
posint fact(nonegist n){ //求n!
top=1; s[top]=n;
while (s[top]>1)
{ top++;  s[top]=s[top-1]-1; }
f=1;
while (top>=1)  { f=f*s[top]; top--; }
return(f);
} //fact
3.4 队列
一.队列的定义
队列是限定在一端进行插入、另一端删除操作的线性表
二.队列的特点:先进先出
三.队列的基本运算
1.        enqueue(&Q,e); .delqueue(&Q,&e);3.gethead(Q,&e);4.queueempty(Q);
5.iniqueue(Q)
四.队列的存储结构
  1.循环队列
(1)        循环队列的优点
(2)        循环队列的表示
  #define MAXQSIZE 100  //队列的最大容量
  typedef struct{
qelemtype  *base;  //初始化；动态分配存储空间
int  front,rear; //队列首、尾指针(分别指向头和尾＋1处)
  } sqqueue;
(3) 队列空、栈满条件: 空: Q.front=Q.rear
        满: (Q.rear+1) % MAXQSIZE =Q.front
(4) 基本运算的实现
入队
if ( (Q.rear+1) % m ==Q.front)  return error;
else { Q.base[Q.rear]=e;  Q.rear=(Q.rear+1) % MAXQSIZE; }
出队:
if ( Q.front==Q.rear )  return error;
else { e= Q.base[q.front] ; Q.front:=(Q.front+1) % MAXQSIZE; }
  2.链式队列
  入队:  p=(queueptr )mallocsizeof(Qnode);
   p->data=x;
   p->next=Q.rear^.next;
   Q.rear->next=p;
  出队: if (Q.rear==Q.front) return error;
   else { p=Q.front->next;
      Q.front->next=p->next;
      If ( p==Q.rear)  Q.rear=Q.front;    
      e=p-.data;
    }