顺序栈的表示和实现

栈是一种重要的数据结构，从数据结构角度来看，栈也是线性表，其特殊性在于栈的基本操作是线性操作的子集，是操作受限的线性表。但是从数据类型角度来看，栈和线性表大不相同的两类重要的抽象数据结构。栈被广泛的应用在各种软件系统中，因此在面向对象的设计中，栈是多型数据类型。

名词解释

栈

• 是限定仅在表未进行插入或删除的线性表

顺序栈

• 和线性表类似，栈也有两种存储结构。顺序栈，即栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈低到栈顶的数据元素，同时附设指针top指向栈顶元素在顺序栈中的位置。

栈顶

• 表示栈的线性表的表尾端

栈低

• 表示栈的线性表的表头端

顺序栈的存储结构

typedef struct {
    
    ElemType *base; //在栈构造之前和销毁之后 base的值应该为NULL
    ElemType *top;  //栈顶指针
    int stackSize;  //当前已经分配的存储空间，以元素为单位
    
}SqStack;

基本操作

• Status InitStack(SqStack **stack);
• Status GetSqStackTop(SqStack stack, ElemType *elem);
• Status Push(SqStack *stack, ElemType elem);
• Status Pop(SqStack *stack, ElemType *elem);
• Status SqStackLength(SqStack stack, int *length);
• Status ClearSqStack(SqStack *stack);
• Status DestroySqStack(SqStack *stack);
• Status TraverseSqStack(SqStack stack);

基本操作实现

初始化

Status InitStack(SqStack **stack) {
    
    *stack = (SqStack *)malloc(sizeof(SqStack));
    (*stack)->base = (ElemType *)malloc(kSqStackInitSize * sizeof(ElemType));
    if (!(*stack)->base) {
        
        printf("%s--%d--OVERFLOW", __func__, __LINE__);
        return OVERFLOW;
    }
    (*stack)->top = (*stack)->base;
    (*stack)->stackSize = kSqStackInitSize;
    return OK;
}

定义一个指向指针的指针去接收指针地址，而*stack表示初始化函数接收到的指针。

得到栈顶元素

Status GetSqStackTop(SqStack stack, ElemType *elem) {
    
    if (stack.base == stack.top) {
        
        return ERROR;
    }
    *elem = *(stack.top-1);
    return OK;
}

如果栈顶和栈低指针地址相同，表示这个栈为空栈直接返回ERROR。因为栈顶指针Top永远指向下一个进栈元素，所以读取当前栈顶元素为*(stack.top - 1)

进栈

Status Push(SqStack *stack, ElemType elem) {
    
    if (stack->top - stack->base >= stack->stackSize) {
        
        stack->base = (ElemType *)realloc(stack->base, (stack->stackSize+kSqStackIncrement)*sizeof(ElemType));
        if (!stack->base) {
            
            return OVERFLOW;
        }
        stack->top = stack->base + stack->stackSize;
        stack->stackSize += kSqStackIncrement;
    }
    *stack->top = elem;
    stack->top++;
    return OK;
}

在栈空间不够的时候分配空间后，需要更新栈顶指针

出栈

Status Pop(SqStack *stack, ElemType *elem) {
    
    if (stack->base == stack->top) {
        
        return ERROR;
    }
    *elem = *(--stack->top);
    return OK;
}

出栈后需要及时更新栈顶指针

栈中元素个数

Status SqStackLength(SqStack stack, int *length) {
    
    int counter = 0;
    while (stack.base != stack.top) {
        
        stack.top--;
        counter++;
    }
    *length = counter;
    return OK;
}

清空栈

Status ClearSqStack(SqStack *stack) {
    
    if (stack->base != stack->top) {
        
        stack->top = stack->base;
    }
    return OK;
}

栈被清空之后，这个栈依然可以使用

销毁栈

Status DestroySqStack(SqStack *stack) {
    
    free(stack->base);
    stack->base = NULL;
    free(stack);
    return OK;
}

栈被销毁之后，这个栈就不在存在不能被使用。

输出栈中元素

Status TraverseSqStack(SqStack stack) {
    
    while (stack.base != stack.top) {
        
        printf("stack elem %d \n", *--stack.top);
    }
    return OK;
}

应用举例

数制转换：对于输入任意一个非负十进制整数，打印输出与其等值的八进制数
例如：十进制 1348 = 八进制 2504

void conversion() {
    
    SqStack *stack;
    InitStack(&stack);
    int number = 1348;
    printf("十进制：%d 等于 ", number);
    while (number) {
        
        Push(stack, number % 8);
        number = number / 8;
    }
    while (stack->top != stack->base) {
        
        int elem;
        Pop(stack, &elem);
        printf("%d", elem);
    }
    printf("\n");
}

小结

栈在软件设计方面应用非常广泛，比如走迷宫，递归算法，匹配等这些思想都有栈的影子。

欢迎讨论

Email：huliuworld@yahoo.com

Github:https://github.com/LHCoder2016/DataStructure