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

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

代码实现如下：

// 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;
}

秒客网

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

相关文章