用双向链表实现一个栈

àì夳堔傛蜴生んèń 2022-08-24 00:43 173阅读 0赞

前面我们已经造好了一个轮子——双向链表，那么我们可以利用这个轮子做一个栈。

入栈：我们采用链表的头插

获得栈顶的元素：把头部元素拷贝到用户数据区

出栈：先把头部的元素拷贝到用户数据区，然后删除这个节点

好的，看一下头文件吧。

#pragma once
    #include "dlist.h"
    
    struct stack_info {
    	struct dlist_info *dlist;// 双向链表的指针
    
    	int (*push)(struct stack_info *info, 
    			const  void *data, size_t size);//入栈
    
    	int (*top)(struct stack_info *info,
    			void *data, size_t size);//获得栈顶的元素
    
    	int (*pop)(struct stack_info *info,
    			void *data, size_t size);//出栈
    
    	int (*is_empty)(struct stack_info *info);
    };
    
    void stack_init(struct stack_info *info);
    void stack_destroy(struct stack_info *info);

接下来看实现。

static int stack_push(struct stack_info *info, 
                            const  void *data, size_t size)
    {
    	info->dlist->add_head(info->dlist, data, size);
    	return 0;	
    }

是不是很简单呢？直接头插就可以了。

static int stack_is_empty(struct stack_info *info)
    {
    	
    	return  dlist_is_empty(info->dlist);	
    }

static int stack_top(struct stack_info *info,
                            void *data, size_t size)
    {
    	if (stack_is_empty(info)) {
    		return -1;
    	}else{
    		memcpy(data, info->dlist->head->next->data, size);
    	}
    	
    	return 0;
    }

top方法，注意，这个方法只会得到栈顶元素的值，并不会删除栈顶的元素。

static int stack_pop(struct stack_info *info,
                            void *data, size_t size)
    {
    	if (stack_top(info, data, size) < 0) {
    		return -1;// means empty
    	}else{
    		info->dlist->del(info->dlist->head->next);
    	}
    	return 0;
    }

pop方法，不用多说。

构造和析构：

void stack_init(struct stack_info *info)
    {
    	info->dlist = (struct dlist_info *)malloc(sizeof(struct dlist_info));
    	
    	if (info->dlist != NULL) {
    		dlist_init(info->dlist);
    	}else{
    		printf("stack initialize failed.\n");
    		return ;
    	}
    
    	info->push = stack_push;
    	info->pop = stack_pop;
    	info->top = stack_top;
    	info->is_empty = stack_is_empty;
    }
    
    
    
    void stack_destroy(struct stack_info *info)
    {
    	dlist_destroy(info->dlist);
    	free(info->dlist);	
    }

最后我们看一下单元测试

void print_student(void* data)
    {
    	struct student *p = (struct student *)(data);
    	printf("Name: %15s  Age:%d\n",p->name,p->age);
    	
    }
    
    
    
    START_TEST(case_2)
    {
    	struct student students[] = {
       {"WangDong",18},{"LiuMing",19},{"SunYazhou",21},{"QingYun",27}};
    	struct stack_info stack;
    	stack_init(&stack);
    
    	struct student stu_tmp;
    
    	ck_assert_msg(stack.is_empty(&stack)==1);
    	int i = 0;
    	for(;i<(sizeof(students)/sizeof(students[0]));++i)
    		stack.push(&stack,students+i,sizeof(students[0]));
    	while(stack.is_empty(&stack)!=1)
    	{
    
    		stack.pop(&stack,&stu_tmp,sizeof(students[0]));
    		print_student(&stu_tmp);
    	}
    		
    }
    END_TEST

简单的测一下pop和push，结果如下：

Running suite(s): stack\_(using\_dlist)

Name:         QingYun  Age:27

Name:       SunYazhou  Age:21

Name:         LiuMing  Age:19

Name:        WangDong  Age:18

100%: Checks: 1, Failures: 0, Errors: 0

（完）