stack.c

经典迷宫算法

// file: stack.c
#include "stack.h"
#include "malloc.h"

// 构造一个空栈
bool InitStack(SqStack *S)
{
    S->base = (SELEM_TYPE *)malloc(STACK_INIT_SIZE* sizeof(SELEM_TYPE));

    if (!S->base)
        return false;

    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return true;
}

// 销毁栈
void DestroyStack(SqStack *S) {free(S->base);S->base = S->top = 0;S->stacksize = 0;}

// 把S置为空栈
void ClearStack(SqStack *S) {S->top = S->base;}

// 判断栈是否为空
bool StackEmpty(SqStack *S) {return (S->top == S->base);}

// 返回栈的长度
int StackLength(SqStack *S) {return S->top - S->base;}

// 若栈不空，用e返回S的栈顶元素
bool GetTop(SqStack *S, SELEM_TYPE *e) 
{
    if (StackEmpty(S) || e==0)
        return false;
    
    *e = *(S->top-1);
    return true;
} 

// 将e压至栈顶
bool Push(SqStack *S, SELEM_TYPE e)
{
    if (S->top-S->base >= S->stacksize)
    {
        S->base = (SELEM_TYPE *)realloc(S,(S->stacksize + STACKINCREMENT) * sizeof(SELEM_TYPE) );
        if (!S->base) 
            return false;
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }

    *(S->top++) = e;
    return true;
}

// 删除栈顶元素，并以e返回
bool Pop(SqStack *S, SELEM_TYPE *e)
{
    if (StackEmpty(S))
        return false;

    if (e != 0)
        *e = *--S->top;
    else
        S->top--;
    return true;
}

// 从栈顶到栈底（也可以栈底到栈顶）每个元素调用函数visit
// 加入方向direction，true：从底到顶 ，false：从顶到底
bool StackTraverse(SqStack *S, bool (*visit)(SELEM_TYPE e) , bool direction)
{
    SELEM_TYPE *pe = 0;

    if (StackEmpty(S))
        return false;

    if(direction)
    {
        pe = S->base;
        while(pe < S->top)
        {
            if (!visit(*pe++))return false;
        }
    }
    else
    {
        pe = S->top;
        while(pe >= S->base)
        {
            if (!visit(*--pe))return false;
        }
    }

    return true;
}