抽象数据类型(ADT)-栈

栈是另一种抽象数据类型，我们在前面文章（用数组实现栈）中讲到了它的定义和一种通用栈实现，实际应用中栈内多数只存储一种数据类型。这里我们实现一种存储单一数据类型的栈。

单一数据类型栈实现

如果栈中只有一种数据类型，可以通过　#define ELEMENT_TYPE char 来定义该数据类型，通过定义不同的 ELEMENT_TYPE 来实现用于存储不同数据类型的栈：

//定义数据类型
#define ELEMENT_TYPE int

#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)

//栈结构
typedef struct {
    unsigned int stackTop;
    unsigned int stackSize;
    ELEMENT_TYPE *stackArray;
}ttStack;

需要实现的栈接口：

ttStack* stackInit();    //初始化栈
void stackDestory(ttStack* stack);    //销毁栈
bool stackEmpty(ttStack* stack);    //判断栈是否为空
int push(ttStack* stack, ELEMENT_TYPE data);    //入栈
ELEMENT_TYPE pop(ttStack* stack);    //出栈
ELEMENT_TYPE top(ttStack* stack);    //取栈顶元素

接口实现：

ttStack* stackInit()
{
    ttStack *stack = NULL;
    stack = (ttStack *) malloc (sizeof(ttStack));
    if (stack == NULL)
        return NULL;
    stack->stackTop = 0;
    stack->stackSize = STACK_LENGTH;
    stack->stackArray = (ELEMENT_TYPE*)malloc(sizeof(ELEMENT_TYPE) * 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;
    }
}

bool stackEmpty(ttStack* stack)
{
    if (stack == NULL || stack->stackTop == 0)
        return true;
    return false;
}

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);
    ELEMENT_TYPE* tmpArray = (ELEMENT_TYPE *) malloc (nowSize * sizeof(ELEMENT_TYPE));
    if (tmpArray == NULL)
        return STACK_RESIZE_ERR;

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

    return STACK_OK;
}

int push(ttStack* stack, ELEMENT_TYPE data)
{
    if (stack == NULL || stack->stackArray == NULL) {
        printf("please init stack first\n");
        return STACK_INIT_ERR;
    }
    if (pushCheckAndResize(stack, 1) != STACK_OK)
        return STACK_PUSH_ERR;
    stack->stackArray[stack->stackTop++] = data;
    return STACK_OK;
}

ELEMENT_TYPE pop(ttStack* stack)
{
    if (stack == NULL || stack->stackArray == NULL || stack->stackTop == 0)
        return (ELEMENT_TYPE)STACK_INIT_ERR;
    stack->stackTop --;
    return stack->stackArray[stack->stackTop];
}

ELEMENT_TYPE top(ttStack* stack)
{
    if (stack == NULL || stack->stackArray == NULL || stack->stackTop == 0)
        return (ELEMENT_TYPE)STACK_INIT_ERR;
    return stack->stackArray[stack->stackTop - 1];
}

测试函数：

int main(int argc, char* argv[])
{
    ttStack* stack = stackInit();

    push(stack, 'a');
    push(stack, 'b');
    push(stack, 'c');
    push(stack, '[');

    while (!stackEmpty(stack)) {
        char a = top(stack);
        char b = pop(stack);
        printf("a:%c, b:%c\n", a, b);
    }

    stackDestory(stack);
    return 0;
}

参考：

<数据结构与算法分析-C语言实现> P3