数据结构-栈(c顺序实现)

1.什么是栈？
栈(stack)是仅限于在表尾进行插入或删除操作的线性表，表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈又被成为后进先出的线性表。
2. 栈的顺序实现

/*
    时间：2012年3月10日 23:19:11
    目的：学习c语言，学习数据结构
    功能：栈的顺序实现
*/

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 5

typedef int Status;

typedef int SElemType;

typedef struct Stack
{
    SElemType * base;    //栈底指针
     SElemType * top;    //栈顶指针
    int stacksize;        //当前已分配的存储空间，已元素为单位
} SqStack;

Status InitStack(SqStack *s);

void DestroyStack(SqStack *s);

void ClearStack(SqStack *s);

Status StackEmpty(SqStack *s);

int StackLength(SqStack *s);

Status GetTop(SqStack *s, SElemType *e);

Status Push(SqStack *s, SElemType *e);

Status Pop(SqStack *s, SElemType *e);

void StackTraverse1(SqStack *s);

Status InitStack(SqStack *s)
{
    s->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (NULL == s->base)
    {
        printf("内存分配失败，程序退出\n");
        exit(-1);
    }
    s->top = s->base; //空栈的标志：栈顶指针 = 栈底指针
    s->stacksize = STACK_INIT_SIZE;

    return OK;
}

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

//置空顺序栈
void ClearStack(SqStack *s)
{
    s->top = s->base;
}

//判断栈是否为空
Status StackEmpty(SqStack *s)
{
    if (s->top == s->base) //这里不要将==写成=号了。。。
        return TRUE;
    else
        return FALSE;
}

//栈中元素个数
int StackLength(SqStack *s)
{
    return (s->top - s->base);
}

//获取栈顶元素，用e返回其值
Status GetTop(SqStack *s, SElemType *e)
{
    SElemType *p = s->top;
    if (StackEmpty(s))
    {
        printf("栈为空\n");
        return ERROR;
    }
    *e = *(--p); //这里不能写成 *e = *(p--);
    return OK;
}

//将元素e压栈，成为新的栈顶元素
Status Push(SqStack *s, SElemType e)
{
    //判断栈是否已满
    if (s->top - s->base >= STACK_INIT_SIZE)
    {
        SElemType *newbase = (SElemType *)realloc(s->base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));
        if (NULL == newbase)
        {
            printf("内存增加失败,程序退出\n");
            exit(-1);
        }
        s->base = newbase;
        s->top = s->base + s->stacksize;
        s->stacksize += STACKINCREMENT;
    }
    *(s->top) = e;
    s->top++;

    return OK;
}

//删除s的栈顶元素，并用e返回其值
Status Pop(SqStack *s, SElemType *e)
{
    if (StackEmpty(s))
    {
        printf("栈为空\n");
        return ERROR;
    }

    SElemType *p = s->top;
    *e = *--p; ////这里不能写成 *e = *p--;
    s->top--;

    return OK;
}
void StackTraverse1(SqStack *s)
{
    SElemType *q = s->top; //遍历操作后，不能改变top指针所指位置
    while (q - s->base > 0)
    {
        //q--;
        printf("%d ", *--q); //--运算符优先级高于*,这里用前置--
    }
    printf("\n");
}


int main()
{
    SqStack s;
    SElemType e;
    //初始化栈
    if (InitStack(&s))
    {
        printf("--->初始化栈完成\n");
    }
    else
    {
        printf("初始化栈失败,程序退出\n");
        exit(-1);
    }

    //入栈
    printf("--->创建栈\n");
    Push(&s, 2);
    Push(&s, 4);
    Push(&s, 5);
    Push(&s, 7);
    Push(&s, 9);
    printf("--->栈中元素个数为: %d\n", StackLength(&s));
    StackTraverse1(&s);

    printf("--->清空栈\n");
    ClearStack(&s);
    printf("--->栈中元素个数为: %d\n", StackLength(&s));

    printf("--->构造新栈\n");
    Push(&s, 1);
    Push(&s, 3);
    Push(&s, 5);
    Push(&s, 7);
    Push(&s, 9);
    Push(&s, 11);
    StackTraverse1(&s);
    printf("--->栈中元素个数为: %d\n", StackLength(&s));


    //获取栈顶元素
    if (GetTop(&s, &e))
    {
        printf("有栈顶，栈顶值为: %d\n", e);
    }
    else
    {
        printf("空栈,没有栈顶元素\n");
    }
    StackTraverse1(&s);

    //出栈

    while (s.top - s.base > 0)
    {
        if (Pop(&s, &e))
        {
            printf("栈顶元素出栈成功, 栈顶元素为: %d\n", e);
        }
        else
        {
            printf("空栈,没有栈顶元素\n");
        }
    }

    StackTraverse1(&s);

    DestroyStack(&s);

    return 0;
}