「数据结构四」C 语言实现栈

栈（stack）是限定在表尾进行插入或删除操作的线性表。因此，栈的表尾端具有特殊的含义，称为栈顶（top），相对应，表头端的称为栈底（bottom）。

为什么称之为特殊的线性表，它的特殊之处在于只能允许在栈的顶端加入数据（push）和输出数据（pop）。由于它是特殊的线性表，所以我们可以实现顺序结构的栈和链式结构的栈。

顺序栈

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，同时设置 top 指针指向栈顶元素。

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

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 2

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE 0

typedef int Status;
typedef int SElemType;

typedef struct {
    SElemType *base;  //栈底指针
    SElemType *top;  //栈顶指针
    int stackSize;
}SqStack;

Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status 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);
Status StackTraverse(SqStack S, void(*vi)(SElemType));

/**
 * 操作结果：构造一个空栈 S。
 * @param S
 * @return
 */
Status InitStack(SqStack *S) {
    S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SqStack));  //开辟内存空间
    if (!S->base) {
        exit(OVERFLOW);  //开辟失败
    }
    S->top = S->base;
    S->stackSize = STACK_INIT_SIZE;
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：栈 S 被销毁
 * @param S
 * @return
 */
Status DestroyStack(SqStack *S) {
    if (S->base) {
        free(S->base);  //释放栈底指针内存空间
    }
    S->top = S->base = NULL;  //栈底栈顶指针置为 NULL
    S->stackSize = 0;
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：将栈 S 清为空栈
 * @param S
 * @return
 */
Status ClearStack(SqStack *S) {
    S->top = S->base;
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：若 S 为空栈，返回 true，否则返回 false
 * @param S
 * @return
 */
Status StackEmpty(SqStack S) {
    if (S.top == S.base) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：返回 S 中元素的个数，即栈的长度
 * @param S
 * @return
 */
int StackLength(SqStack S) {
    return (int) (S.top - S.base);
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果：返回栈顶元素，不修改栈顶指针
 * @param S
 * @return
 */
Status GetTop(SqStack S, SElemType *e) {
    if (S.top != S.base) {
        *e = *(S.top - 1);
        return OK;
    }
    return ERROR;

}

/**
 * 初始条件：栈 S 存在
 * 操作结果：插入元素 e 为新的栈顶元素
 * @param S
 * @param e
 * @return
 */
Status Push(SqStack *S, SElemType e) {
    if ((S->top - S->base) >= S->stackSize) { //判读栈是否满
        S->base = (SElemType *)realloc(S->base, (S->stackSize + STACK_INCREMENT) * sizeof(SqStack));
        if (!S->base) {
            return ERROR;
        }
        S->top = S->base + S->stackSize;
        S->stackSize += STACK_INCREMENT;
    }
    *S->top++ = e;
    return OK;
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果：删除 S 的栈顶元素，并用 e 返回其值
 * @param S
 * @param e
 * @return
 */
Status Pop(SqStack *S, SElemType *e) {
    if (S->top == S->base) {  //栈为空
        return ERROR;
    }
    *e = *--S->top;
    return OK;
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果：从栈底到栈顶依次对 S 的每个元素进行访问
 * @param S
 * @param vi
 */
Status StackTraverse(SqStack S, void(*vi)(SElemType)) {
    while (S.top > S.base) {  //遍历栈中元素
        vi(*S.base++);
    }
    printf("\n");
    return OK;
}

/**
 * 遍历函数
 * @param e
 */
void vi(SElemType e) {
    printf("%d ", e);
}

/**
 * 主函数，测试程序
 * @return
 */
int main() {
    SqStack s;
    SElemType e;

    InitStack(&s);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));
    Push(&s, 3);
    Push(&s, 4);
    Push(&s, 5);
    Push(&s, 6);
    StackTraverse(s,vi);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));
    GetTop(s, &e);
    printf("栈顶元素：%d\n", e);
    printf("栈的长度：%d\n", StackLength(s));
    Pop(&s, &e);
    StackTraverse(s, vi);
    ClearStack(&s);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));

    DestroyStack(&s);
}

上面测试代码在 Clion 下的执行结果如下图所示。

链式栈

链栈是采用链式存储结构实现的栈。

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE 0

typedef int Status;
typedef int SElemType;

typedef struct StackNode {
    SElemType data;  //数据域
    struct StackNode *next;  //指针域
}StackNode, *LinkStack;

