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

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

相关文章

来自专栏函数式编程语言及工具

SDP(6):分布式数据库运算环境- Cassandra-Engine

    现代信息系统应该是避不开大数据处理的。作为一个通用的系统集成工具也必须具备大数据存储和读取能力。cassandra是一种分布式的数据库,具备了分布式数据...

3204
来自专栏FD的专栏

编辑器背后的数据结构

大约刚上大二的时候,想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器,而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一...

1223
来自专栏码匠的流水账

bloomfilter的简单实现

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,可以用于检索一个元素是否在一个集合中。

601
来自专栏码匠的流水账

聊聊storm的ICommitterTridentSpout

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSp...

1003
来自专栏码匠的流水账

聊聊flink的RichParallelSourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/func...

1122
来自专栏积累沉淀

研究MapReduce源码之实现自定义LineRecordReader完成多行读取文件内容

TextInputFormat是Hadoop默认的数据输入格式,但是它只能一行一行的读记录,如果要读取多行怎么办? 很简单 自己写一个输入格式,然后写一个对...

1939
来自专栏小樱的经验随笔

Codeforces 768B Code For 1

B. Code For 1 time limit per test:2 seconds memory limit per test:256 megabytes ...

3558
来自专栏码匠的流水账

聊聊flink的RichParallelSourceFunction

flink-streaming-java_2.11-1.6.2-sources.jar!/org/apache/flink/streaming/api/func...

1481
来自专栏计算机视觉与深度学习基础

Leetcode 题目列表(难度、出现频率、知识点)

不全,但好像没看到有更好的版本,刷前132题暂时凑合着用吧! 转载自:LeetCode Question Difficulty Distribution ?...

3826
来自专栏编程之路

羊皮书APP (Android版)开发系列(二)日志工具类

在App开发过程中,很重要的一个调试工具就是日志的打印,Android系统自带的日志打印文件,看起来并不是很直观。这里我们自己对原生Android 日志做一个...

961

扫码关注云+社区