[数据结构与算法]关于数据结构（c语言）中，栈中顺序结构的大部分操作的代码实现

引入

? ? ? ? 数据结构是计算机专业必学的一门课程，如果说算法是一个程序的操作动作，那么数据结构就是一个程序的灵魂，它让一段程序在运行的过程中，拥有足够强大的“内力”进行代码的实现。

? ? ? ? 栈在数据结构中的地位其实是线性表的具体延申，它的实质是受限制的线性表，而它受到限制的部分即在原有线性表的基础上增加了两个指针，分别栈底指针与栈顶指针，并规定栈底指针始终指向栈底结点不动，而栈顶指针始终指向顶部结点（或顶部结点的后一个结点），并随着结点的压栈出栈等操作而上下移动。这样一个受限制的线性表即被称为栈，而这样的限制方式也使得栈拥有了其特别之处，即先进后出(FILO)或后进先出(LIFO)，使得栈有了广泛的应用。因此，学好栈的基本操作的代码实现是必要的，而理解栈这一存储结构的重要思想更是必不可少的。

? ? ? ? 本篇文章将要介绍的，是栈（逻辑结构）中的顺序结构（存储结构），即下文所称的顺序栈。而在下文将要介绍的程序中，将要通过对顺序栈的初始化、压栈（入栈）、遍历并输出、判空、出栈、清空、销毁的分段过程，对整体代码进行分析与剖析。

第一部分 头文件与结构体的创建

? ? ? ? 创建两个结构体，其中一个与链表的结构体相同，使其包含顺序表的数据域（用于存放一个结点的值）与指针域（用于存放一个结点指向的下一个结点），利用typedef，使结构体在之后的操作部分简化声明，其中，NODE等价于struct Node，PNODE等价于struct Node*。另一个结构体中主要包含栈的特征，即栈顶指针与栈底指针，其中，STACK等价于struct Stack，PSTACK等价于struct Stack*。

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

typedef struct Node
{
    int data;
    struct Node* pNext;
}NODE, *PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;

第二部分 函数声明

? ? ? ? 提前对所需操作的函数进行函数声明，对顺序栈进行初始化、压栈（入栈）、遍历并输出、判空、出栈、清空、销毁的操作，便于为之后具体代码的书写理清思路。

void init(PSTACK pS); //对栈进行初始化
void push(PSTACK,int val); //压栈
void traverse(PSTACK pS); //遍历并输出栈
bool is_empty(PSTACK pS); //判空
bool pop(PSTACK pS, int* pVal); //出栈
bool clear(PSTACK pS); //清空顺序栈
void destory(PSTACK pS); //销毁顺序栈

第三部分 主函数中的实例化与函数调用

? ? ? ? 将Stack结构体变量实例化为S，调用要操作的函数，对各类操作进行验证。

int main(void)
{
    STACK S;
    int val;
    init(&S);
    push(&S,1);
    push(&S,2);
    push(&S,3);
    push(&S,4);
    push(&S,5);
    push(&S,6);
    printf("经压栈后的初始顺序栈为：");
    traverse(&S);
    if(pop(&S,&val))
    {
        printf("出栈成功，出栈的元素为：%d\n",val);
    }
    else
    {
        printf("出栈失败！\n");
    }
    printf("出栈后的顺序栈为：");
    traverse(&S);
    if(clear(&S))
    {
        printf("顺序栈已清空！\n");
    }
    else
    {
        printf("清空失败！\n");
    }
    destory(&S);
    return 0;
}

第四部分 各类操作的具体代码实现

1、顺序栈的初始化 void init(PSTACK pS);

? ? ? ? a. 为栈顶指针pS->pTop分配一段动态内存空间。

? ? ? ? b. 判断栈顶指针的内存是否分配成功。

? ? ? ? c. 若分配成功，使顺序栈的初始状态为：栈底指针与栈顶指针指向同一片内存空间，将栈顶指针指向的后一个结点置为空，便于后续操作。

void init(PSTACK pS)
{
    pS->pTop=(PNODE)malloc(sizeof(NODE));
    if(NULL==pS->pTop)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
        pS->pBottom=pS->pTop;
        pS->pTop->pNext=NULL;
}

2、压栈（入栈） void push(PSTACK pS, int val);

? ? ? ? a. 创建一个将要生成的新结点并为其分配内存空间，使其数据域为要输入的值。

? ? ? ? b. 使新分配的结点插入在栈顶指针前。

? ? ? ? c. 使栈顶指针指向新结点（也可使栈顶指针指向栈顶结点的下一个位置）。

void push(PSTACK pS,int val)
{
    PNODE pNew=(PNODE)malloc(sizeof(NODE));
    pNew->data=val;
    pNew->pNext=pS->pTop;
    pS->pTop=pNew;
    return;
}

3、遍历并输出 void traverse(PSTACK pS);

? ? ? ? a. 分配一个临时结点，使其与栈顶指针的指向相同。

? ? ? ? b. 进入循环，使临时指针自后向前依此指向每一个结点，直到指向栈底指针，输出每一个结点的值。

void traverse(PSTACK pS)
{
      PNODE p=pS->pTop;
      while(p!=pS->pBottom)
      {
          printf("%d ",p->data);
          p=p->pNext;
      }
      printf("\n");
      return;
}

4、判空 bool is_empty(PSTACK pS);

? ? ? ? 当栈顶指针与栈底指针指向同一片内存空间时，顺序栈即为空。

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

5、出栈 bool pop(PSTACK pS, int* pVal);

? ? ? ? a. 判断顺序栈是否为空，若为空则不需要执行出栈操作，返回false。

? ? ? ? b. 分配一个临时指针，使其与栈顶指针的指向相同（即指向栈顶结点）。

? ? ? ? c. 让要出栈的栈顶元素的值先被保存在临时变量*pVal中，便于之后输出时读取。

? ? ? ? d. 使栈顶指针指向临时分配的指针的前一个结点，即出栈元素的前一个结点。

? ? ? ? e. 最终释放临时结点，返回true。

从出栈操作即可看出，栈是从栈顶元素开始出栈的。

bool pop(PSTACK pS, int* pVal)
{
    if(is_empty(pS))
    {
        return false;
    }
    else
    {
        PNODE r=pS->pTop;
        *pVal=r->data;
        pS->pTop=r->pNext;
        free(r);
        r=NULL;
        return true;
    }
}

6、清空 bool clear(PSTACK pS);

? ? ? ??a. 判断顺序栈是否为空，若为空则不需要执行出栈操作，返回false。

? ? ? ??b. 分配一个临时指针p，使其与栈顶指针的指向相同（即指向栈顶结点）。

? ? ? ? c. 分配一个临时指针q，使其先置为空，之后要使其一直指向p的前一个结点。

? ? ? ? d. 进入循环，使q一直指向p的前一个结点（作用是保存删除结点的前一个结点的位置）。

? ? ? ? e. 退出循环后，清空的最终结果即为空顺序栈，返回true。

bool clear(PSTACK pS)
{
    if(is_empty(pS))
    {
        return false;
    }
    else
    {
    PNODE p=pS->pTop;
    PNODE q=NULL;
    while(p!=pS->pBottom)
    {
       q=p->pNext; //使q一直指向p的前一个元素
       free(p);
       p=q;
    }
    pS->pTop=pS->pBottom;
    }
    return true;
}

7、销毁 void destory(PSTACK pS);

void destory(PSTACK pS)
{
    free(pS);
    pS=NULL;
}

写在最后

? ? ? ? 以上所有的操作细节与代码具体实现的思想已叙述完毕，希望对各位读者有所帮助与启发。