数据结构（1）----堆栈

 1 #include "stack.h"
 2 /*
 3 typedef int T;
 4 //#define N 10
 5 //类型
 6 typedef struct Stack{
 7     T* m_vect;   //存储元素内存空间 
 8     size_t size; //堆栈总容量
 9     size_t index;//堆栈中已经存储元素的个数
10     //T m_vect[N];
11 }Stack;
12 */
13 //初始化堆栈   申请动态内存
14 void init(Stack *stack,size_t size){
15     stack->m_vect = calloc(size,sizeof(T));
16     stack->size = size;
17     stack->index = 0;
18 }
19 
20 //把data这个元素放到堆栈中去
21 void push(Stack *stack,T data){
22     stack->m_vect[stack->index] = data;
23     stack->index++;
24 }
25 
26 //从堆栈中取到一个元素  该元素是最后放到堆栈中那个元素
27 T pop(Stack *stack){
28     return stack->m_vect[--stack->index];    
29 }
30 
31 //查看堆栈顶的元素  并不拿走
32 T peek(Stack *stack){
33     return stack->m_vect[stack->index-1];    
34 }
35 
36 //堆栈是否为空
37 bool isEmpty(Stack *stack){
38     /*if(stack->index == 0){
39         return true;    
40     }else{
41         return false;    
42     }*/
43     return stack->index == 0;    
44 }
45 
46 //堆栈中存储元素的个数
47 size_t getCnt(Stack *stack){
48     return stack->index;    
49 }
50 
51 //堆栈中容量的大小
52 size_t getSize(Stack *stack){
53     return stack->size;    
54 }
55 
56 //堆栈是否已经满了
57 bool isFull(Stack *stack){
58     return stack->size == stack->index;    
59 }
60 
61 //销毁堆栈
62 void destroy(Stack *stack){
63     if(stack->m_vect != NULL){
64         free(stack->m_vect);
65         stack->m_vect = NULL;
66     }
67 }
68 //清空堆栈中的元素
69 void clear(Stack *stack){
70     while(!isEmpty(stack)){
71         pop(stack);    
72     }
73 }
74 //遍历一下堆栈中的元素
75 void travel(Stack *stack){
76     for(int i=0;i<stack->index;i++){
77         printf("%d ",stack->m_vect[i]);    
78     }    
79     printf("\n");
80 }
81 //判断brr是否是arr作为入栈的出栈顺序
82 bool isOutOfStack(T arr[],T brr[],size_t len){
83     Stack s;
84     init(&s,len);
85     int j = 0;//记录brr[]数组下标位置
86     for(int i=0;i<len;i++){
87         push(&s,arr[i]);//把入栈元素依次入栈
88         while(!isEmpty(&s) && peek(&s)==brr[j]){//一旦栈顶元素等于出栈元素 
89             pop(&s);//出栈
90             j++;    //下一个出栈元素
91         }
92     }
93     bool flag = isEmpty(&s);//栈里面元素全部都出列了 
94     destroy(&s);
95     return flag;
96 }