欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构入门-栈

程序员文章站 2023-11-02 15:27:16
定义:一种可以实现“ 先进后出 ”的存储结构 分类: 1. 静态栈 2. 动态栈 算法: 1. 出栈 2. 压栈 代码实现: 多敲,多敲 ,后期改进 应用: 1. 函数调用 2. 中断 3. 表达式求值 4. 内存分配 5. 缓冲处理 6. 迷宫 ......

定义:一种可以实现“先进后出”的存储结构

分类:

  1. 静态栈
  2. 动态栈

算法:

  1. 出栈
  2. 压栈

代码实现:

多敲,多敲,后期改进

#include <stdio.h>
#include <stdlib.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);
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 , 8);
    push(&s , 23);
    push(&s , 26);
    push(&s , 34);
    push(&s , 45);
    push(&s , 76);
    push(&s , 88);
    traverse(&s); // 遍历输出

    if(pop(&s , &val))
    {
        printf("你删除的是%d\n", val );
        traverse(&s);
        printf("清空数据\n");
        clear(&s);
        traverse(&s);
    }
    else
    {
        printf("删除失败\n");
    }
}




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->pbottom->pnext = null
    }
}


void push(pstack ps, int val)
{
    pnode pnew = (pnode)malloc(sizeof(node));

    pnew->data = val; 

    pnew->pnext = ps->ptop; // 这里需要注意
    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所指向的栈出栈一次,并把出栈元素存下
bool pop(pstack ps , int *val)
{

    if (empty(ps))
    {
        return false;
    }
    else
    {
        pnode p = ps->ptop;
        *val = p->data;

        ps->ptop = p->pnext;
        free(p);
        p = null;
        return true;

    }
    
}


// 清空
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;
    }
}

应用:

  1. 函数调用
  2. 中断
  3. 表达式求值
  4. 内存分配
  5. 缓冲处理
  6. 迷宫