数据结构 - 堆栈（通用数据结构）

堆栈是一种特殊的线性表，数据从栈顶进从栈顶出，遵循“先进后出”的原则。
堆栈的实现方式很多，以C语言为例，堆栈可以是顺序堆栈（数据存储在连续的地址空间内），也可以是链式堆栈（地址不连续，通过链式指针链接），本文介绍的就C语言实现的通用数据结构型的顺序堆栈。

参考数据结构 - 队列（顺序队列、通用数据类型）类似的思路，在堆栈初始化时候，完成堆栈空间的分配，并记录该空间的基地址，同样记录栈顶的位置，在出入栈时动态变化，采用以下的宏定义就可以实现访问数组式的访问到堆栈成员。

#define ARRAY_AT(arr, size, index)	(*(((unsigned char *)arr)+(index)*(size)))

#ifndef __stack_H
#define __stack_H

typedef struct 
{
	void			*arr;			
	unsigned int	item_size;		
	unsigned int	stack_len;		
	unsigned int	items_cnt;		
	unsigned int	top;			
	unsigned char	state;			
}STACK;	

unsigned char stack_init(STACK *stack, unsigned int item_size, unsigned int stack_len);
unsigned char stack_empty(STACK *stack);
unsigned char stack_full(STACK *stack);
unsigned int stack_cnt(STACK *stack);
unsigned char stack_push(STACK *stack, void *data);
unsigned char stack_pop(STACK *stack, void *data);
void stack_clean(STACK *stack);
void stack_free(STACK *stack);

#endif

STACK结构体当中，包含了存放队列成员空间的基地址（*arr），每个成员所占用的空间大小（item_size），栈深（stack_len），堆栈成员计数（items_cnt），栈顶索引。

#include "stack.h"
#include 
#include 

#ifndef ARRAY_AT(arr, size, index)
#define ARRAY_AT(arr, size, index)	(*(((unsigned char *)arr)+(index)*(size)))
#endif


unsigned char stack_init(STACK *stack, unsigned int item_size, unsigned int stack_len)
{
	stack->arr = malloc(item_size * stack_len);		
	if (stack->arr != NULL)
	{
		stack->item_size = item_size;
		stack->stack_len = stack_len;
		stack->top = 0;
		stack->state = 0;
		stack->items_cnt = 0;
	}
	else 
	{
		return 0;
	}

	memset(stack->arr, 0, item_size * stack_len);

	return 1;
}


unsigned char stack_empty(STACK *stack)
{
    if (stack->state == 0)
	{
		return 1;
	}
    else
	{
		return 0;
	}
}


unsigned char stack_full(STACK *stack)
{
	if (stack->top >= stack->stack_len - 1 && stack->state == 1)
	{
		return 1;
	}
    else
	{
		return 0;
	}
}


unsigned int stack_cnt(STACK *stack)
{
	if (stack->state == 1)
	{
		return stack->top + 1;
	}
    else
	{
		return 0;
	}
}


unsigned char stack_push(STACK *stack, void *data)
{
	if (stack_full(stack))
	{
		return 0;
	}
	else
	{
		if (stack->state == 1)
		{
			stack->top++;
		}
		
		memcpy(&ARRAY_AT(stack->arr, stack->item_size, stack->top), data, stack->item_size);
		stack->items_cnt++;
		stack->state = 1;
		return 1;
	}
}


unsigned char stack_pop(STACK *stack, void *data)
{
    if(stack_empty(stack))
    {
		return 0;
    }
    else
    {
		
		memcpy(data, &ARRAY_AT(stack->arr, stack->item_size, stack->top), stack->item_size);
		stack->items_cnt--;
		if(stack->top == 0)							
		{
			stack->state = 0;
		}
		else 
		{
			stack->top--;
		}
		return 1;
    }
}


void stack_clean(STACK *stack)
{
	stack->top = 0;
	stack->state = 0;
	stack->items_cnt = 0;
}


void stack_free(STACK *stack)
{
	stack->top = 0;
    stack->state = 0;
	stack->items_cnt = 0;
	stack->stack_len = 0;
	stack->item_size = 0;
	free(stack->arr);
	stack->arr = NULL;
}

堆栈操作函数和队列差不多，包含初始化、入栈、出栈、清空、释放等操作。不对每行代码进行细述，直接看测试代码。

#include 
#include "stack.h"
#include 

typedef struct 
{
	char name[10];
	int height;
	int age;
}STUDENT;

int main()
{
	STACK stack;
	STACK s_student;
	int i = 0;
	int data = 0;
	STUDENT student;
	int stack_count = 0;

	stack_init(&stack, sizeof(int), 12);
	stack_init(&s_student, sizeof(STUDENT), 6);

	for (i = 0; i < stack.stack_len; i++)
	{
		data = i + 10;
		stack_push(&stack, &data);
	}

	for (i = 0; i < s_student.stack_len; i++)
	{
		student.age = 18 + i;
		student.height = 180 - i;
		sprintf(student.name, "student%d", i+1);
		stack_push(&s_student, &student);
	}

	stack_pop(&stack, &data);
	stack_pop(&stack, &data);
	stack_push(&stack, &data);
	stack_push(&stack, &data);
	printf("stack cnt: %drn", stack.items_cnt);
	
	stack_count = stack_cnt(&stack);
	for (i = 0; i < stack_count; i++)
	{
		if (stack_pop(&stack, &data) == 1)
		{
			printf("%drn", data);
		}
	}

	stack_count = stack_cnt(&s_student);
	for (i = 0; i < stack_count; i++)
	{
		if (stack_pop(&s_student, &student) == 1)
		{
			printf("name: %s, age = %d, height = %drn", student.name, student.age, student.height);
		}
	}

	getchar();
	return 0;
}

结果：

最后的最后，本人才疏学浅，此代码仅供参考交流，本人如有叙述错误，麻烦各位指正，有什么好的建议欢迎留言。