数据结构之栈

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

/*
声明结构体类型struct node,
包含数据域data和指针域next,属于一个结点类型
*/
typedef struct node
{
int data;
struct node* next; //存放指向下一个结点的地址
}Node,*PNode;

/*
声明一个结构体类型，包含栈顶和栈底元素，
Stack替换struct stack,PStack替换struct stack*
*/
typedef struct stack
{
PNode Top;
PNode Bottom;
}Stack,*PStack;

/*
声明函数，初始化栈，进栈，出栈，输出栈中元素函数
*/
void init_stack(PStack);
void push(PStack,int);
bool pop(PStack,int*);
void traverse_stack(PStack);

int main()
{
int val; //定义变量val,存放出栈的元素
Stack sta; //定义struct stack变量sta
init_stack(&sta); //初始化栈
push(&sta,1); //元素进栈
push(&sta,2);
push(&sta,3);
push(&sta,4);
push(&sta,5);
push(&sta,6);
putchar(‘\n‘);
traverse_stack(&sta); //遍历栈中元素
putchar(‘\n‘);
if(pop(&sta,&val)) //出栈操作
{
printf("出栈的元素：%d\n",val);
putchar(‘\n‘);
traverse_stack(&sta);
}
return 0;
}

/*
初始化栈，传入sta的地址，申请一块struct node*类型的内存，
其指针域赋值为空，栈顶和栈底都指向这块内存
*/
void init_stack(PStack psta)
{
psta->Bottom=(PNode)malloc(sizeof(Node)); //栈底指向申请的内存
psta->Top=psta->Bottom;
psta->Bottom->next=NULL; //设置PNode变量的指针域为空
return;
}

/*
元素进栈，传入sta的地址和插入元素值，
先申请一块类型为PNode内存，将其指针域赋值为栈顶元素，栈顶赋值为这块内存的地址
*/
void push(PStack psta,int val)
{
PNode PNew=(PNode)malloc(sizeof(Node)); //定义struct node*类型的变量PNew指向一块申请的内存
PNew->data=val; //将PNew的数据域赋值为val
PNew->next=psta->Top; //PNew的指针域赋值为栈顶元素
psta->Top=PNew; //栈顶元素指向PNew
printf("进栈元素：%d\n",val);
return;
}

/*
遍历输出栈中元素，传入sta的地址，
先判断栈是否为空，如果为空则不需要遍历，
定义一个PNode变量p指向栈顶指向的内存，while遍历栈中元素，知道p等于栈底的值
*/
void traverse_stack(PStack psta)
{
if(psta->Top==psta->Bottom) //判断栈是否为空
{
printf("栈内没有元素，怎么遍历！\n");
}
else
{
PNode p=psta->Top; //定义一个指向栈顶指向内存的struct node*变量p
printf("栈内元素遍历：\n");
while(p!=psta->Bottom) //循环条件，p不等于栈底元素
{
printf("%d\t",p->data);
p=p->next; //p指向下一块内存
}
printf("\n");
}
return;
}

/*
出栈，传入sta的地址和val的地址，
先判断栈是否为空，如果为空则不能进行出栈操作，
定义一个PNode变量p指向栈顶指向的内存，将栈顶元素赋值为下一个元素的地址，释放p的内存
*/
bool pop(PStack psta,int* val)
{
if(psta->Top==psta->Bottom)
{
printf("栈内没有元素，出不了栈的！\n");
return false;
}
else
{
PNode p=psta->Top; //定义一个指向栈顶指向内存的struct node*变量p
*val=p->data; //将p指向的数据域的值赋值给*val
psta->Top=p->next; //栈顶指向下一个元素
free(p); //释放p指向的内存
return true;
}
}

数据结构之栈

原文：http://www.cnblogs.com/swcks/p/4931176.html