c語言數據結構之棧的基本操作，數據結構基本操作

c語言數據結構之棧的基本操作，數據結構基本操作

棧是限定僅在表尾進行插入或者刪除操作的線性表。各位也可以到360雲盤中下載完整程序，運行環境為vc++6.0 

http://yunpan.cn/cVKkv9fmsp4wB  訪問密碼 b737

1 typedef struct
2 {
3     SelemType *base;
4     SelemType *top;
5     int        stacksize;
6 }SqStack;

現在來介紹下棧的操作實現。

/********************************************************************
函數名稱：  InitStack
函數作用：  構造一個空棧
輸入參數：  s
輸出參數：  無
返回值：    FALSE or TRUE
********************************************************************/
Status InitStack(SqStack &s)
{
   s.base=(SelemType *)malloc(STACK_INIT_SIZE*sizeof(SelemType));  //申請空間
   if(!s.base) return FALSE;    //如果申請不成功，返回FALSE
   s.top=s.base;                //申請成功，令棧頂指針等於棧尾指針
   s.stacksize=STACK_INIT_SIZE; //stacksize表示申請分配的空間大小
   return TRUE;
}

/********************************************************************
函數名稱：  Push
函數作用：  將元素e入棧 
輸入參數：  棧s,元素e
輸出參數：  無
返回值：    FALSE or TRUE
時間復雜度：O(1)
********************************************************************/
Status Push(SqStack &s,SelemType e)
{
   if((s.top-s.base)>=s.stacksize)
   {
     s.base=(SelemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SelemType));
     if(!s.base) return FALSE; 
     s.top=s.base+s.stacksize;
     s.stacksize+=STACKINCREMENT;
   }
   *s.top++=e;
   return TRUE;
}

/********************************************************************
函數名稱：  StackBrower
函數作用：  遍歷
輸入參數：  棧s
輸出參數：  無
返回值：    FALSE or TRUE
時間復雜度：O(n)
********************************************************************/
Status StackBrower(SqStack s)
{
    if(!s.base) 
    {
        cout<<"不存在棧s"<<endl;
        return FALSE;
    }
    if(s.top==s.base) 
    {
        cout<<"s為空棧"<<endl;
        return FALSE;
    }
    while(!(s.top==s.base))
    {
       cout<<*(--s.top)<<"  ";
    }
    cout<<endl;
    return TRUE;
}

/********************************************************************
函數名稱：  DestroyStack
函數作用：  銷毀空棧
輸入參數：  棧s
輸出參數：  無
返回值：    FALSE or TRUE
時間復雜度：O(1)
********************************************************************/
Status DestroyStack(SqStack &s)
{
   free(s.base);          //只需要釋放base指針 
   s.base=NULL;
   return TRUE;
}   

/********************************************************************
函數名稱：  ClearStack
函數作用：  銷毀空棧
輸入參數：  棧s
輸出參數：  無
返回值：    FALSE or TRUE
時間復雜度：O(1)
********************************************************************/
Status ClearStack(SqStack &s)
{
    if(s.top==s.base) return TRUE;
    s.top=s.base;
    return TRUE; 
}  

/********************************************************************
函數名稱：  StackEmpty
函數作用：  判斷是否為空棧
輸入參數：  棧s
輸出參數：  無
返回值：    0非空棧 or 1空棧
時間復雜度：O(1)
********************************************************************/
Status StackEmpty(SqStack &s)
{
   return(s.base==s.top);
}

/********************************************************************
函數名稱：  StackLength
函數作用：  獲取當前儲存數據的長度
輸入參數：  棧s
輸出參數：  無
返回值：    棧長
時間復雜度：O(1)
********************************************************************/
int    StackLength(SqStack s)
{
 return (s.top-s.base);
}

Status GetTop(SqStack s,SelemType &e)
{
  e=*(s.top-1);
  return TRUE;
}

接下來就是main函數測試代碼

#include"StackLib.h"

void main()
{
  int e[20];
  int i=0;
  int a;
  for(i=0;i<20;i++) e[i]=i;
  SqStack s;
  InitStack(s);           //構造一個空棧
  for(i=0;i<20;i++) 
  {
      Push(s,e[i]);       //數據入棧
  }

  StackBrower(s);         //遍歷堆棧
  cout<<"當前儲存數據:"<<StackLength(s)<<"個"<<endl;

  GetTop(s,a);            //獲得棧頂元素，並打印
  cout<<a<<endl;
  
  ClearStack(s);          //清空棧
  StackBrower(s);         //遍歷棧
  cout<<"1為空棧，0非空:"<<StackEmpty(s)<<endl;  //判斷棧是否為空

  DestroyStack(s);        //銷毀堆棧
  StackBrower(s);         //
}