栈（链式结构）

栈（链式结构）

头文件MyStack.h

#ifndef _MYSTACK_H_
#define _MYSTACK_H_

#include 
#include 
#include 

typedef struct Node *pNode;
typedef struct Stack *linkStack;

struct Node
{
    int data;
    pNode next;
};

struct Stack
{
    int size;                               // 栈顶指针
    pNode top;
};

linkStack Create (void);                    // 创建栈
bool IsEmpty (linkStack stack);             // 判断空栈
int GetSize (linkStack stack);              // 获取栈大小
void Push (linkStack stack, int val);        // 元素入栈
pNode GetTop (linkStack stack);             // 获取栈顶元素
pNode Pop (linkStack stack);                // d出栈顶元素
void Destory (linkStack stack);             // 销毁栈

linkStack
Create (void)
{
    linkStack stack = (linkStack)malloc (sizeof (struct Stack));

    if (stack == NULL)
    {
        printf ("Error Memoty!");

        exit (1);
    }

    stack -> top = NULL;
    stack -> size = 0;

    return stack;
}

bool
IsEmpty (linkStack stack)
{
    if (stack -> top == NULL || stack -> size == 0)
    {
        return true;
    }

    return false;
}

int
GetSize (linkStack stack)
{
    return stack -> size;
}

void
Push (linkStack stack, int val)
{
    pNode p = (pNode)malloc (sizeof (struct Node));

    if (p != NULL)
    {
        p -> data = val;                            // 将数据储存在新节点中
        p -> next = GetTop (stack);                 // 将新节点与原栈顶相连接

        stack -> top = p;                           // 将新节点重新定义为栈顶
        stack -> size ++;
    }
}

pNode
GetTop (linkStack stack)
{
    if (stack -> size != 0)
    {
        return stack -> top;
    }

    return NULL;
}

pNode
Pop (linkStack stack)
{
    if (IsEmpty (stack))
    {
        return NULL;
    }

    pNode p = stack -> top;                         // 储存原栈顶

    stack -> top = stack -> top -> next;            // 将原栈顶下一元素重定义为栈顶
    stack -> size --;

    return p;                                       // d栈
}

void
Destory (linkStack stack)
{
    if (IsEmpty (stack))
    {
        free (stack);

        printf ("当前为空栈，无需销毁！n");

        return;
    }

    do
    {
        pNode p = Pop (stack);

        free (p);
    }
    while (stack -> size != 0);

    printf ("成功销毁栈！n");
}

#endif // _MYSTACK_H_

测试文件main.c

#include "MyStack.h"
#include 


int main (void)
{
    srand ((unsigned) time (0));                                // 生成随机数
    linkStack stack = NULL;
    stack = Create ();

    if (IsEmpty (stack))                                        // 测试是否创建为空栈
    {
        printf ("空栈！n");
    }
    else
    {
        printf ("栈不为空！n");
    }

    for (int i = 0; i < 10; i ++)
    {
        Push (stack, rand () % 100);                            // 随机数入栈
    }

    if (IsEmpty (stack))                                        // 测试是否元素入栈
    {
        printf ("空栈！n");
    }
    else
    {
        printf ("栈不为空！n");
    }

    printf ("栈的大小: %d n", stack -> size);

    printf ("栈顶元素: %d n", *((int *)GetTop (stack)));       // 强制转换 pNode => int

    while (stack -> size != 0)
    {
        printf ("%d ", *((int *)Pop (stack)));                  // d出栈顶元素
    }

    printf ("n");

    Destory (stack);                                            // 销毁栈

    system ("pause");
    return 0;
}

结语

        栈的链式存储也称为链栈，和链表的存储原理一样，用指针来建立各个节点之间的逻辑关系；压栈和d栈表现的尤为明显。

        链栈就是一个单端 *** 作的链表，其插入 删除 *** 作就是在链表的一端实现的