一起talk C栗子吧（第十六回：C語言實例--棧一）

各位看官們，大家好，從今天開始，我們講大型章回體科技小說 ：C栗子，也就是C語言實例。閑話休提， 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧！

看官們，上一回中咱們說的是雙向鏈表的例子，這一回咱們說的例子是：棧。

什么是棧？我們聽過龍門客棧，你這個是哪家客棧？我還沒有說，臺下已經(jīng)有客官在問了。看官們，棧是 類似我們在前面幾回中說過的鏈表，它也是用來存放數(shù)據(jù)的一種抽象的數(shù)據(jù)結(jié)構(gòu)。因為比較抽象，咱們還 是舉個現(xiàn)實生活中的例子來說明吧。我們出去旅游時通常拿一個行李箱存放自己的物品，比如衣服，鞋子 電腦，相機等。出發(fā)前，我們會把這些東西依次放到行李箱中，首先會把不容易壓壞的物品放到箱底，比 如衣服。然后把容易壓壞的物品放到上面，比如電腦和相機。當(dāng)我們到達目的地時，會取出行李箱中的物 品。首先拿出放在箱子上面的電腦和相機，最后拿出放在箱子底部的衣服。大家看看，拿出物品的順序和 存放物品的順序正好相反。最后放進去的電腦和相機等易壓碎的物品最先拿出來，最先放進去的衣服等不 易壓碎的物品最后拿出來。這個行李箱就好比一個存放數(shù)據(jù)的棧，箱子里面的物品好比數(shù)據(jù)，從箱子里拿 物品好比操作數(shù)據(jù)，拿物品要先拿最后存放的物品，操作數(shù)據(jù)也要先操作最后放到棧中的數(shù)據(jù)。就是說最 先存放到棧中的數(shù)據(jù)最后被拿出。這便是棧的特點：先進后出。

看官們，和鏈表一樣，棧也有兩種實現(xiàn)方式：順序存放和鏈?zhǔn)酱娣?。我們會分別舉例子說明。棧有兩個基 本的操作：出棧和入棧。入棧就是把數(shù)據(jù)存放到棧中，出棧就是把數(shù)據(jù)從棧中拿出來。入棧和出棧這兩個 操作要符合?！跋冗M后出”的特點。

看官們，詳細的代碼如下，大家可以參考。關(guān)于代碼中有一些需要注意的地方和大家說一下：

• 1.棧的順序存儲是通過一個全局數(shù)組實現(xiàn)的，棧的大小就也就是數(shù)組的長度，可以自己定義。
• 2.入棧時要確認棧是否已經(jīng)満了，不然會有溢出。我在代碼中多放了一個空間可以避免溢出。
• 3.出棧時要確認棧是否已經(jīng)空了，不然會有溢出。我在代碼中通過多放了一個變量size可以避免溢出。

     1  /* **************************
     2   * Head file of Stack
     3   * *************************/
     4  #ifndef STACK_H
     5  #define STACK_H
     6  
     7  #include<stdio.h>
     8  #include<stdlib.h>
     9  
    10  #define SUCCESS 0
    11  #define FAILE 1
    12  
    13  #define LEN 5 //棧的長度先定義為5,需要時可自行修改
    14  
    15  typedef int StackElmt; //把int當(dāng)作棧中元素的類型，實際中可以使用其它的類型或者自己定義一個List類型
    16  typedef struct _Stack{
    17      StackElmt *base;
    18      StackElmt *top;
    19      int size;
    20  }Stack;
    21  
    22  StackElmt STACK[LEN+1] = {0}; //順序存儲方式的棧,防止數(shù)組越界，最后一個位置不放元素
    23  
    24  //聲明函數(shù)原型，這里有入棧和出棧操的函數(shù)
    25  int StackInit(Stack *s);
    26  int StackPrint(Stack *s);
    27  int StackPush(Stack *s, StackElmt e);
    28  int StackPop(Stack *s, StackElmt *e);
    29  
    30  #endif /*STACK_H*/

     1  /* **************************
     2   * Soure file of Stack
     3   * *************************/
     4  
     5  #include"Stack1.h"
     6  
     7  //實現(xiàn)List的函數(shù)，為了方便,放到了主函數(shù)所在的文件中，最好是單獨建立實現(xiàn)函數(shù)的源文件
     8  //初始化中棧
     9  int StackInit(Stack *s)
    10  {
    11      if(NULL == s)
    12          return FAILE;
    13  
    14      s->top = s->base = &STACK[0];
    15      s->size = 0;
    16  
    17  }
    18  //輸出棧中存放的元素
    19  int StackPrint(Stack *s)
    20  {
    21      int index = 0;
    22  
    23      if(NULL == s)
    24          return FAILE;
    25  
    26      if(s->size == 0)
    27      {
    28          printf("the Stack is empty,there is not any element \n");
    29          return FAILE;
    30      }
    31  
    32      while(index < (s->size))
    33      {
    34          printf("%d  ",*((s->base)+index) );
    35          index++;
    36      }
    37  
    38      printf("\n ");
    39  
    40      return SUCCESS;
    41  }
    42  
    43  //入棧函數(shù),top指向棧頂,先把元素入棧,然后向棧頂移動一位
    44  int StackPush(Stack *s, StackElmt e)
    45  {
    46      if(NULL == s)
    47          return FAILE;
    48  
    49      if(s->size >= LEN)
    50      {
    51          printf("the Stack is full \n");
    52          return FAILE;
    53      }
    54  
    55      *(s->top) = e;
    56      (s->top)++;
    57      (s->size)++;
    58  
    59      return SUCCESS;
    60  }
    61  
    62  //出棧函數(shù),top先向棧底移到一位，然后移出當(dāng)前它所指向的元素
    63  int StackPop(Stack *s, StackElmt *e)
    64  {
    65      if(NULL == s)
    66          return FAILE;
    67  
    68      if(s->size == 0)
    69      {
    70          printf("the Stack is empty \n");
    71          return FAILE;
    72      }
    73  
    74      (s->top)--;
    75      *e = *(s->top);
    76      (s->size)--;
    77  
    78      return SUCCESS;
    79  }
    80  
    81  
    82  int main()
    83  {
    84      int i = 0;
    85      StackElmt e = 0;
    86      Stack stack ;
    87  
    88      if( SUCCESS == StackInit(&stack) )
    89          StackPrint(&stack);
    90  
    91      StackPush(&stack,7);
    92      StackPrint(&stack);
    93  
    94      StackPop(&stack,&e);
    95      printf("%d is poped \n",e);
    96  
    97      while(i++ < LEN+5)
    98      {
    99          if( SUCCESS == StackPush(&stack,i) )
   100              printf("%d is pushed \n",i);
   101      }
   102  
   103      while(i-- > 0)
   104      {
   105          if( SUCCESS == StackPop(&stack,&e) )
   106              printf("%d is poped \n",e);
   107      }
   108  
   109  }

各位看官，關(guān)于棧的例子咱們就說到這里。欲知后面還有什么例子，且聽下回分解。