C语言数据结构 栈的基础操作

/*
 * 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是某个确定的、将由用户自行定义的、含某个关系运算的数据对象
typedef int SElemType;

//函数结果状态代码
#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;  //在栈构造之前和销毁之后，base的值为NULL
  SElemType *top;   //栈顶指针
  int stacksize;   //当前已分配
}SqStack;
/**********基本操作的函数原型说明**********/
//构造一个空栈S
Status InitStack(SqStack &S);      
//销毁栈S，S不再存在
Status DestroyStack(SqStack &S);
//把S置为空栈
Status ClearStack(SqStack &S);
//若栈S为空栈，则返回TURE，否则返回FALSE
Status StackEmpty(SqStack S); 
//返回S的元素个数，即栈的长度
int StackLength(SqStack S);
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
Status GetTop(SqStack S, SElemType &e); 
//插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e);
//若栈不空，则删除S的栈顶元素，用e新栈顶的值，并返回OK;否则返回ERROR;
Status Pop(SqStack &S, SElemType &e);
//从栈底到栈顶依次对栈中每个元素调用函数visit();一旦visit()失败，则操作失败
Status StackTraverse(SqStack S, Status(* visit)(SElemType));
//visit()函数
Status visit(SElemType e);
//测试函数
Status TestMyStack();

#endif MYSTACK_H_

#include "MyStack.h"

Status InitStack(SqStack &S){
  //构造一个空栈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;
}//InitStack

Status DestroyStack(SqStack &S){
  if(!S.base){
    printf("DestroyStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
//在调用malloc的时候，系统会记住你申请的这块连续空间的起始地址以及这块空间的大小，
//释放free的时候，只要把这个起始地址告诉系统，系统自然就知道要释放多大的空间。
  free(S.base);    
  S.top = NULL;
  S.base = NULL;
  S.stacksize = 0;
  return OK;
}//DestroyStack

Status ClearStack(SqStack &S){
  if(!S.base){
    printf("ClearStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
  S.top = S.base; 
  return OK; 
}//ClearStack

Status StackEmpty(SqStack S){
  if(S.top == S.base){
    return TRUE;
  }
  else{
    return FALSE;
  }
}//StackEmpty

int StackLength(SqStack S){
  return S.top - S.base;
}//StackLength

Status 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;
}//GetTop

Status 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;
}//Push

Status Pop(SqStack &S, SElemType &e){
  //若栈不空，则删除S的栈顶元素，用e返回新栈顶的值，并返回OK，否则返回ERROR;
  if(S.top == S.base){
    printf("Pop: Stack is empty\n");
    return ERROR;
  }
  e = *--S.top;    //S.top--; e = *S.top;
  return OK;
}//Pop

Status StackTraverse(SqStack S, Status(* visit)(SElemType)){
  while(S.top > S.base){
    visit(*S.base++); 
  } 
  printf("\n");
  return OK; 
}//StackTraverse

Status visit(SElemType e){
  printf("%d ",e) ;
  return OK;
}//visit

Status 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

//主函数
int main(){
  TestMyStack();
  system("pause");
  return 0;
}