資料結構與算法：棧的原理及操作執行個體--進制轉換、括号比對、遞歸的消除

順序棧

順序棧的類型描述：

利用順序存儲方式實作的棧稱為順序棧。 繼承順序表的特點，仍然用動态配置設定的一維數組來描述其順序存儲結構。

#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;
  }
}