2. (1) Chained storage of stack, operation of chain stack (illustration, comment, code)

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

---

目录

1.结构体定义

2.初始化一个链栈

2.1图解过程

2.2代码

3.压栈

3.1图解过程

3.2代码

4.出栈

4.1.图解过程 

4.2代码

5.栈的判空

6.栈的遍历

6.1图解过程

6.2代码

---

1.结构体定义

The chain storage of the stack is mainly used两个结构体

A structure holds the top and bottom pointers of the stack

        之所以这样,This is because the stack belongs to a linear list with limited operations,Operations on the stack can only be performed at the top of the stack

A structure is the storage node

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

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


typedef struct Stack //Stores the top and bottom pointers of the stack
{
    PNODE pTop; // pTopThe data type pointed to is struct Node
    PNODE pBottom;
} STACK, *PSTACK;
//Stack<=>struct Stack
//PSTACK<=>struct Stack*

2.初始化一个链栈

2.1图解过程

（1）我们创建存放The structure of the pointer to the top of the stack and the bottom of the stack（That is, the structure of the stack）,并动态创建一个结点,作为栈底,The pointer field at the bottom of the stack is empty

 

（2）初始状态下,栈顶指针(S.top)and the stack bottom pointer(S.bottom)都指向栈底

2.2代码

void initStack(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(Node)); //Generate a node dynamically,使得pTop指针指向它,pTopHolds the address of the first byte of this node
    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;Make the pointer field at the bottom of the stack empty
    }
}

3.压栈

Operations on the stack can only be performed at the top of the stack,So the point is to move the position of the top pointer on the stack,让S.Ptop指向栈顶元素

3.1图解过程

（1）Generate a node dynamicallypNew

（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.图解过程 

 Popping is the reverse process of pushing,只需要将S.pTop指针下移,Then release the memory of the deleted node

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.栈的判空

栈空的条件为,The stack top pointer and the stack bottom pointer point to the same memory location

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

6.栈的遍历

6.1图解过程

1.Define a structure pointer to point to the top of the stack,和S.pTop指向同一个位置

2.Every time an element is read it will bepmove down once,直到pThe pointer field to the node pointed to is 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;
    }
}