手写C版本的stack

记录一个小demo，留着以后批判。

实现了除了运算符重载以外的所有功能(大概),deque扩容有问题，push和pop设计导致的，可以通过修改宏SIZE的大小来避免扩容，其他的都没什么问题。stack使用的是extern const struct stackFuntion stack; **类似于C++的namespace**中的通用接口。

用到的宏

1
2
3
#define TYPE int
#define SIZE 51200//修改大小避免扩容
#define INT_MIN -2147483648

data定义

1
2
3
4
5
6
7
8
9
typedef struct deque{
    struct deque *prev;
    struct deque *next;
    unsigned int nowdeque;//当前所处的deque位置
    unsigned int top;
    unsigned int size;
    unsigned int empty;
    TYPE data[0];
}deque;

funtion定义

1
2
3
4
5
6
7
8
9
typedef struct stackFuntion{
    deque* (*initStackData)(void);//初始化stack为empty
    TYPE (*top)(deque* this);
    unsigned int (*empty)(deque* this);
    unsigned int (*size)(deque* this);
    void (*push)(deque** this,TYPE value);
    TYPE (*pop)(deque** this);//删除的同时拿到被删除的元素，与STL不同，方便操作
    void (*swap)(deque** stackData1,deque** stackData2);
}stackFuntion;

stack初始化

1
2
3
const stackFuntion stack = {
    initStackData,tops,emptys,sizes,push,pop,swaps
};

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
void StackTest(){
    deque* p =  stack.initStackData();
    for(int i = 0; i < 50; i++){
        stack.push(&p,i);
        printf("i = %d\tstack.top() = %d\n",i,stack.top(p));
    }
    TYPE a =  stack.pop(&p);
    printf("a = %d\n",a);
    printf("size = %d\n",stack.size(p));
    printf("empty = %d\n",stack.empty(p));
}

完整代码

Stack.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
//
//  stack.c
//  CwithSTL
//
//  Created by echo on 2021/2/16.
//  Copyright © 2021 echo. All rights reserved.
//

#include "stack.h"
#include "stdlib.h"
#include "stdio.h"


//初始化stack，初始容量为512个数据单位，返回数据指针
deque* initStackData(){
    deque* this = malloc(sizeof(deque)+sizeof(TYPE)*SIZE);
    this->size = 0;
    this->top = 0;
    this->empty = 1;
    this->nowdeque = 1;
    this->next = NULL;
    this->prev = NULL;
    return this;
}

//返回stack顶元素，如果stack为空则返回INT_MIN
TYPE tops(deque* this){
    if(this->empty == 0)return INT_MIN;
    else return this->data[this->top - 1];
}

//空返回1，非空返回0
unsigned int emptys(deque* this){
    return this->empty;
}

//返回整个stack的元素数量,所有元素数量等于当前栈所处的位置-1*512(stack size)+size(当前stack size)
unsigned int sizes(deque* this){
    return this->size+(this->nowdeque-1)*SIZE;
}

//入栈，如果栈满则开辟新的栈
void push(deque** this,TYPE value){
    if((*this)->size == SIZE){
        deque* tmp = (deque*)malloc(sizeof(deque)+ sizeof(TYPE)*SIZE);
        tmp->top = 0;
        (*this)->next = tmp;
        tmp->prev = (*this);
        tmp->nowdeque = (*this)->nowdeque+1;//当前deque所处位置+1;
        tmp->size = 0;
        tmp->data[tmp->size++] = value;
        tmp->empty = 0;
        *this = tmp;//当前指针指向新的deque
    }else{
        (*this)->top++;
        (*this)->data[(*this)->size++] = value;//如果非扩容情况
    }
}

TYPE pop(deque** this){
    //如果当前deque并非最后一个deque并且这个deque只有一个元素时
    if((*this)->nowdeque != 1 && (*this)->size == 1){
        deque* tmp = (*this)->prev;
        tmp->nowdeque = (*this)->nowdeque+1;
        tmp->size = 0;
        tmp->next = NULL;
        free(*this);
        (*this) = tmp;
        tmp = NULL;
    }
    //如果当前deque为最后一个deque并且deque只有一个元素时
    if((*this)->size != 0){
        (*this)->empty = (*this)->size > 0 ? 0 : 1;
        return (*this)->data[--(*this)->size];//返回最后一个元素并且size--
    }
    else{
        printf("pop error，stack is empty\n");
        return INT_MIN;
    }
}

//交换俩个stack
void swaps(deque** stackData1,deque** stackData2){
    deque* tmp = (*stackData1);
    stackData1 = stackData2;
    stackData2 = &tmp;
}

const stackFuntion stack = {
    initStackData,tops,emptys,sizes,push,pop,swaps
};

stack.h

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
//
//  stack.h
//  CwithSTL
//
//  Created by echo on 2021/2/16.
//  Copyright © 2021 echo. All rights reserved.
//

#ifndef stack_h
#define stack_h

#include <stdio.h>
#include "stdlib.h"
#include "stdio.h"
#define TYPE int
#define SIZE 51200
#define INT_MIN -2147483648
typedef struct deque{
    struct deque *prev;
    struct deque *next;
    unsigned int nowdeque;//当前所处的deque位置
    unsigned int top;
    unsigned int size;
    unsigned int empty;
    TYPE data[0];
}deque;

typedef struct stackFuntion{
    deque* (*initStackData)(void);//初始化stack为empty
    TYPE (*top)(deque* this);
    unsigned int (*empty)(deque* this);
    unsigned int (*size)(deque* this);
    void (*push)(deque** this,TYPE value);
    TYPE (*pop)(deque** this);//删除的同时拿到被删除的元素，与STL不同，方便操作
    void (*swap)(deque** stackData1,deque** stackData2);
}stackFuntion;

#endif /* stack_h */

Main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "stack.h"

extern const struct stackFuntion stack;
//貌似deque有点小问题，不支持扩容，最大容量通过修改stack.c中的SIZE宏来确定
void StackTest(){
    deque* p =  stack.initStackData();
    for(int i = 0; i < 50; i++){
        stack.push(&p,i);
        printf("i = %d\tstack.top() = %d\n",i,stack.top(p));
    }
    TYPE a =  stack.pop(&p);
    printf("a = %d\n",a);
    printf("size = %d\n",stack.size(p));
    printf("empty = %d\n",stack.empty(p));
}

int main(){
    StackTest();
    return 0;
}