C语言栈的简易兑现，包含O（1）时间复杂度的min方法

C语言栈的简易实现，包含O（1）时间复杂度的min方法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
//定义栈的初始分配空间
#define STACK_INIT_SIZE 100
//栈的分配增量
#define STACKINCRENMENT 10

typedef struct
{
 char *top;//栈顶
 char *base;//栈底
 char min;
 int stacksize;//当前栈的大小
}stack;

//栈的初始化
stack *initStack(stack *s)
{
 s->base=(char*)malloc(STACK_INIT_SIZE *sizeof(char));
 //假设s没有分配成功
 if(NULL==s)
 {
  exit(-1);
 }
 //栈顶指针指向栈底，也就是说栈顶与栈底都指向同一个位置
 s->top=s->base;
 s->stacksize=STACK_INIT_SIZE;
}

//销毁栈
stack * destoryStack(stack *s)
{
 //如果栈不存在，表示栈根本没有被初始化
 if(NULL==s->base)
 {
  return ;
 }
 //进行销毁，也就是将分配的内存空间收回，将栈的一些参数重新设置
 free(s->base);
 s->top=s->base=NULL;
 s->stacksize=0;
 return s;
}

//清空栈
stack *clearStack(stack *s)
{
 if(NULL==s->base)
 {
  printf("\n Sorry, stack does not exist！\n");
  return ;
 }
 s->top=s->base;
 return s;
}

//取元素
char getStackElem(stack *s)
{
 //保存栈顶元素
 char topElem;
 //如果栈顶指针指向与栈底指针指向同一内存单元时，表示栈为空或者栈不存在
 if(s->top=s->base)
 {
  printf("栈中没有可以被取的元素！\n");
  return ;
 }
 topElem=*(s->top--);
 return topElem;
}
//进栈操作
stack *push(stack *s,char elem)
{
 //s是否已满，若栈满，重新分配空间
 if((s->top-s->base)>STACK_INIT_SIZE)
 {
  s->base=(char*)realloc(s->base,(STACKINCRENMENT+STACK_INIT_SIZE)*sizeof(char));
  if(NULL==s->base)
  {
   return;
  }
  //将栈顶指针指向栈顶
  s->top=s->base+s->stacksize;
  s->stacksize+=STACKINCRENMENT;
 }
 //将元素e，写入栈顶。
 *(s->top)=elem;
 s->min=s->top-s->base ==0 ? elem : elem < s->min ? elem : s->min;//取得最小值。top==base时，min=elem，否则取较小的。
 s->top++;
 return s;

}
//出栈
char pop(stack *s)
{
 char elem;
 if(s->top==s->base)
 {
   exit(-1);
 }
 s->top--;
 elem=*(s->top);
 return elem;
}

char minofStack(stack *s){
	return s->min;
}

int main()
{
 stack s;
 int i;
 char *elem="bcdfg";
 char *temp;
 //栈的初始化；
 initStack(&s);
 //插入元素a,b,c,d,e调用push函数
 printf("进栈顺序：\n");
 temp=elem;
 while(*elem!='\0')
 {
  printf("%3c",*elem);
  elem++;
 }
 elem=temp;
  while(*elem !='\0')
 {
  push(&s,*elem);
  elem++;
 }

 putchar('\n');
 printf("min = %3c",minofStack(&s));

 //取出元素,调用pop函数
    printf("\n出栈顺序：\n");
 //while(s.top!=s.base!=NULL)
 while(s.top!=NULL && s.base!=NULL)
 {
  printf("%3c",pop(&s));
 }

 clearStack(&s);

 return 1;
}