栈是限定在只能在尾部操作(插入或删除)的线性表。

栈是按照后进先出的，LIFO。

一般来说，栈应该是无上限的，即如果栈满了，应该可以自动扩充。

定义如下的栈结构：

struct Stack
{
	int* base;
	int* top;
	int size;
};

注意，top指向的不是栈顶而是栈顶的下一个元素！

当base==NULL或者top==base时，可以认为栈是空的。

基本操作有push、pop、top(取得栈顶元素但不弹出栈)、isempty。

代码如下：

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

#define STACK_INIT_SIZE 100
#define STACK_INC_SIZE 20

struct Stack
{
	int* base;
	int* top;
	int size;
};

void stack_init(struct Stack* stack)
{
	stack->size = 0;
	stack->base = stack->top = NULL;
	// malloc
	stack->base = (void*)malloc(sizeof(int)*STACK_INIT_SIZE);
	if(!stack->base)
	{
		return ;
	}
	stack->top = stack->base;
	stack->size = 0;
}

void stack_free(struct Stack* stack)
{
	if(stack->base)
	{
		free(stack->base);
	}
	stack->base = stack->top = NULL;
	stack->size = 0;
}

void stack_push(struct Stack* stack, int data)
{
	// check if enough stack space
	if(stack->top - stack->base >= stack->size)
	{
		stack->base = (void*)realloc(stack->base, sizeof(int)*(stack->size+STACK_INC_SIZE));
		if(!stack->base)
		{
			return ;
		}
		stack->size += STACK_INC_SIZE;
	}
	// Push
	//*stack->top = data;
	//stack->top++;
	*stack->top++ = data;
}

void stack_pop(struct Stack* stack, int* data)
{
	// Pop
	//stack->top--;
	//*data = *stack->top;
	*data = *--stack->top;
}

//有Bug！！需要判断栈是否为空！
void stack_top(struct Stack* stack, int* data)
{
    // Top
    if(!stack_isempty(stack))
    {
        *data = *(stack->top-1);
    }
}

void stack_print(struct Stack* stack)
{
	int* p = stack->base;
	while(p!=stack->top)
	{
		printf("%d ", *p);
		p++;
	}
}

int stack_isempty(struct Stack* stack)
{
	if(stack->base==NULL || stack->base == stack->top)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main()
{
	struct Stack stack;
	int i;
	int elem;
	stack_init(&stack);
	// IsEmpty
	printf("IsEmpty:%d\n", stack_isempty(&stack));
	// Push
	for(i=0; i<200; i++)
	{
		stack_push(&stack, i);
	}
	for(i=0; i<100; i++)
	{
		stack_pop(&stack, &elem);
	}
	stack_top(&stack, &elem);
	printf("%d\n", elem);
	// IsEmpty
	printf("IsEmpty:%d\n", stack_isempty(&stack));
	// Print
	stack_print(&stack);
	stack_free(&stack);
	return 0;
}