栈与队列恰好相反，栈是一种后进先出的结构（Last In First Out）LIFO,你可以想像成一个容器，最先倒进去的最后倒出来

本文介绍的是链式栈结构，在数据结构中几乎用的都是这种存储形式，这里要把数据结构的栈和内存的栈空间区别开，这里的栈是一种数据结构，内存的栈是指内存的存取方式类似于栈这种形式，因此取名栈空间。

• 栈的结构,这里也是封装了一个链表，在此基础上加了一个栈顶指针，和栈内的数据个数。

typedef struct StackNode
{
	int data;
	struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
	LinkStackPtr top;
	int count;
}LinkStack;

• 初始化一个栈,此时栈内部的链表没有任何节点，也就是栈内没有任何数据

void init_stack(LinkStack *S)
{
	S->top = NULL;
	S->count = 0;
}

• push操作，入栈操作
  这里需要注意的是，这里不是按照单链表的方式连接到上一个节点的尾部，这里相当于单链表反向操作，即是把新加入的节点的next指向链表表头的位置（栈顶节点top），并且把top更新为新插入的节点
  为什么这么做？原因在于删除的节点为链表最新加入的节点，这样便于删除这个节点，而不用遍历整个链表

int push(LinkStack *S,int data)
{
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(struct StackNode));
	s->data = data;
	s->next = S->top;	
	/* 逆向的链表 */
	S->top = s;
	S->count ++;
	return 1;
}

• pop操作，出栈操作，就是把栈顶指针top更新为top->next,并把top节点free掉

int pop(LinkStack *S, int *p_dat)
{
	LinkStackPtr p;
	if(S == NULL || S->top == NULL)
		return 0;
	
	if(p_dat != NULL)
	*p_dat = S->top->data;
	
	p = S->top->next;
	free(S->top);
	S->top = p;
	S->count--;
	return 1;
}

• 遍历整个栈,从栈顶一直遍历到栈底

int print_all(LinkStack *S)
{
	if(S == NULL || S->top == NULL)
		return 0;
    do{
		printf("data is %d \n",S->top->data);
		S->top = S->top->next;
	   }while(S->top != NULL);
	return 1;
}

注意栈结构中的链表操作有所不同