/* * Include.h * * Created on: 2016.11.23 *   Author: Jack Cui */#ifndef MYSTACK_H_#define MYSTACK_H_#include <stdlib.h>#include <stdio.h>#include <malloc.h> /*棧(Stack)是限定僅在表尾進行插入或刪除操作的線性表**棧頂(top)和棧底(bottom)相等，代表為空棧***///SElemType是某個確定的、將由用戶自行定義的、含某個關(guān)系運算的數(shù)據(jù)對象typedef int SElemType;//函數(shù)結(jié)果狀態(tài)代碼#define TRUE    1  #define FALSE    0#define OK     1#define ERROR    0#define INFEASIBLE -1   //不可行#define MY_OVERFLOW -2   //溢出/**********棧的順序存儲表示**********/#define STACK_INIT_SIZE 100   //存儲空間初始分配量#define STACKINCREMENT 10   //存儲空間分配增量typedef struct{  SElemType *base;  //在棧構(gòu)造之前和銷毀之后，base的值為NULL  SElemType *top;   //棧頂指針  int stacksize;   //當前已分配}SqStack;/**********基本操作的函數(shù)原型說明**********///構(gòu)造一個空棧SStatus InitStack(SqStack &S);      //銷毀棧S，S不再存在Status DestroyStack(SqStack &S);//把S置為空棧Status ClearStack(SqStack &S);//若棧S為空棧，則返回TURE，否則返回FALSEStatus StackEmpty(SqStack S); //返回S的元素個數(shù)，即棧的長度int StackLength(SqStack S);//若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORStatus GetTop(SqStack S, SElemType &e); //插入元素e為新的棧頂元素Status Push(SqStack &S, SElemType e);//若棧不空，則刪除S的棧頂元素，用e新棧頂?shù)闹担⒎祷豋K;否則返回ERROR;Status Pop(SqStack &S, SElemType &e);//從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)visit();一旦visit()失敗，則操作失敗Status StackTraverse(SqStack S, Status(* visit)(SElemType));//visit()函數(shù)Status visit(SElemType e);//測試函數(shù)Status TestMyStack();#endif MYSTACK_H_

#include "MyStack.h"Status InitStack(SqStack &S){  //構(gòu)造一個空棧S  S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));  if(!S.base){    //存儲分配失敗    printf("InitStack: malloc err/n");    exit(MY_OVERFLOW);  }  S.top = S.base;  S.stacksize = STACK_INIT_SIZE;  return OK;}//InitStackStatus DestroyStack(SqStack &S){  if(!S.base){    printf("DestroyStack: Stack does not exist/n");    exit(MY_OVERFLOW);  }//在調(diào)用malloc的時候，系統(tǒng)會記住你申請的這塊連續(xù)空間的起始地址以及這塊空間的大小，//釋放free的時候，只要把這個起始地址告訴系統(tǒng)，系統(tǒng)自然就知道要釋放多大的空間。  free(S.base);      S.top = NULL;  S.base = NULL;  S.stacksize = 0;  return OK;}//DestroyStackStatus ClearStack(SqStack &S){  if(!S.base){    printf("ClearStack: Stack does not exist/n");    exit(MY_OVERFLOW);  }  S.top = S.base;   return OK; }//ClearStackStatus StackEmpty(SqStack S){  if(S.top == S.base){    return TRUE;  }  else{    return FALSE;  }}//StackEmptyint StackLength(SqStack S){  return S.top - S.base;}//StackLengthStatus GetTop(SqStack S, SElemType &e){  ////若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR  if(S.top == S.base){    printf("GetTop: Stack is empty/n");    return ERROR;  }  e = *(S.top - 1);  return OK;}//GetTopStatus Push(SqStack &S, SElemType e){  //插入元素e為新的棧頂元素  if(S.top - S.base >= S.stacksize){ //棧滿，追加存儲空間    S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));    if(!S.base){      printf("Push: realloc error/n");    }    S.top = S.base + S.stacksize;    S.stacksize += STACKINCREMENT;  }  *S.top++ = e;    //*S.top = e; S.top++;  return OK;}//PushStatus Pop(SqStack &S, SElemType &e){  //若棧不空，則刪除S的棧頂元素，用e返回新棧頂?shù)闹担⒎祷豋K，否則返回ERROR;  if(S.top == S.base){    printf("Pop: Stack is empty/n");    return ERROR;  }  e = *--S.top;    //S.top--; e = *S.top;  return OK;}//PopStatus StackTraverse(SqStack S, Status(* visit)(SElemType)){  while(S.top > S.base){    visit(*S.base++);   }   printf("/n");  return OK; }//StackTraverseStatus visit(SElemType e){  printf("%d ",e) ;  return OK;}//visitStatus TestMyStack(){  SElemType j;   SqStack s;   SElemType e;   if(InitStack(s) == OK)   for(j = 1; j <= 12; j++)   {     Push(s,j);   }   printf("棧中的元素依次為：");   StackTraverse(s,visit);   Pop(s, e);   printf("彈出的棧頂元素 e=%d/n", e);   printf("棧空否：%d(1：是 0：否)/n", StackEmpty(s));   GetTop(s, e);   printf("棧頂元素 e=%d,棧的長度為%d/n", e, StackLength(s));   ClearStack(s);   printf("清棧后，棧是否為空：%d(1：空 0：否)/n",StackEmpty(s));   DestroyStack(s);   printf("銷毀棧后，s.top = %u s.base= %u s.stacksize=%d/n",s.top,s.base,s.stacksize);   return 0; }//TestMyStack//主函數(shù)int main(){  TestMyStack();  system("pause");  return 0;}