数据结构：顺序栈

这是严蔚敏吴伟民版本的算法，感觉没《大话数据结构》里面的简单易懂

这个版本里面的top指针指向下一个空单元格，这个其实是有些问题的，因为栈满的时候，top是指向栈外的，有些不安全。

#ifndef SQ_STACK_HEAD
#define SQ_STACK_HEAD
#include <stdio.h>
#include <stdlib.h>
#define Status int
#define OVERFLOW -1
#define OK 0
#define ERROR 1
#define MAX_SIZE 100    //初始容量
#define STEP_SIZE 5     //容量增长步长
typedef int ElemType;

typedef struct{
    ElemType *base;     //栈底，这个是不变的
    ElemType *top;      //栈顶，指向下一个空单元，所以取栈顶元素要用*(top-1)
    int size;           //当前栈容量上限
} SqStack;

/* 栈初始化
 * 1.申请栈区
 * 2.top和base指针同时指向第一个单元
 */
Status init(SqStack *s)
{
    s->size = MAX_SIZE;
    s->base = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));
    if (s->base == NULL) return OVERFLOW;   //分配失败
    s->top = s->base;   //s->top指向下一个新单元
    return OK;
}

/*
 * 销毁栈
 * 1.释放栈区域
 * 2.base和top指针置空
 */
Status destroy(SqStack *s)
{
    if (s->base == NULL) {
        s->top = NULL;
        return ERROR;
    }
    free(s->base);
    s->top = s->base = NULL;
    s->size = 0;
    return OK;
}

/* 入栈
 * 1.如果栈已满，则realloc()
 * 2.将新元素写入top指向的单元
 * 3.top向上移动一格
 */
Status push(SqStack *s, ElemType e)
{
    ElemType *new_base;
    if (s->top - s->base >= s->size) {//如果栈已满，注意测试边界值
        /* 注意一下这里，之所以要多用一个new_base，是因为如果写成：
         * s->base = realloc(s->base, new_size)
         * 此时如果realloc()失败则s->base之前指向的地址会丢失而不可控
         */
        new_base = (ElemType *)realloc(s->base, (s->size + STEP_SIZE) * sizeof(ElemType));
        if (new_base == NULL) {
            return OVERFLOW;
        }
        s->base = new_base;
        s->top = s->base + s->size;
        s->size += STEP_SIZE;
        new_base = NULL;
    }
    *s->top++ = e;//由于s->top指向的是空单元，所以直接将e写入，然后s->top移动一格
    return OK;
}

/*
 * 出栈
 * 1.top向下退一格
 * 2.取top指向的值
 */
Status pop(SqStack *s, ElemType *e)
{
    if (s->top == s->base) return ERROR;//空栈或者已经被销毁
    *e = *--s->top;//s->top指向的是空单元，所以要先移动s->top才能取值
    return OK;
}

/* 取栈顶值:取top下一格的值 */
Status getTop(SqStack s, ElemType *e)
{
    if (s.top == s.base) return ERROR;
    *e = *(s.top - 1);//s->top指向的是空单元，所以s->top下一格才是栈顶元素
    return OK;
}

#endif

 

优化后的算法：

#ifndef SQ_STACK_HEAD
#define SQ_STACK_HEAD
#include <stdio.h>
#include <stdlib.h>
#define Status int
#define OVERFLOW -1
#define OK 0
#define ERROR 1
#define MAX_SIZE 10    //初始容量
#define STEP_SIZE 5     //容量增长步长
typedef int ElemType;

typedef struct{
    ElemType *base;     //栈底，这个是不变的
    ElemType *top;      //栈顶，指向最后一个单元格
    int size;           //当前栈容量上限
} SqStack;

/* 栈初始化
 * 1.申请栈区
 * 2.top置空
 */
Status init(SqStack *s)
{
    s->size = MAX_SIZE;
    s->base = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));
    if (s->base == NULL) return OVERFLOW;   //分配失败
    s->top = NULL;
    return OK;
}

/*
 * 销毁栈
 * 1.释放栈区域
 * 2.base和top指针置空
 */
