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

单链表限定只能在头部进行插入和删除操作的时候,即为链栈,一般我们会将单链表的头指针和栈的栈顶指针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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1098 均分纸牌

1098 均分纸牌 2002年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 D...

3198
来自专栏移动开发面面观

iOS中HTML的解析——Hpple

1222
来自专栏数据结构与算法

BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

1104
来自专栏跟着阿笨一起玩NET

PropertyGrid绑定Dictionary

本文摘抄:http://greatverve.cnblogs.com/archive/2012/02/08/propergrid-Dictionary.ht...

652
来自专栏码匠的流水账

java10系列(二)Local-Variable Type Inference

本文主要解读下java10的Local-Variable Type Inference

581
来自专栏更流畅、简洁的软件开发方式

[自定义服务器控件] 第三步:CheckBoxList。

前面发了文本框和下拉列表框的,这回发一个CheckBoxList。不知道中文名字该叫什么。 CheckBoxList 最郁闷的地方就是:明明可以选择多个选项,但...

2076
来自专栏ASP.NET MVC5 后台权限管理系统

ASP.NET MVC5+EF6+EasyUI 后台管理系统(17)-LinQ动态排序

首先修复程序中的一个BUG这个BUG在GridPager类中,把sord修改为sort这个名称填写错误,会导致后台一直无法获取datagrid的排序字段 本来是...

2085
来自专栏码匠的流水账

聊聊sentinel的ArrayMetric

com/alibaba/csp/sentinel/slots/statistic/metric/ArrayMetric.java

891
来自专栏coding

使用v-for遍历数据

804
来自专栏数据结构与算法

BZOJ2434: [Noi2011]阿狸的打字机(AC自动机 树状数组)

1013

扫码关注云+社区