数据结构 day06 基础知识学习 （栈）

一.栈的特点 ：后进先出

二.用单链表实现栈

三.老师的代码（3个文件）gcc 编译（今天老师有点懒，所以没有写makefile！！！！！） 

1.stack.h

2.stack.c

3.main.c

四.代码：

stack.h

#ifndef __STACK_H__
#define __STACK_H__
#include 
#include 
#include 
#include 
typedef struct node
{
    void* data;
    struct node* next;
}node,*pnode;

typedef struct 
{
    int size;
    struct node* top;//栈
}stack;

//初始化
void stack_init(stack* s);

//入栈
int stack_push(stack* s,const void* data_ptr,const int size);

//出栈
int stack_pop(stack * s);

//获取栈顶元素
void* stack_top(stack* s);

//获取元素个数
int stack_size(stack* s);

//判断是否为ＮＵＬＬ
bool stack_empty(stack* s);

//销毁栈
void stack_destroy(stack* s);

#endif

stack.c

#include "stack.h"

//初始化
void stack_init(stack *s)
{
    if (s == NULL)
    {
        return;
    }
    s->size = 0;
    s->top = NULL;
}

//入栈
int stack_push(stack *s, const void *data_ptr, const int size)
{
    if (s == NULL || data_ptr == NULL || size <= 0)
    {
        return -1;
    }
    node *pnew = (node *)malloc(sizeof(node));
    if (pnew == NULL)
    {
        return -2;
    }
    pnew->data = malloc(size);
    if (pnew->data == NULL)
    {
        return -2;
    }
    memcpy(pnew->data, data_ptr, size);
    pnew->next = s->top;
    s->top = pnew;
    s->size++;
}

//出栈
int stack_pop(stack *s)
{
    if (s == NULL)
    {
        return -1;
    }
    if (stack_empty(s))
    {
        return -2;
    }
    node *ptemp = s->top;
    s->top = s->top->next;
    free(ptemp->data);
    free(ptemp);
    s->size--;
    return 0;
}

//获取栈顶元素
void *stack_top(stack *s)
{
    if (s == NULL)
    {
        return NULL;
    }
    if (stack_empty(s))
    {
        return NULL;
    }
    return s->top->data;
}

//获取元素个数
int stack_size(stack *s)
{
    if (s == NULL)
    {
        return -1;
    }
    return s->size;
}

//判断是否为ＮＵＬＬ
bool stack_empty(stack *s)
{
    if (s == NULL || s->size == 0)
    {
        return true;
    }
    return false;
}

//销毁栈
void stack_destroy(stack *s)
{
    if (s == NULL)
    {
        return;
    }
    while (s->size )
    {
        stack_pop(s);
    }
}

main.c

#include "stack.h"

stack s;
int main()
{
    stack_init(&s);
    int data = 1;
    for(int i = 0;i <10;i++ )
    {
        //data *= i+1;
        stack_push(&s,&data,sizeof(int));
    }
    printf("栈顶元素%dn",*(int*)stack_top(&s));
    stack_pop(&s);
    printf("栈顶元素%dn",*(int*)stack_top(&s));
    stack_destroy(&s);
    if(stack_empty(&s))
    {
        printf("栈空n");
    }
    return 0;
}

我写的代码：（差不多）（我的有makefile   嘿嘿 鄙视老师 今天偷懒，注释都没有我写的多）

stack.h

#ifndef __STACK_H__
#define __STACK_H__
#include 
#include 
#include 
#include 

typedef struct node   //栈的节点
{
    void *data;
    struct node* next;
}node, *pnode;

typedef struct stack
{
    int size;
    node* top;    //栈顶指针
}stack;


void stack_init(stack *s );//初始化  
int stack_push(stack *s,const void *data_ptr,const int size  ); //入栈
int stack_pop(stack *s ); //出栈
void * stack_top(stack* s); //获取栈顶元素
int stack_size(stack *s ); //获取栈的元素个数
void stack_delete(stack *s); //销毁栈
bool stack_empty(stack *s); //判断栈是否为空





#endif

stack.c

#include
#include
#include
#include
#include
#include
#include"stack.h"

void stack_init(stack *s )//初始化
{
       if(s==NULL)
       {
              return;
       }
       s->size=0;
       s->top=NULL;

}  



int stack_push(stack *s,const void *data_ptr,const int size  ) //入栈
{
       if(s==NULL ||data_ptr==NULL|| size <=0 )
       {
              return -1;
       }
       node* temp = (node* )malloc (sizeof(node));
       if(temp==NULL)
       {
              return -2;
       }
       temp->data=malloc(size);
       if(temp->data==NULL)
       {
              return -3;
       }
       memcpy(temp->data,data_ptr,size);
       temp->next=s->top;   //跟单链表的头部插入差不多
       s->top=temp;
       (s->size)++;
       return 1;
}

int stack_pop(stack *s ) //出栈
{

       if(s==NULL)
       {
              return -1;
       }  
       node* temp=s->top;
       int a=*(int *)temp->data;  //获取头部的数据
       s->top=temp->next;
       free(temp->data);
       free(temp);
       --(s->size);
       return a;
}
void * stack_top(stack* s) //获取栈顶元素
{
       if(s==NULL)
       {
              return NULL;
       }  
       return s->top->data;
}
int stack_size(stack *s )//获取栈的元素个数
{
       if(s==NULL)
       {
              return -1;
       }  
       return s->size;
}
void stack_delete(stack *s) //销毁栈
{
       if(s==NULL)
       {
              return;
       }  
       while(s->size!=0)
       {
           stack_pop(s);   
       }  
       printf("栈已销毁！n");
}

bool  stack_empty(stack *s ) //判断栈是否为空
{
       if(s==NULL)
       {
              return true;
       } 
       else  if (s->size==0)
       {
              return true;
       }
       else
       {
              return false;
       }
}

main.c

#include
#include
#include
#include
#include
#include
#include"stack.h"

stack s;
int main(int argc,char *argv[])
{
       int m;
       stack_init(&s);
       for(int i=0;i<10;i++)
       {
              m=stack_push(&s,&i,4);
              printf("m=%dn",m);
       }
       printf("栈的元素个数：%dn",stack_size(&s));
       printf("栈顶元素： %dn",*(int *)stack_top(&s));
       for(int i=0;i<5;i++)
       {
             m=stack_pop(&s);
             printf("出栈元素为：%dn",m);
       }
       stack_delete(&s);
       if(stack_empty(&s))
       {
          printf("栈元素没了！n");           
       }
       return 0;
}

makefile

stack :main.o stack.o
	gcc -g -o stack main.o stack.o
main.o:main.c
	gcc -g -c main.c -o main.o
stack.o:stack.c
	gcc -g -c stack.c -o stack.o

加油：

物质的贫穷，能摧毁你一生的尊严，精神的贫穷，能耗尽你几世的轮回。人生没有白走的路，人生没有白读的书，你读过的书，走过的路，会在不知不觉中改变你的认知，悄悄帮你擦去脸上的无知和肤浅。书便宜，但不意味知识的廉价，虽然读书不一定功成名就，不一定能让你锦绣前程，但它能让你说话有德，做事有余，出言有尺，嬉闹有度！