数据结构和算法--栈的链式实现

柔光的暖阳◎ 2022-07-15 08:00 168阅读 0赞

//链式栈的实现（类似与单链表）
    
    #include <stdio.h>
    #include <stdlib.h>
    //定义数据类型
    typedef int datatype_t;
    
    //定义结构体
    typedef struct node{
    	datatype_t data;
    	struct node *next;
    }linkstack_t;
    
    //创建一个空的栈
    linkstack_t *linkstack_create()
    {
    	linkstack_t *s = (linkstack_t *)malloc(sizeof(linkstack_t));
    
    	s->next = NULL;
    
    	return s;
    }
    
    //判断栈是否为空
    int linkstack_empty(linkstack_t *s)
    {
    	return s->next == NULL ? 1 : 0;
    }
    
    //入栈（压栈）(单链表的头插法)
    int linkstack_push(linkstack_t *s, datatype_t value)
    {
    	linkstack_t *temp = (linkstack_t *)malloc(sizeof(linkstack_t));
    	temp->data = value;
    
    	temp->next = s->next;
    	s->next = temp;
    
    	return 0;
    }
    
    //打印数据
    int linkstack_show(linkstack_t *s)
    {
    	while(s->next != NULL)
    	{
    		s = s->next;
    		printf("%d ", s->data);
    	}
    
    	putchar(10);
    
    	return 0;
    }
    
    //出栈（弹栈） (类似与单链表的头删法)
    datatype_t linkstack_pop(linkstack_t *s)
    {
    	linkstack_t *temp = NULL;
    	datatype_t value = 0;
    
    	if(linkstack_empty(s))
    	{
    		printf("linkstack is empty\n");
    		return (datatype_t)-1;
    	}
    
    	temp = s->next;
    	s->next = temp->next;
    
    	value = temp->data;
    
    	free(temp);
    	temp = NULL;
    
    	return value;
    }
    
    int main(int argc, const char *argv[])
    {
    	linkstack_t *s = linkstack_create();
    
    	linkstack_push(s, 10);
    	linkstack_push(s, 20);
    	linkstack_push(s, 30);
    	linkstack_push(s, 40);
    	linkstack_push(s, 50);
    	linkstack_show(s);
    
    	printf("%d ", linkstack_pop(s));
    	printf("%d ", linkstack_pop(s));
    	printf("%d ", linkstack_pop(s));
    	printf("%d ", linkstack_pop(s));
    	printf("%d ", linkstack_pop(s));
    
    	printf("\n");
    	
    	return 0;
    }