2.（1）栈的链式存储、链栈的操作（图解、注释、代码）

本人坚持更新C语言和数据结构知识，可以收藏＋关注随时了解

---

目录

1.结构体定义

2.初始化一个链栈

2.1图解过程

2.2代码

3.压栈

3.1图解过程

3.2代码

4.出栈

4.1.图解过程 

4.2代码

5.栈的判空

6.栈的遍历

6.1图解过程

6.2代码

---

1.结构体定义

栈的链式存储主要是用到了两个结构体

一个结构体存放栈顶指针和栈底指针

        之所以这样，是因为栈属于一个操作受限的线性表，对栈的操作只能在栈顶执行

一个结构体是存放结点

        结点包括数据域和指针域，类似于链表

typedef struct Node //结点
{
    int data;
    struct Node *pNext;
} Node, *PNODE;
// Node<=>struct Node
// PNODE <=>struct Node *


typedef struct Stack //存放栈顶指针和栈底指针
{
    PNODE pTop; // pTop指向的数据类型为struct Node
    PNODE pBottom;
} STACK, *PSTACK;
//Stack<=>struct Stack
//PSTACK<=>struct Stack*

2.初始化一个链栈

2.1图解过程

（1）我们创建存放栈顶栈底指针的结构体（也就是栈的结构体），并动态创建一个结点，作为栈底，栈底的指针域为空

 

（2）初始状态下，栈顶指针(S.top)和栈底指针(S.bottom)都指向栈底

2.2代码

void initStack(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(Node)); //动态生成一个结点，使得pTop指针指向它,pTop保存这个结点第一个字节的地址
    if (NULL == pS->pTop)
    {
        printf("dynamic memory is failed to allocate,procedure is over!\n");
        exit(-1);
    }
    else
    {
        pS->pBottom = pS->pTop;    //让pBottom和pTop指向同一个结点
        pS->pBottom->pNext = NULL; // pS->pTop->pNext = NULL;令栈底的指针域为空
    }
}

3.压栈

栈的操作只能在栈顶进行，所以重点是移动栈顶指针的位置，让S.Ptop指向栈顶元素

3.1图解过程

（1）动态生成一个结点pNew

（2）pNew指向栈底，栈顶指针指向pNew

（3）以此类推

   

3.2代码

void pushStack(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(Node));
    pNew->data = val;
    pNew->pNext = pS->pTop; // pS->pTop不能改成pS->pBottom
    pS->pTop = pNew;        // pTop指向pNew
}

4.出栈

4.1.图解过程 

 出栈是压栈的逆过程，只需要将S.pTop指针下移，然后释放被删除节点的内存就可以

4.2代码

/把pS所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中
bool pop(PSTACK pS, int *pVal)
{
    if (empty(pS))
        return false;
    else
    {
        PNODE r = pS->pTop;
        *pVal = r->data;
        pS->pTop = pS->pTop->pNext; // ps->pTop=r->pNext
        free(r);
        r = NULL;
        return true;
    }
}

5.栈的判空

栈空的条件为，栈顶指针和栈底指针指向同一个存储单元

bool empty(PSTACK pS)
{
    if (pS->pBottom == pS->pTop)
    {
        return true;
    }
    else
    {
        return false;
    }
}

6.栈的遍历

6.1图解过程

1.定义一个结构体指针指向栈顶，和S.pTop指向同一个位置

2.每读取一个元素就将p下移一次，直到p指向的节点的指针域为NULL

6.2代码

void traverse(PSTACK pS)
{
    PNODE p;
    p = pS->pTop;
    cout << "stack's datas are:" << endl;
    while (p->pNext != NULL)
    {
        cout << p->data << endl;
        p = p->pNext;
    }
}