链栈

1.链表的头指针就是栈顶
2.不需要头结点
3.基本不存在栈满情况
4.空栈相当于头指针指向空
5.插入和删除仅在栈顶处执行，链栈中的操作大部分都和单链表类似，只是插入和删除特殊一些
Note:链栈中指针的方向
如下图所示:

image.png

LinkStack.h

#pragma once
#include <iostream>
using namespace std;

#define MAXSIZE 20
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int SElemType;

typedef struct StackNode
{
    SElemType data;
    struct StackNode* next;
}StackNode, * LinkStack;

//链栈初始化
void InitStack(LinkStack& S);

//判断链栈是否为空
bool StackEmpty(LinkStack S);

//链栈的入栈
Status Push(LinkStack& S, SElemType e);

//链栈的出栈
Status Pop(LinkStack& S, SElemType& e);

//链栈的遍历
void StackTraverse(LinkStack S);

//取栈顶元素
SElemType GetTop(LinkStack S);

LinkStack.cpp

#include "LinkStack.h"

//链栈初始化
void InitStack(LinkStack& S)
{
    //构造一个空栈，栈顶指针值为空
    S = NULL;
}

//判断链栈是否为空
bool StackEmpty(LinkStack S)
{
    if (!S)
    {
        return true;
    }
    return false;
}

//链栈的入栈
Status Push(LinkStack& S, SElemType e)
{
    StackNode* p = new StackNode;
    p->data = e;
    p->next = S;

    S = p;

    return OK;
}

//链栈的出栈
Status Pop(LinkStack& S, SElemType& e)
{
    if (StackEmpty(S))
    {
        cout << "栈为空" << endl;
        return ERROR;
    }

    StackNode* p = S;
    e = p->data;
    S = S->next;

    delete p;

    return OK;
}

//链栈的遍历
void StackTraverse(LinkStack S)
{
    StackNode* p = S;

    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

//取栈顶元素
SElemType GetTop(LinkStack S)
{
    if (S)
    {
        return S->data;
    }
    return ERROR;
}

main.cpp

测试：

#include "LinkStack.h"

int main(int argc, char** argv)
{
    LinkStack S;
    InitStack(S);       //初始化链栈

    Push(S, 1);         //入栈
    Push(S, 2);
    Push(S, 3);

    StackTraverse(S);   //遍历

    SElemType e;
    Pop(S, e);          //出栈
    cout << "出栈的元素：" << e << endl;

    //获取栈顶元素
    cout << "栈顶元素为：" << GetTop(S) << endl;

    return 0;
}