【数据结构和算法】【栈】顺序栈的代码实现

系统管理员 2022-08-13 12:55 185阅读 0赞

顺序栈的存储方式如下图所示：

![Center][]

代码实现如下：

// Filename: sq_stack.h
    
    #ifndef SQ_STACK_H_INCLUDED
    #define SQ_STACK_H_INCLUDED
    
    #ifndef _OK_
    #define OK  0
    #endif
    
    #ifndef _ERROR_
    #define ERROR  1
    #endif
    
    #ifndef _TRUE_
    #define TRUE  1
    #endif
    
    #ifndef _FALSE_
    #define FALSE  0
    #endif
    
    #ifndef _BiTNode_
    #define _BiTNode_
    typedef char TElemType;
    
    typedef struct BiTNode
    {
        TElemType data;
        struct BiTNode *lchild;
        struct BiTNode *rchild;
    } BiTNode, *BiTree;
    #endif
    
    // 栈中结点的元素类型
    typedef BiTree SElemType; // TODO: 根据实际应用修改类型
    
    typedef struct SqStack
    {
        SElemType *top;     // 栈顶指针
        SElemType *base;    // 栈底指针
        int stacksize;      // 栈当前可使用的最大容量
    }SqStack;
    
    #define STACK_INIT_SIZE 100     // 顺序栈的存储空间初始分配量
    #define STACK_INCREMENT 10      // 顺序栈的存储空间分配增量
    
    // 栈初始化，即构造一个空栈，成功返回OK，失败返回ERROR
    int InitStack(SqStack *pS);
    
    // 销毁堆栈，成功返回OK，失败返回ERROR
    int DestroyStack(SqStack *pS);
    
    // 判断是否为空栈，是空栈返回TRUE，不是空栈返回FALSE
    int StackEmpty(SqStack *pS);
    
    // 返回栈顶元素，成功返回OK，失败返回ERROR
    int GetTop(SqStack *pS, SElemType *pE);
    
    // 入栈，即插入元素至栈顶，成功返回OK，失败返回ERROR
    int Push(SqStack *pS, SElemType *pE);
    
    // 出栈，即删除元素从栈顶，成功返回OK，失败返回ERROR
    int Pop(SqStack *pS, SElemType *pE);
    
    // 从栈底到栈顶进行遍历，打印栈的元素，成功返回OK，失败返回ERROR
    int StackTraverse(SqStack *pS, void (*Visit)());
    
    #endif // SQ_STACK_H_INCLUDED

// Filename: sq_stack.c
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "sq_stack.h"
    
    // 栈初始化，即构造一个空栈，成功返回OK，失败返回ERROR
    int InitStack(SqStack *pS)
    {
        if (!pS) return ERROR;
    
        pS->base = (SElemType *)malloc(sizeof(SElemType) * STACK_INIT_SIZE);
        if (!pS->base) return ERROR;
        pS->top = pS->base;
        pS->stacksize = STACK_INIT_SIZE;
    
        return OK;
    }
    
    // 销毁堆栈，成功返回OK，失败返回ERROR
    int DestroyStack(SqStack *pS)
    {
        if (!pS) return ERROR;
        free(pS->base);
        return OK;
    }
    
    // 判断是否为空栈，是空栈返回TRUE，不是空栈返回FALSE
    int StackEmpty(SqStack *pS)
    {
        if (!pS) return TRUE;
        if (pS->top == pS->base) return TRUE;
        return FALSE;
    }
    
    // 返回栈顶元素，成功返回OK，失败返回ERROR
    int GetTop(SqStack *pS, SElemType *pE)
    {
        if (!pS || !pE) return ERROR;
        if (StackEmpty(pS)) return ERROR;
        *pE = *(pS->top - 1);
        return OK;
    }
    
    // 入栈，即插入元素至栈顶，成功返回OK，失败返回ERROR
    int Push(SqStack *pS, SElemType *pE)
    {
        if (!pS || !pE) return ERROR;
    
        // 栈满则扩充存储空间
        if (pS->top - pS->base >= pS->stacksize)
        {
            pS->base = (SElemType *)realloc(pS->base, pS->stacksize + sizeof(SElemType) * STACK_INCREMENT);
            if (!pS->base) exit(1);
            pS->top = pS->base + pS->stacksize;
            pS->stacksize += STACK_INCREMENT;
        }
    
        *pS->top = *pE;
        pS->top++;
    
        return OK;
    }
    
    // 出栈，即删除元素从栈顶，成功返回OK，失败返回ERROR
    int Pop(SqStack *pS, SElemType *pE)
    {
        if (!pS || !pE) return ERROR;
    
        // 栈空则返回失败
        if (StackEmpty(pS)) return ERROR;
    
        pS->top--;
        *pE = *(pS->top);
    
        return OK;
    }
    
    // 从栈底到栈顶进行遍历，对栈的元素调用访问函数Visit()，成功返回OK，失败返回ERROR
    int StackTraverse(SqStack *pS, void (*Visit)())
    {
        if ((!pS) || (!Visit)) return ERROR;
    
        // 栈空则提示返回
        if (StackEmpty(pS)) printf("空栈\n");
    
        SElemType *p = NULL;
        for (p = pS->base; p < pS->top; p++)
        {
            (*Visit)(p);
        }
    
        return OK;
    }

[Center]: /images/20220810/b50ecd16c85e4d32ac64a32947320414.png