C语言 栈的实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// 头文件 
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
// 宏定义
#define TRUE 1 
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100
typedef int ElemType;
typedef int Status;
// 栈的顺序结构表示
typedef struct {
	ElemType* base;
	ElemType* top;
	int stacksize;
}SqStack;
//初始化一个空栈 
Status InitStack(SqStack& S) {
	S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!S.base) return false;
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return true;
   
}
//销毁栈 
Status DestroyStack(SqStack& S){
	S.top=NULL;
	S.stacksize=0;
	free(S.base);
	return true;
}
//清空栈 
Status ClearStack(SqStack& S){
	S.top=S.base;
	return true;
} 
//判断栈是否为空
Status StackEmpty(SqStack S){
	if(S.top==S.base) 
	  return true;//空为真 
	else 
	  return false;//  非空为假 
	  
}
//求栈的长度
Status StackLength(SqStack S){
	return (S.top-S.base);
}
//求栈顶元素
Status GetTop(SqStack S,ElemType &e){
     if(S.top==S.base) {
     	printf("空栈~");
       return FALSE;
	 } 
    else {
      
      e=*(S.top-1);
	}
}

//入栈
Status Push(SqStack& S,ElemType e){
	if(S.top-S.base>=S.stacksize){ // 满栈 
		S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!S.base)
		  return false;
		S.top=S.base+S.stacksize;//栈底地址可能改变，重新定位栈顶元素
		S.stacksize+=STACKINCREMENT;
	}
	*S.top=e;
	S.top++;
	return true;
}
//出栈 
Status Pop(SqStack& S,ElemType& e){
	if(S.base==S.top){  //空栈 
        printf("空栈~");
		return false;
		}
    S.top--;
    e=*S.top;
	   //说明：此处容易使人迷惑，实际上此元素并没真正删除，仍在S.top中，
	   //但是如果插入元素，就会被更新，就像是删除了一样  
    
}
//遍历栈 
Status StackTraverse(SqStack S){
	if(S.base==NULL) 
	   return ERROR;
	if(S.base==S.top) 
	 printf("栈中没有元素~~\n");
	ElemType* p;
	p=S.top;
	while(p>S.base){ //从栈顶向栈低遍历 
		p--; 
		printf("%d\n",*p);
	} 
	return true;
}
int main(){
   SqStack s;
   InitStack(s);//初始化
   for(int i=1;i<=150;i++){
   	Push(s,i);//入栈 
   } 
   StackTraverse(s);//遍历 
   printf("栈顶的长度为，%d\n",StackLength(s));
   int n;
   Pop(s,n);
   printf("出栈的元素为：%d\n\n",n);
   GetTop(s,n);
   printf("现在栈顶的元素为：%d\n\n",n); 
   printf("清空栈~~\n\n") ;
   ClearStack(s);
   printf("栈现在为：%d\n",StackEmpty(s)); 
    
   }