数据结构与算法：栈的原理及操作实例--进制转换、括号匹配、递归的消除

顺序栈

顺序栈的类型描述：

利用顺序存储方式实现的栈称为顺序栈。 继承顺序表的特点，仍然用动态分配的一维数组来描述其顺序存储结构。

#define STACK_INIT_SIZE 100   //存储空间的初始分配量
#define STACKINCREMENT 10   //存储空间分配增量
typedef int ElemType;   //简化操作，让类型在此定义为int型 
typedef struct{
  ElemType *date;
  int top; //栈顶指针
  int stacksize; 
}SqStack;      

通常将数组的0下标作为栈底，这样空栈时栈顶指针指向数组第一个元素。

——>为什么只设一个指针？

——指针是单方向操作结构，只需定义“栈顶指针”即可。

栈的初始化：

int InitStack(SqStack &s){      //这里为什么要加“&”（取地址符）——>这里实际上操作的是栈地址，或者说栈空间，又或说：栈（顶）元素
  s.date=new ElemType[STACK_INIT_SIZE];
  if(!s.date) exit(overflow);   //存储分配失败
  s.top=-1;   //栈空
  s.stacksize=STACK_INIT_SIZE;
  return OK;
}      

——>栈中，好像挺喜欢用“s.top=-1”来表示栈（s）为空。

进栈操作：

int Push(SqStack &s,ElemType e){   //将e插入栈顶 
  ElemType *p;
  if(s.top>=s.stacksize-1){
    p=(ElemType *)realloc(s.date,(s.stacksize+STACKINCREMENT)*sizeof(ElemType));   //此时，应开辟空间，开辟一个符合栈类型（ElemType）的空间
    if(!p) exit(overflow);   //存储分配失败
    s.date=p;
    s.stacksize=s.stacksize+STACKINCREMENT; 
  }
  s.date[++s.top]=e;
  return OK;
}      

“s.top”:“头”处插入数据。前面说过，栈只能单方向操作!我们称被操作的方向为：栈顶。

出栈操作:

int Pop(SqStack &s,ElemType &e){   //若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回error 
  if(s.top==-1) return error;
  e=s.date[s.top--];
  return OK;
}      

判断栈是否为空栈：

int StackEmpty(SqStack s){
  if(s.top==-1) return OK;
  return error;
}       

——>需注意的是：对于顺序栈，入栈时首先应判断栈是否满了（条件：S.top>=S.stacksize-1），防止空间溢出 <-- 解决：追加存储空间 -->

这就好比链式操作·出栈时要先判断栈是否为空一样。

链栈

typedef struct node{
  ElemType data;
  struct node *next;
}StackNode,*LinkStack;   //*LinkStack是什么？学过c/c++的都知道，这不过是栈指针罢了，有了它，下面设置关于栈的指针时就会轻松许多
LinkStack top;   //明目张胆的设置栈顶指针top       

基本操作：

其主要运算仍是对于栈顶执行插入、删除之类的操作。

void InitStack(LinkStack &top){   //置空栈
  top=NULL;   //构建一个空栈，栈顶指针为top 
}

int StackEmpty(LinkStack top){   //判断栈是否为空
  if(top==NULL) return OK;
  else return error; 
}

int Push(LinkStack &top,ElemType x){   //入栈
  StackNode *s;
  s=new StackNode;   //new一个新空间，并让指针指向它。同顺序栈中的这一步：p=(ElemType *)realloc(s.date                            //(s.stacksize+STACKINCREMENT)*sizeof(ElemType));
  if(!s) exit(overflow);
  s->data=x;
  s->next=top;
  top=s;
  return OK; 
}

int Pop(LinkStack &top,ElemType &x){   //出栈
  StackNode *p;
  if(top==NULL) return error;
  else{
    x=top->data;
    p=top;
    top=top->next;
    delete p;
    return OK;
  }
}      

应用实例-操作

1.进制转换（十->?）

原理：由十进制转换为其它进制时，其打印输出（从高位->低位）与计算过程恰好相反。

实现：将计算得到的八进制数的各位按顺序入栈，然后按出栈顺序打印即可（最简单、从输出过程控制）。

（算法思想：（结合上面两种之任一））

void conversion(){
  SqStack s;
  int N,e;
  InitStack(s);
  scanf("%d",&N);   //输入十进制数
  while(N){
    Push(s,N%8);
    N=N/8;   
  }
  while(!StackEmpty(s)){   //调用函数判断栈空与否
    Pop(s,e);   //条件都满足下 出栈
    printf("%d",e);
  }
}      

2.汉诺塔的递归实现

曾经看过汉诺塔的实现过程，我去，真是。。。看了都不想学了那种感觉。今天既然说栈，咱就好好唠唠这个“栈”。

在高级语言编写的程序中，为了追求效率，调用函数与被调用函数之间的联结和信息交换（如：参数传递）都是通过栈来进行的。

下面，探究下“递归”世界下的“汉诺塔”：

void hannuo(int n,char x,char y,char z){   //将x塔上按直径大小从上到下编号为1-n的圆盘从x移到z，y可做辅助塔 
  if(n==1)
    move(x,1,z);   //将编号为1的圆盘从x移到z
  else{
    hannuo(n-1,x,z,y);   //将x编号上为1至n-1的圆盘移到y，z做辅助塔
    move(x,n,z);   //将编号为n的圆盘从x移到z
    hannuo(n-1,y,x,z);   //将y编号上为1至n-1的圆盘移到z，x做辅助塔
  } 
}

void move(char x,int n,char z){
  printf("%d号圆盘：%c-- -->%c\n",n,x,z);
}      

（留意下5、6、7三行）

but，递归真的好吗？

递归的消除

原因：递归虽然代码量小，重构性大，但其在时空上的性能未必是最好的。递归的消除有两种：1.简单递归消除（尾递归和单向递归消除） 2.基于栈。

if(n==1||n==0) return n;
else{
  int x=0,y=1,m;
  for(int i=2;i<=n;i++){
    m=y;
    y=x+y;
    x=m;
  }
}