数据结构-栈的C语言实现(1、顺序存储 2、链式存储)

栈的顺序存储方式

我们的思路就是使用一个结构体，来存储栈节点，里面有数据的地址和大小，然后再针对这个结构体做一些栈操作封装

struct sstack
{
   	void *data[MAX];
    int size;
}

这里存储元素地址使用的是一个void 的数组，所以是叫顺序存储*

具体实现代码如下：

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

#define MAX  1000
struct sstack
{
	void* data[MAX];
	int size;
}sstack;
//定义一个给用户使用的栈栈结构体指针，不告诉用户类型
typedef void* seqstack;

//栈的初始化
seqstack*  init_stack()
{
	struct sstack * stack= (struct sstack*)malloc(sizeof(sstack));
	if (stack == NULL)
	{
		return NULL;
	}
	//先清空用来存储栈的结构体
	memset(stack, 0, sizeof(stack));
	stack->size = 0;
	return (seqstack*) stack;
}
//栈的push
void push_stack(seqstack stack, void* data)
{
	if (stack == NULL || data == NULL)
	{
		return;
	}
	struct sstack * mystack =(	struct sstack * ) stack;
	//判断栈是否满了
	if(mystack->size>=MAX)
    {
        return ;
    }
    //入栈
	mystack->data[mystack->size]=data;
	mystack->size++;

}
//栈的pop出栈
void pop_stack(seqstack stack)
{	
    if(stack==NULL)
    {

        return ;
    }
   struct  sstack* mystack=( struct  sstack*)stack;
   //判断栈是否为空
    if(mystack->size<=0)
    {

        return ;
    }
    //出栈,数组存储的最后一个元素的地址置为NULL
    mystack->data[mystack->size-1]=NULL;
	//数组大小减一
    mystack->size--;

}
//获取栈顶元素
void * top_stack(seqstack stack)
{
    if(stack==NULL)
    {
        return NULL;
    }
    struct sstack *mystack=( struct sstack *)stack;
    if(mystack->size==0)
    {

        return NULL;
    }
    return mystack->data[mystack->size-1];

}
int isempty_stack(seqstack stack)
{

    if(stack==NULL)
    {
        return 0;
    }
      struct sstack *mystack=( struct sstack *)stack;
      if(mystack->size==0)
      {

          return 0;
      }
    //非空返回1表示真，因为C语言非0为真
      return 1;
}
void destory_stack(seqstack stack)
{
    if(stack ==NULL)
    {
        return ;
    }
    free(stack);
    stack=NULL;
}
struct Person
{
    char name[64];
    int age;

};
void test()
{

	//初始化栈
	seqstack stack = init_stack();


	//创建数据
	struct Person p1 = { "aaa", 10 };
	struct Person p2 = { "bbb", 20 };
	struct Person p3 = { "ccc", 30 };
	struct Person p4 = { "ddd", 40 };
	struct Person p5 = { "eee", 50 };
	struct Person p6 = { "fff", 60 };
	push_stack(stack,&p1);
	push_stack(stack,&p2);
	push_stack(stack,&p3);
	push_stack(stack,&p4);
	push_stack(stack,&p5);
	push_stack(stack,&p6);

	struct sstack * mystack=(struct sstack *)stack;

	while(isempty_stack(stack))
    {

       struct Person *person=(struct Person *)top_stack(stack);
       printf("栈顶元素是：%d,     ,%s\n",person->age,person->name);
       pop_stack(stack);
    }
    destory_stack(stack);
}
int main()
{
    test();
    return 0;
}

栈的链式存储

具体实现方法J就是：建立一个节点结构体，来存储数据的地址如下：

struct linknode
{
	void *data;
	struct linknode *next;
}

然后建立一个结构体作为栈的实现

struct linkstack
{
	struct linknode *header;
	int size;//表示栈的大小
}

具体实现代码如下：

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