Status InitStack(LinkStack *S);
Status DestroyStack(LinkStack *S);
Status ClearStack(LinkStack *S);
Status StackEmpty(LinkStack S);
int StackLength(LinkStack S);
Status GetTop(LinkStack S, SElemType *e);
Status Push(LinkStack *S, SElemType e);
Status Pop(LinkStack *S, SElemType *e);
void StackTraverse(LinkStack S, void(*vi)(SElemType));

/**
 * 操作结果：构造一个空栈 S
 * @param L
 * @return
 */
Status InitStack(LinkStack *S) {
    S = NULL;  //构造一个空栈，栈顶指针置空
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：栈 S 被销毁
 * @param S
 * @return
 */
Status DestroyStack(LinkStack *S) {
    LinkStack p;
    while (*S) {  //未到栈底
        p = (*S)->next;
        free(*S);  //释放栈顶空间
        *S = p;
    }
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：将栈 S 清空
 * @param S
 */
Status ClearStack(LinkStack *S) {
    LinkStack q, p = (*S)->next;  // p 指向栈顶元素
    while (p) {  //未到栈底
        q = p->next;
        free(p);
        p = q;
    }
    (*S) = NULL;
    return OK;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：若 S 是空栈，返回 true，否则返回 false
 * @param S
 * @return
 */
Status StackEmpty(LinkStack S) {
    if (S == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：返回栈 S 长度
 * @param S
 * @return
 */
int StackLength(LinkStack S) {
    int i = 0;  //计数器
    LinkStack p = S;  //p指向栈顶元素
    while (p) {  //未到栈底
        i++;
        p = p->next;
    }
    return i;
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果；用 e 返回栈 S 的栈顶元素，不修改栈顶指针
 * @param S
 * @return
 */
Status GetTop(LinkStack S, SElemType *e) {
    if (S) {  //S 非空
        *e = S->data;
        return OK;
    }
    return ERROR;
}

/**
 * 初始条件：栈 S 存在
 * 操作结果：插入元素 e 为新的栈顶元素
 * @param L
 * @param e
 * @return
 */
Status Push(LinkStack *S, SElemType e) {
    LinkStack p;
    p = (LinkStack)malloc(sizeof(struct StackNode));  //生成新结点
    p->data = e;
    p->next = *S;  //将新结点插入栈顶
    *S = p;  //修改栈顶指针
    return OK;
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果：删除栈顶元素，并用 e 返回且值
 * @param S
 * @param e
 * @return
 */
Status Pop(LinkStack *S, SElemType *e) {
    LinkStack p;
    if (!S) {
        return ERROR;
    }
    *e = (*S)->data;  //返回栈顶元素
    p = *S;  //p 临时保存栈顶空间，以备释放
    *S = (*S)->next;  //修改栈顶指针
    free(p);  //释放原栈栈顶空间
    return OK;
}

/**
 * 初始条件：栈 S 存在且非空
 * 操作结果：从栈底到栈顶依次对 S 中的每个元素进行访问
 * @param S
 * @param vi
 */
void StackTraverse(LinkStack S, void(*vi)(SElemType)) {
    LinkStack p = S;  //p 指向栈顶
    while (p) {
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}

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

/**
 * 主函数，测试程序
 * @return
 */
int main() {
    LinkStack s = NULL;
    SElemType e;

    InitStack(&s);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));
    Push(&s, 3);
    Push(&s, 4);
    Push(&s, 5);
    Push(&s, 6);
    StackTraverse(s,vi);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));
    GetTop(s, &e);
    printf("栈顶元素：%d\n", e);
    printf("栈的长度：%d\n", StackLength(s));
    Pop(&s, &e);
    StackTraverse(s, vi);
    ClearStack(&s);
    printf("栈的长度：%d\n", StackLength(s));
    printf("栈是否为空：%d\n", StackEmpty(s));

    DestroyStack(&s);
}

具体运行效果和顺序栈运行效果一样。

想要查看源码可以访问下面 github 链接，如果觉得不错，请给个 Star。

顺序栈
 链式栈

本文属数据结构系列持续更新中。

最后编辑于：2017.12.07 03:48:57

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,324评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,303评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,192评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,555评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,569评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,566评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,927评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,583评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,827评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,590评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,669评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,365评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,941评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,928评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,159评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,880评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,399评论 2赞 342

「数据结构 四」C 语言实现栈

顺序栈

链式栈

推荐阅读更多精彩内容

「数据结构四」C 语言实现栈