数据结构-链栈(C语言实现)

1. 导入头文件

编写代码过程中，涉及动态内存分配等常用的函数，需要引入如下头文件

#include<stdio.h>
#include<stdlib.h>

2. 结构体定义

// 链表的 Node 结构体
typedef struct Node
{
    int data;
    struct Node * next;
} NODE, *PNODE;

// Stack 结构体
typedef struct Stack
{
    PNODE pTop;            // 指向栈顶的指针
    PNODE pBottom;      // 指向栈底的指针
} STACK, *PSTACK;

3. 函数声明

void init(PSTACK pStack);    // 初始化
void show(PSTACK pStack);    // 列出所有元素
int isEmpty(PSTACK pStack); // 是否为空
void push(PSTACK pStack, int val);      // 入栈
void pop(PSTACK pStack, int *val);  // 出栈
void clear(PSTACK pStack);  // 清空

4. 栈的初始化

pS 通过传参的方式传过来，不需要进行初始化，pS 已经分配空间，只需要将两个成员 pTop、pButtom 初始化即可，初始化时，栈顶和栈底的指向相同

void init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if (pS->pTop==NULL)
    {
        printf("内存分配失败");
        exit(-1);
    } else
    {
        pS->pBottom = pS->pTop;     // 初始化时指向相同
        pS->pTop->next = NULL;
    }

}

5. 栈是否为空

如果栈顶和栈底的指向相同，则表示栈为空

int isEmpty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)    // 和初始化时相同则为空
    {
        return 1;
    }
    return 0;
}

5. 入栈操作

栈添加元素时需要先将新元素的next指向栈顶元素，然后将栈顶指针上移

void push(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (pNew == NULL)
    {
        printf("内存分配失败");
        exit(-1);
    }

    pNew->data=val;
    pNew->next=pS->pTop;      // 新元素指针的指向
    pS->pTop = pNew;            // 修改栈顶指针指向
}

6. 出栈操作

出栈时需将栈顶元素返回，然后修改栈顶指向

void pop(PSTACK pS, int *val)
{
    if (isEmpty(pS))
    {
        printf("Stack is Empty");
        return;
    } else
    {
        PNODE q = pS->pTop;
        *val = q->data;
        pS->pTop = q->next;
        free(q);                  // 内存释放
        q = NULL;
    }
}

6. 清栈操作

清理需要依次遍历所有元素，将内存释放

void clear(PSTACK pS)
{
    if (isEmpty(pS))
    {
        printf("Stack is Empty");
        return;
    } else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while (p!=pS->pBottom)
        {
            q=p->next;
            free(p);
            p=q;
        }
        pS->pTop=pS->pBottom;      // 最后将栈顶栈底指向同一位置
    }
}

7. 展示操作

依次遍历，将元素列出

void show(PSTACK pS)
{
    if (isEmpty(pS))
    {
        printf("栈元素为空\n");
    } else
    {
        PNODE p = pS->pTop;
        while (p != pS->pBottom)
        {
            printf("%d,", p->data);
            p=p->next;
        }

        printf("\n");
    }
}

8. main函数

int main()
{
    int val;
    STACK S;
    init(&S);
    push(&S, 1);
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    show(&S);
    pop(&S, &val);
    pop(&S, &val);
    pop(&S, &val);
    show(&S);
    clear(&S);
    show(&S);
    return 0;
}

数据结构-链栈(C语言实现)

原文：https://www.cnblogs.com/sugare/p/13156607.html