栈属于数据结构，它本质上属于线性表，只是受限的线性表。

            我们今天来讨论下动态栈也就是链栈的相关问题。

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

typedef struct Node
{
	int data;
	struct Node* pNext;
}NODE, *PNODE;

typedef struct Stack
{
	PNODE pTop;    //栈顶
	PNODE pBottom; //栈底
}STACK, *PSTACK;
//初始化空栈
void InitStack(PSTACK pS)
{
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if(NULL == pS->pTop)
	{
		printf("ERROR \n");
		exit(-1);
	}
	else
	{
		pS->pBottom = pS->pTop;
		pS->pBottom->pNext = NULL;
		//pS->pTop->pNext = NULL;
	}	
}
//遍历栈
void TraverseStack(PSTACK pS)
{
	printf("Now start traverse the stack elem : ");
	PNODE p = pS->pTop;
	while(p != pS->pBottom)
	{
		printf("%d  ", p->data);
		p = p->pNext;
	}
	printf("\n");
}
//压栈
void PushStack(PSTACK pS, int Val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = Val;
	pNew->pNext = pS->pTop;
	pS->pTop = pNew; 
}
//判断栈空
bool IsEmptyStack(PSTACK pS)
{
	if(pS->pTop == pS->pBottom)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//出栈
int PopStack(PSTACK  pS, int * pVal)
{
	if(IsEmptyStack(pS))
	{
		printf("ERROR stack is  empty  \n");
		exit(-1);
	}
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;

		pS->pTop = r->pNext;	
		free(r);
		r = NULL;
	}

	return true;
}
//清空栈
void ClearStack(PSTACK pS)
{
	printf("Now start clear the stack  ... ");
	if(IsEmptyStack(pS))
	{
		return ;
	}
	PNODE  p = pS->pTop;
	PNODE  q = NULL;

	while(p != pS->pBottom)
	{
		q = p->pNext;
		free(p);
		p = q;
	}
	pS->pTop = pS->pBottom;

	puts("\n");
}
//主程序
int main(void)
{
	STACK   S;

	InitStack(&S);//造成一个空栈
	//压栈
	
	PushStack(&S, 1);
	PushStack(&S, 2);
	PushStack(&S, 3);
	PushStack(&S, 4);
	//遍历	
	TraverseStack(&S);

	//弹出栈顶元素
	int val = 0;
	if(PopStack(&S, &val))
	{
		printf("pop stack top  elem is %d  \n\n", val);
	}

	//遍历
	TraverseStack(&S);
	//清空栈
	ClearStack(&S);
	//遍历
	TraverseStack(&S);

	return 0;
}

本文出自 “享受科技带来的快乐” 博客，请务必保留此出处http://liam2199.blog.51cto.com/2879872/1532114