学步园

        栈是一种重要的数据结构，栈其实也是一种线性表，但是它只能在表尾进行插入和删除。

        栈其实就是记录线性表的起始跟结尾，以及表的容量的数据结构。

        例如定义一个栈的结构体：

typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

         结构中base指向线性表的表头元素，top指向线性表表尾元素，而stacksize记录栈的大小， 线性表有两种实现（顺序存储和链式存储），同样对应于栈也有相应的两种实现 方式，本文要实现的是顺序栈。

         下面是具体的代码：

         头文件stack.h

#ifndef __STACK_H__
#define __STACK_H__

#define STACK_INIT_SIZE      10
#define STACK_INCREMENT    5

#define TRUE      1
#define FALSE    0

typedef int bool;

typedef int SElemType;

typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;


typedef enum
{
    OVERFLOW=-2,
    EXIT_ERR=-1,
    EXIT_OK   
}Status;


#endif

       实现stack.c

/*
* Copyright (c)  2013
* This is a sample code of stack with C, every one can mody, distribute it.
*
* File Name     : stack.c
* Description   : Implement stack with C.
*
* Version        : Ver0.1
* Author         : Mingqiu.Zhang <zhang_mq@sina.com>
* Date            : 2013-03-04
*/

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

Status InitStack(SqStack *s)
{
    s->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

    if(NULL == s->base)
    {
        return OVERFLOW;
    }

    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
    
    return EXIT_OK;
}


Status DestroyStack(SqStack *s)
{
    if(s->base !=NULL)
        free(s->base);

    s->top = s->base = NULL;
    s->stacksize = 0;

    return EXIT_OK;
}

Status ClearStack(SqStack *s)
{   
    if(s->top !=s->base)
    {
        memset(s->base, 0, (s->stacksize)*sizeof(SElemType));
        s->top = s->base;
    }

    return EXIT_OK;
}

bool StackEmpty(SqStack s)
{
    if(s.top == s.base)
        return TRUE;
    else
        return FALSE;
}

int StackLength(SqStack s)
{
    if((s.base != NULL) && (s.top != NULL))
        return s.top-s.base;
    else
        return EXIT_ERR;
}

Status GetTop(SqStack s, SElemType *e)
{
    if(s.base == s.top)
        return EXIT_ERR;

    *e =*(s.top-1);
    return EXIT_OK;
}


Status Push(SqStack *s, SElemType e)
{
    if(((s->top)-(s->base))/sizeof(SElemType) >= s->stacksize)
    {
        s->base = (SElemType *)realloc(s->base, (s->stacksize+STACK_INCREMENT)*sizeof(SElemType));

        if(NULL == s->base)
            return OVERFLOW;

        s->top = s->base+s->stacksize;
        s->stacksize+=STACK_INCREMENT;
    }

    *((s->top)++) = e;
}


Status Pop(SqStack *s, SElemType *e)
{
    if(s->top == s->base)
        return EXIT_ERR;
    
    *e=*(--(s->top));
    return EXIT_OK;
}


void visit(SElemType e)
{
    printf("%6d", e);
}

Status StackTraverse(SqStack s,  void (*f)(SElemType))
{
    while(s.top > s.base)
    {
        (s.top)--;
        f(*(s.top));
    }

    return EXIT_OK;
}




int main()
{
    int i;
    SElemType tmp;
    Status res;
    SqStack s;

    res = InitStack(&s);
    if(res != EXIT_OK)
    {
        printf("Initialize stack fail. \n");
        return res;
    }

    for(i=0; i<15; i++)
    {
        Push(&s, (SElemType)i);
    }
    printf("Members after push:\n");
    StackTraverse(s, visit);
    printf("\nCurrent the length of stack is %d.\n", StackLength(s));

    for(i=0; i<5; i++)
    {
        Pop(&s, &tmp);
        printf("Element %d is poped.\n", tmp);
    }

    printf("Members after pop:\n");
    StackTraverse(s, visit);
    printf("\nCurrent the length of stack is %d.\n", StackLength(s));

    GetTop(s, &tmp);
    printf("Now the top element is %d\n", tmp);

    res = DestroyStack(&s);
    if(res != EXIT_OK)
    {
        printf("Destroy Stack fail.\n");
        return res;
    }
    
    return 0;
}

上述代码在linux下可以正确的编译运行，下图是运行结果：

代码注释后续会加上