Status destroy(SqStack *s)
{
    s->top = NULL;
    if (s->base == NULL) {
        return ERROR;
    }
    free(s->base);
    s->base = NULL;
    s->size = 0;
    return OK;
}

/* 入栈
 * 1.如果栈已满，则realloc()
 * 2.top向上移动一格
 * 3.将新元素写入top指向的单元
 */
Status push(SqStack *s, ElemType e)
{
    ElemType *new_base;
    if (s->top - s->base >= s->size - 1) {//如果栈已满，注意测试边界值
        new_base = (ElemType *)realloc(s->base, (s->size + STEP_SIZE) * sizeof(ElemType));
        if (new_base == NULL) {
            return OVERFLOW;
        }
        s->base = new_base;
        s->top = s->base + (s->size - 1);
        s->size += STEP_SIZE;
        new_base = NULL;
    }
    if (s->top == NULL)
        s->top = s->base;
    else
        s->top++;
    *s->top = e;
    return OK;
}

/*
 * 出栈
 * 1.取top指向的值
 * 2.top向下退一格
 */
Status pop(SqStack *s, ElemType *e)
{
    if (s->top == NULL) return ERROR;//空栈或者已经被销毁
    *e = *s->top--;
    return OK;
}

/* 取栈顶值:取top下一格的值 */
Status getTop(SqStack s, ElemType *e)
{
    if (s.top == s.base) return ERROR;
    *e = *s.top;//s->top指向的是空单元，所以s->top下一格才是栈顶元素
    return OK;
}
#endif

 

《大话数据结构》中的算法，简单易懂，就是把栈当数组用

#ifndef SQ_STACK_HEAD
#define SQ_STACK_HEAD
#include <stdio.h>
#include <stdlib.h>
#define Status int
#define OVERFLOW -1
#define OK 0
#define ERROR 1
#define STACK_INIT_SIZE 100    //初始容量
#define STEP_SIZE 5     //容量增长步长
typedef int ElemType;

/*
 * 注意跟上面算法的区别
 * 主要是top指针不一样
 * 这个版本更简单易懂
 */
typedef struct{
    ElemType *data;     //栈底，这个是不变的
    int top;            //栈顶，指向最后一个元素
    int size;           //当前栈容量上限
} SqStack;

/* 栈初始化
 * 1.申请栈区,data当成数组使用
 * 2.top=-1，现在栈空所以只能指向-1
 */
Status init(SqStack *s)
{
    s->size = STACK_INIT_SIZE;
    s->data = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (s->data == NULL) return OVERFLOW;   //分配失败
    s->top = -1;
    return OK;
}

/*
 * 销毁栈
 * 1.释放栈区域
 * 2.data指针置空, top置为-1
 */
Status destroy(SqStack *s)
{
    s->top = -1;
    if (s->data == NULL) return ERROR;
    free(s->data);
    s->data = NULL;
    s->size = 0;
    return OK;
}

/* 入栈
 * 1.如果栈已满，则realloc()
 * 2.top上移
 * 3.将新元素写入top指向的单元
 */
Status push(SqStack *s, ElemType e)
{
    ElemType *new_data;
    if (s->top == s->size - 1) {//如果栈已满，注意测试边界值
        new_data = (ElemType *)realloc(s->data, (s->size + STEP_SIZE) * sizeof(ElemType));
        if (new_data == NULL) {
            return OVERFLOW;
        }
        s->data = new_data;
        s->size += STEP_SIZE;
        new_data = NULL;
    }
    s->data[++s->top] = e;//top先移动到下一个空单元，然后再将e写入
    return OK;
}

/*
 * 出栈
 * 1.取top指向的值
 * 2.top后退一格
 */
Status pop(SqStack *s, ElemType *e)
{
    if (s->top == -1) return ERROR;//空栈或者已经被销毁
    *e = s->data[s->top--];
    return OK;
}

/* 取栈顶值:top指向的值 */
Status getTop(SqStack s, ElemType *e)
{
    if (s.top == -1) return ERROR;
    *e = s.data[s.top];
    return OK;
}

#endif