专栏首页开发与安全数据结构:栈的链式存储结构

数据结构:栈的链式存储结构

单链表限定只能在头部进行插入和删除操作的时候,即为链栈,一般我们会将单链表的头指针和栈的栈顶指针top合二为一,通常对链栈来说,是不需要头节点的,因为我们维护了栈顶指针。对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间,对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是top = = NULL的时候。

示例代码:(改编自《大话数据结构》)

#include <iostream>
using namespace std;

typedef int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node *next;

} Node, *NodePtr;

typedef struct LinkStack
{
    NodePtr top; //栈顶指针
    int count; //元素个数
} LinkStack;
/*  构造一个空栈 */
bool InitStack(LinkStack *ps)
{
    cout << "Init Stack ..." << endl;
    ps->top = NULL;
    ps->count = 0;
    return true;
}
/*置为空栈 */
bool ClearStack(LinkStack *ps)
{
    cout << "Clear Stack ..." << endl;
    if (ps->top == NULL)
        return true;
    NodePtr p = ps->top;
    NodePtr q;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    ps->top = NULL;
    ps->count = 0;
    return true;
}

bool StackEmpty(LinkStack LS)
{
    return LS.count == 0;
}

int StackLength(LinkStack LS)
{
    cout << "Stack Length: ";
    return LS.count;
}
/* 返回栈顶元素 */
bool GetTop(LinkStack LS, ElemType *pe)
{
    *pe = LS.top->data;
    cout << "Get Top Item " << *pe << endl;
    return true;
}
/* 压栈 */
bool Push(LinkStack *ps, ElemType Elem)
{
    cout << "Push Item " << Elem << endl;
    NodePtr s = (NodePtr)malloc(sizeof(Node));
    s->data = Elem;
    s->next = ps->top;
    ps->top = s;
    ps->count++;
    return true;
}
/* 出栈 */
bool Pop(LinkStack *ps, ElemType *pe)
{
    NodePtr p = ps->top;
    *pe = p->data;
    ps->top = p->next;
    free(p);
    ps->count--;
    cout << "Pop Item " << *pe << endl;
    return true;
}
/* 输出栈元素 */
bool StackTraverse(LinkStack LS)
{
    cout << "Stack Traverse ..." << endl;
    NodePtr p = LS.top;
    while (p != NULL)
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
    return true;
}

int main(void)
{
    LinkStack LS;
    InitStack(&LS);
    for (int i = 0; i < 5; i++)
        Push(&LS, i);
    StackTraverse(LS);
    int result;
    GetTop(LS, &result);
    Pop(&LS, &result);
    StackTraverse(LS);
    if (!StackEmpty(LS))
        cout << StackLength(LS) << endl;
    ClearStack(&LS);
    StackTraverse(LS);

    return 0;
}

输出为:

如果栈的使用过程中元素变幻不可预料,有时很小,有时非常大,那么最好使用链栈,反之如果变化在可控范围内,建议使用顺序栈会更好一些。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • linux系统编程之基础必备(五):Linux进程地址空间和虚拟内存

    一、虚拟内存 先来看一张图(来自《Linux内核完全剖析》),如下: ? 分段机制:即分成代码段,数据段,堆栈段。每个内存段都与一个特权级相关联,即0~...

    s1mba
  • 浅谈网络数据包传递过程中涉及的话题

    概括来说:首先我们在浏览器地址栏敲下域名地址,浏览器发出get请求,接下来进行dns域名解析(后面再详谈),此时浏览器已经得知目标IP,此时还得知道默认网关的m...

    s1mba
  • 80386的分段机制、分页机制和物理地址的形成

    注:本分类下文章大多整理自《深入分析linux内核源代码》一书,另有参考其他一些资料如《linux内核完全剖析》、《linux c 编程一站式学习》等,只是为了...

    s1mba
  • SpringBoot 开发秘籍 - 启动时配置校验

    在项目开发过程中,某个功能需要依赖在配置文件中配置的参数。这时候就可能出现下面这种现象问题:

    JAVA日知录
  • [816]python之pprint

    pprint提供了以一种“pretty-print”的方式打印出任意python数据结构的模块。当然,如果不是python的基本数据类型,那么这种方式可能加载不...

    周小董
  • IOS UILabel 长字符串处理

    label.lineBreakMode =NSLineBreakMode.byTruncatingMiddle label.numberOfLines = 0...

    用户5760343
  • 专家点评 | 【Google 年度顶级论文】机器学习系统,隐藏多少技术债?

    作者在看完新智元12月8日文章《【Google 年度顶级论文】机器学习系统,隐藏多少技术债?》后有感而发,特作此文。 我: 真的好文。象牙塔里出不来的经验总结。...

    新智元
  • 【六一特稿】为什么人会随着长大变“聪明”:儿童认知能力的大脑神经网络基础

    【新智元导读】大脑的“ 执行功能” 对于个人的发展来说事关重大,宾夕法尼亚大学 Perelman 医学院的研究,发现了人脑中影响这些“执行功能”提升的大脑网络组...

    新智元
  • Spark RDD Map Reduce 基本操作

    RDD是Spark中的抽象数据结构类型,任何数据在Spark中都被表示为RDD。从编程的角度来看,RDD可以简单看成是一个数组。和普通数组的区别是,RDD中的数...

    加米谷大数据
  • 电解电容为什么会爆炸?一文看明白!

    电解电容是通过电解质作用在电极上形成的氧化层作为绝缘层的电容,通常具有较大的容量。电解质是液体、胶冻状富含离子的物质,大多数电解电容都是有极性的,也就是在工作时...

    MCU起航

扫码关注云+社区

领取腾讯云代金券