//链式存储的
struct linknode
{
   void *data;
   struct linknode * next;
};
struct  linkstack
{
    struct linknode  header;
    int size;
};
typedef void * linkstack;
//栈的初始化
linkstack init_linkstack()
{
    struct linkstack * stack=malloc(sizeof(linkstack));
    stack->header.next=NULL;
    stack->size=0;
    return stack;
}
//栈的push
void push_linkstack(linkstack linkstack,void* data)
{
    if(linkstack==NULL ||data==NULL)
    {
        return ;
    }
    struct linkstack *mystack=(  struct linkstack *)linkstack;
    struct linknode *linknode =(    struct linknode *)data;
    linknode->next=mystack->header.next;
    mystack->header.next=linknode;
    mystack->size++;

}
//栈的pop
void pop_linkstack(linkstack linkstack)
{
    if(linkstack==NULL)
    {
        return ;
    }
     struct linkstack *mystack=(  struct linkstack *)linkstack;
    if(mystack->size<=0)
    {
        return ;
    }
    struct linknode *first_node=mystack->header.next;
    mystack->header.next=first_node->next;

    mystack->size--;

}
//获取栈顶元素
void * top_linkstack(linkstack linkstack)
{
    if (linkstack==NULL)
    {
        return NULL;
    }
     struct linkstack *mystack=(struct linkstack *)linkstack;
     if(mystack->size<=0)
     {

         return NULL;
     }
     return mystack->header.next;
}
//判断栈是否为空
int isempty_linkstack(linkstack linkstack)
{
    if(linkstack==NULL)
    {

        return 0;
    }
    struct linkstack *mystack=(struct linkstack *)linkstack;
    if(mystack->size > 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
//销毁栈
void destroy_linkstack(linkstack linkstack)
{
    if(linkstack==NULL)
    {
        return;
    }
    free(linkstack);
    linkstack=NULL;
}
struct Person
{
    char name[64];
    int age;

};
void test()
{

	//初始化栈
	struct linkstack*  stack = init_linkstack();


	//创建数据
	struct Person p1 = { "aaa", 10 };
	struct Person p2 = { "bbb", 20 };
	struct Person p3 = { "ccc", 30 };
	struct Person p4 = { "ddd", 40 };
	struct Person p5 = { "eee", 50 };
	struct Person p6 = { "fff", 60 };
	push_linkstack(stack,&p1);
	push_linkstack(stack,&p2);
	push_linkstack(stack,&p3);
	push_linkstack(stack,&p4);
	push_linkstack(stack,&p5);
	push_linkstack(stack,&p6);

	struct linkstack * mystack=(struct sstack *)stack;
    printf("size=%d\n",mystack->size);
	while(isempty_linkstack(stack))
    {
      struct Person *person=(struct Person *)top_linkstack(stack);
      printf("栈顶元素是：%d,     ,%s\n",person->age,person->name);
      pop_linkstack(stack);
    }
    destroy_linkstack(stack);
}
int main()
{
    test();
    return 0;
}

总结：自己手动把这两种栈实现，其中也是有很多问题了，大多是自己思路没有捋清楚，现在整理一下如下：

1. 栈的初始化操作，对于顺序栈，就是，建立一个栈结构体在堆区(使用mallco)，最后再把这个栈结垢体初始化就好，size=0，然后再返回这个栈结垢体的地址。1.对于链式栈就是初始化栈结垢体 2、然后初始化赋值，size=0；3、header.next=NULL;同理再把栈结垢体返回

2. 栈的push（插入）,对于顺序栈，就是1、 把新数据地址存入结垢体中的data[]数组，2、size++

   **对于链式栈，**1、把新数据的地址存入链表结垢（注意是插入到链表头节点），2、size++

3. 栈的pop（出栈），**对于顺序栈，**1、data[size-1]=NULL，2、size-- ** 对于链式栈，**就是1、链表最后一个节点为NULL， 2、size–