数据结构的C++实现之栈的链式存储结构

当单链表限定只能在头部进行插入和删除操作的时候，即为链栈，一般我们会将单链表的头指针和栈的栈顶指针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;
}

输出为：

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

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索指针
， 数据结构
， c++ 链栈 出错
， 链栈
， 单链表 数据结构 c++
， count
， c++ 栈 计算器
， 代码 cout
， cout
， top
， 链式结构序列化
， 栈的实现代码
， 链式栈
单链
栈的链式存储结构、栈的链式存储、链式栈的实现、栈的链式表示和实现、栈是链式存储的，以便于您获取更多的相关知识。