데이터 구조 3.1 - 스 택 의 선형 표시

//stack.h
#pragma once

#ifndef _STACK
#define _STACK

//        
#define STACK_INIT_SIZE 100
//        
#define STACKINCREMENT 10

//     
#define TRUE 1
#define FALSE 0

typedef struct
{
    int *base;
    int *top;
    int nStackSize;
}sqStack;

//   
int initStack(sqStack &);

//   
int destroyStack(sqStack &);

//   
int clearStack(sqStack &);

//       
int isStackEmpty(sqStack);

//      
int getTop(sqStack, int &);

//   
int push(sqStack &, int);

//  
int pop(sqStack &, int &);

//      
int getStackLength(sqStack, int &);


#endif // !_STACK

//stack.cpp
#include "stack.h"
#include <stdlib.h>
#include <string.h>

//   
int initStack(sqStack &S)
{
    //          
    S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
    if (!S.base)
        return FALSE;

    //         
    S.top = S.base;
    S.nStackSize = STACK_INIT_SIZE;
    return TRUE;
}

//   
int destroyStack(sqStack &S)
{
    memset(S.top, 0x00, S.nStackSize);
    S.top = NULL;
    S.base = NULL;
    S.nStackSize = 0;
    return TRUE;
}

//   
int clearStack(sqStack &S)
{
    memset(S.top, 0x00, S.nStackSize);
    S.base = S.top;
    S.nStackSize = 0;
    return TRUE;
}

//       
int isStackEmpty(sqStack S)
{
    //        
    if (S.top && S.top == S.base)
        return TRUE;
    return FALSE;
}

//      
int getTop(sqStack S, int &nElem)
{
    //     ，      ，   OK，    FALSE
    if (S.top == S.base)
        return FALSE;
    nElem = *(S.top - 1);
    return TRUE;
}

//  
int push(sqStack &S, int nElem)
{
    //    ，      
    if (S.top - S.base >= S.nStackSize)
    {
        S.base = (int *)realloc(S.base, (S.nStackSize + STACKINCREMENT) * sizeof(int));
        //    
        if (!S.base)
            return FALSE;

        S.top = S.base + S.nStackSize;
        S.nStackSize += STACKINCREMENT;
    }
    *S.top++ = nElem;
    return TRUE;
}

//  
int pop(sqStack &S, int &nElem)
{
    //   ，   S     
    if (S.top == S.base)
        return FALSE;

    nElem = *--S.top;
    return TRUE;
}

//      
int getStackLength(sqStack S, int &nLength)
{
    //       FALSE
    if (S.top == S.base)
        return FALSE;
    nLength = S.nStackSize;
    return TRUE;
}

//main.cpp
//    
#include "stack.h"
#include <iostream>

using std::cout;
using std::endl;

typedef int BOOL;

int main()
{
    int nNum = 15;
    //    
    sqStack S;
    BOOL bRet = initStack(S);

    //      
    bRet = isStackEmpty(S);
    if (bRet)
        cout << "   ！" << endl;
    else
        cout << "   ！" << endl;

    //     
    for (int i = 0; i < nNum; ++i)
    {
        bRet = push(S, i);
        if (!bRet)
            break;
    }
    if (bRet)
    {
        //    
        for (int *p = S.base, i = 0; p < S.top; ++p, ++i)
            cout << "  " << i << ":" << *p << endl;
    }

    //      
    int nElem = 0;
    bRet = pop(S, nElem);
    //    
    if (bRet)
        cout << "       " << nElem << endl;

    //   
    bRet = clearStack(S);
    if (bRet)
        cout << "     " << endl;

    return 0;
        
}