栈——线性结构的应用之一

Akari2023-11-232024-03-09

栈和队列是一种特殊的线性结构，是连续存储或离散存储的一种应用。
此为链式队列。

定义

一种可以实现“先进后出”的存储结构，类似于箱子。

算法

出栈
压栈

应用

函数调用
中断
表达式求值
分配内存
缓冲处理
迷宫

举例

int main(void)
{
    int p;
    int * m = (int *)malloc(100);
}

如静态变量p和m是在栈中分配，由操作系统自动分配和释放。而(int *)malloc(100);执行后，将在堆中分配一块100字节的内存，由程序员手动分配。

代码

/**
 * @version: 4.0  
 * @author: @Shiel
 * @date: 2023-10-17 19:42:30
 **/

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

typedef struct Node
{
    int data;
    struct Node* pNext;
}NODE, *PNODE;      // 定义栈节点叫Stack_Node 和 pStack_Node 更好

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;    // 定义保存栈节点地址的 栈指针

void Init(PSTACK);          // 栈初始化，造出空栈
void Push(PSTACK, int );    // 压栈
void Traverse(PSTACK);      // 遍历
bool Empty(PSTACK pS);      // 栈是否为空
bool Pop(PSTACK, int *);    // 出栈
void Clear(PSTACK pS);      // 清除栈

int main(void)
{
    STACK s;    // STACK 等价于 struct Stack
//  PSTACK S = (PSTACK)malloc(sizeof(PSTACK));  // 没必要，画蛇添足
//  PSTACK S = (PNODE)malloc(sizeof(NODE));     // 结构体类型不一样，不能转换
//  PSTACK S = NULL;    // 大错特错！
    int val;
    
// 郝斌老师：
    Init(&s);
    Push(&s, 1);
    Push(&s, 2);
    Push(&s, 3);
    Push(&s, 4);
    Traverse(&s);   // 目的是便于输出

// 同上————没必要，画蛇添足。
/*  Me:
    Init(S);
    Push(S, 1);
    Push(S, 2);
    Traverse(S);
*/
    if(Pop(&s, &val))
    {
        printf("出栈成功！出栈的元素是：%d\n", val);
    }
    else
        printf("出栈失败！\n");
    
    Clear(&s);
    Traverse(&s);
    
    if(Pop(&s, &val))
    {
        printf("出栈成功！出栈的元素是：%d\n", val);
    }
    else
        printf("出栈失败！\n");
    
    return 0;
}

void Init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));     // 新建栈节点，头栈节点
    if(NULL == pS->pTop)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else
    {
        pS->pBottom = pS->pTop;     // 栈顶和栈底 都指向指针域为空的头栈节点
        pS->pBottom->pNext = NULL;  // 头栈节点的指针域为 NULL
    }
}

void Push(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));   // 新建一个栈节点
    
    pNew->data = val;   // 给栈节点中的数据域赋值
    pNew->pNext = pS->pTop;     // pS-pTop 不能改为 pS-pBottom
                                // 栈节点的指针域保存下一个节点的地址
    pS->pTop = pNew;    // 新的栈节点变为新的栈顶
    
    return;
}

void Traverse(PSTACK pS)
{
    PNODE p = pS->pTop;     // 指针指向栈顶
    
    while(p != pS->pBottom) // 是否遍历到栈底
    {
        printf("%d ", p->data);
        p = p->pNext;   // 下一个节点的地址，栈节点的指针域保存下一个节点的地址
    }
    printf("\n");
    return;
}

bool Empty(PSTACK pS)
{
    if(pS->pTop == pS->pBottom) // 栈顶和栈底都指向头栈节点时栈才为空
    {
        return true;
    }
    else
        return false;
}

// 把pS所指向的栈出栈一次，并把出栈的元素存入 pVal形参所指向的变量中，如果出栈失败，返回 false，否则返回 true
bool Pop(PSTACK pS, int* pVal)
{
    if(Empty(pS))   // pS 本身存放的就是S的地址
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop; // 指针指向栈顶
        *pVal = r->data;    // 获取栈顶的数据域内的数据 
        pS->pTop = r->pNext;// 新的栈节点变为新的栈顶
        free(r);    // 内存释放，否则容易造成内存泄漏。释放r所指向的原栈顶节点的内存
        r = NULL;   // 避免野指针，NULL 是拴狗的狗链子
        
        return true;
    }
}

void Clear(PSTACK pS)   // 清空栈
{
    if(Empty(pS))   // pS 本身存放的就是 S 的地址
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop; // 指针指向栈顶
        PNODE q = NULL;     // 栈节点的地址临时保存在 q 中
        
        while(p != pS->pBottom) // 是否遍历到栈底

        {
            q = p->pNext;   // 栈节点指针域(下一节点地址)临时保存在指针 q 中
            free(p);    // 经过上步才能进行此步，否则直接 free，就找不到下一个节点地址了
            p = q;      // 临时保存在 q 中的下一节点地址赋值给 p，准备循环释放下一节点内存
        }
        pS->pTop = pS->pBottom; // 栈顶和栈底都指向指针域为空的头栈节点
    }
}