用数组实现栈

栈定义

栈是一种特殊的线性表，它只允许在表的一端进行操作，遵循先进后出(FILO, First In Last Out)的原则，可以操作的一端称为栈顶，不可以操作的一端称为栈底。向栈中加入数据叫入栈，从栈中取出数据叫做出栈。数据结构及操作如图所示：

栈实现

栈可以使用数组或链表来实现，这里用数组实现。

数据结构定义：

typedef struct {
    unsigned int stackTop;    //栈顶索引
    unsigned int stackSize;    //栈大小
    char *stackArray;
}ttStack;

栈初始化及销毁：

//错误码定义
#define STACK_RESIZE_OK    (1)
#define STACK_OK    (0)
#define STACK_INIT_ERR    (-1)
#define STACK_RESIZE_ERR    (-2)
#define STACK_PUSH_ERR    (-3)

#define STACK_LENGTH    (16)

//栈初始化
ttStack* stackInit()
{
    ttStack *stack = NULL;
    stack = (ttStack *) malloc (sizeof(ttStack));
    if (stack == NULL)
        return NULL;
    stack->stackTop = 0;
    stack->stackSize = STACK_LENGTH;
    stack->stackArray = (char*)malloc(sizeof(char) * STACK_LENGTH);
    if (stack->stackArray == NULL) {
        free(stack);
        return NULL;
    }
    return stack;
}

//销毁栈
void stackDestory(ttStack* stack)
{
    if (stack != NULL) {
        if (stack->stackArray != NULL) {
            free(stack->stackArray);
            stack->stackArray = NULL;
        }
        free(stack);
        stack = NULL;
    }
}

栈调用 stackInit 进行初始化，先申请一个 STACK_LENGTH 大小的数组，当栈容量不够时会调用 pushCheckAndResize 对栈进行扩容，与 c++ 中 vector 扩容方式相同，每次容量扩为原来的 2 倍。栈销毁时要将对应的内存进行释放。

static int pushCheckAndResize(ttStack* stack, unsigned int pushSize)
{
    unsigned int nowSize = stack->stackSize;
    if (stack->stackTop + pushSize <= nowSize)
        return STACK_OK;

    while (stack->stackTop + pushSize > nowSize)
        nowSize *= 2;

    printf("resize Stack %d, need:%d\n", nowSize, stack->stackTop + pushSize);
    char* tmpArray = (char *) malloc (nowSize * sizeof(char));
    if (tmpArray == NULL)
        return STACK_RESIZE_ERR;

    memcpy(tmpArray, stack->stackArray, stack->stackTop * sizeof(char));
    free(stack->stackArray);
    stack->stackArray = tmpArray;
    stack->stackSize = nowSize;

    return STACK_OK;
}

栈最重要的操作就是入栈和出栈，下面是对数据类型是 int 的数据进行入栈和出栈的操作：

//int 入栈
int pushInt(ttStack* stack, int data)
{
    if (stack == NULL || stack->stackArray == NULL) {
        printf("please init stack first\n");
        return STACK_INIT_ERR;
    }
    if (pushCheckAndResize(stack, sizeof(int)) != STACK_OK)
        return STACK_PUSH_ERR;
    *((int *)(&stack->stackArray[stack->stackTop])) = data;
    stack->stackTop += sizeof(int);
    return STACK_OK;
}

//int 出栈
int popInt(ttStack* stack)
{
    if (stack == NULL || stack->stackArray == NULL || stack->stackTop < sizeof(int))
        return (int)STACK_INIT_ERR;
    stack->stackTop -= sizeof(int);
    int a = *((int *)(&stack->stackArray[stack->stackTop]));
    return a;
}

其它数据类型与 int 类型基本相同，因此可用宏定义来定义不同数据类型的函数：

//入栈函数宏
int push##funcName(ttStack* stack, type data)    \
{    \
    if (stack == NULL || stack->stackArray == NULL) {    \
        printf("please init stack first\n");    \
        return STACK_INIT_ERR;    \
    }    \
    if (pushCheckAndResize(stack, sizeof(type)) != STACK_OK)    \
        return STACK_PUSH_ERR;    \
    *((type *)(&stack->stackArray[stack->stackTop])) = data;    \
    stack->stackTop += sizeof(type);    \
    return STACK_OK;    \
}
//出栈函数宏
#define implementPopFunction(funcName, type)    \
type pop##funcName(ttStack* stack)    \
{    \
    if (stack == NULL || stack->stackArray == NULL || stack->stackTop < sizeof(type))    \
        return (type)STACK_INIT_ERR;    \
    stack->stackTop -= sizeof(type);    \
    type a = *((type *)(&stack->stackArray[stack->stackTop]));    \
    return a;    \
}

//入栈函数
//char
implementPushFunction(Char, char)
//short
implementPushFunction(Short, short)
//int
implementPushFunction(Int, int)
//long
implementPushFunction(Long, long)
//指针
implementPushFunction(Ptr, void*)
//float
implementPushFunction(Float, float)
//double
implementPushFunction(Double, double)

//出栈函数
//char
implementPopFunction(Char, char)
//short
implementPopFunction(Short, short)
//int
implementPopFunction(Int, int)
//long
implementPopFunction(Long, long)
//指针
implementPopFunction(Ptr, void*)
//float
implementPopFunction(Float, float)
//double
implementPopFunction(Double, double)

测试函数：

int main(int argc, char* argv[])
{
    char a = 'a';
    short b = 10;
    int c = 1024;
    long d = 10000;
    int array[] = { 1, 2, 3, 4, 5 };

    printf("array:%p\n", array);

    ttStack* stack = stackInit();

    pushChar(stack, a);
    pushShort(stack, b);
    pushInt(stack, c);
    pushLong(stack, d);
    pushPtr(stack, array);

    //必须按逆序出栈
    int* ptr = (int*)popPtr(stack);
    long dd = popLong(stack);
    int cc = popInt(stack);
    short bb = popShort(stack);
    char aa = popChar(stack);

    printf("pop:%c, %d, %d, %d, %p\n", aa, bb, cc, dd, ptr);

    stackDestory(stack);
    return 0;
}