2- 栈的功能实现

灰太狼 2023-08-17 16:02 119阅读 0赞

### 数据结构3 ###

1、线性结构的两种常见应用之一 栈 (存储数据的结构)  
定义

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

2、分类

*  静态栈 （类似于用数组实现）
 *  动态栈 （类似于用链表实现）

3、算法（往里放，从里取）

*  出栈
 *  压栈（参看Java中线程的例子，成产消费的例子

4、栈的示意图  
![1665530-20190706235412804-146494666.jpg][]

##### 2-1 程序实现静态栈功能 #####

# include <stdio.h>
    # include <malloc.h>
    /*如静态变量p和m是在栈中分配，有操作系统自动分配和释放。
     而(int *)malloc(100);执行后，将在堆中分配一块100字节的内存，由程序员手动分配。*/
    void f(int k)
    {
        int m;
    
        double * q = (double *)malloc(200);
    }
    
    int main(void)
    {
        int i = 10;
        int * p = (int *)malloc(100);
    
        return 0;
    }

**代码实现2**

# include <stdio.h>
    # include <malloc.h>
    # include <stdlib.h>
    
    typedef struct Node
    {
        int data; //数据域
        struct Node * pNext;  //指针域
    }NODE, * PNODE;
    
    
    //创建栈数据类型
    typedef struct Stack
    {
        PNODE pTop;   //指针顶部
        PNODE pBottom; //指针底部
    }STACK, * PSTACK;  //PSTACK 等价于 struct STACK *
    
    void init(PSTACK);  //初始化
    void push(PSTACK, int ); //压栈
    void traverse(PSTACK);   //遍历输出
    bool pop(PSTACK, int *); //出栈
    void clear(PSTACK pS);
    
    int main(void)
    {
        STACK S;  //STACK 等价于 struct Stack
        int val;
    
        init(&S);  //目的是造出一个空栈
        push(&S, 1); //压栈
        push(&S, 2);
        push(&S, 3);
        push(&S, 4);
        push(&S, 5);
        push(&S, 6);
        traverse(&S); //遍历输出
        
        clear(&S);
        //traverse(&S); //遍历输出
    
        if ( pop(&S, &val) )
        {
            printf("出栈成功，出栈的元素是%d\n", val);
        }
        else
        {
            printf("出栈失败!\n");
        }
    
        traverse(&S); //遍历输出
    
        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->pTop->pNext = NULL; //pS->Bottom->pNext = NULL;
        }
    }
    
    void push(PSTACK pS, int val)
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        
        pNew->data = val;
        pNew->pNext = pS->pTop; //pS->Top不能改成pS->Bottom
        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 = NULL;
    
            return true;
        }
    }
    
    //clear清空
    void clear(PSTACK pS)
    {
        if (empty(pS))
        {
            return;
        }
        else
        {
            PNODE p = pS->pTop;
            PNODE q = NULL;
    
            while (p != pS->pBottom)
            {
                q = p->pNext;
                free(p);
                p = q;
            }
            pS->pTop = pS->pBottom;
        }
    }

转载于:https://www.cnblogs.com/Guard9/p/11144741.html

[1665530-20190706235412804-146494666.jpg]: /images/20230810/d205d869c09a441f9663d97b16814822.png