/*
=================================================================
作者：rerli
时间：2003-12-03(修改稿）
目的：由一个例子学习栈。
栈应用详解：
栈的实现可以用数组，亦可用链表。
下面讲讲这两种实现栈结构的详细程序，并分别看看：
用栈改递归为非递归，计算Ackermann函数A(n,x,y)。
==================================================================
*/
/*
==================================================================
第二种：链表
用链表实现的栈称为链接栈。很显然链接栈没有栈满之说了，它是来者不拒啊！
栈顶是链表的第一个元素；
栈底是链表的最后一个元素；
链表的头指针就是栈顶指针。
===================================================================
*/
#include <stdlib.h>
#include <stdio.h>
#define NULL 0
typedef struct node
{
int n;
double x;
double y;
}NODE;
typedef struct lnode
{
NODE data;
struct lnode *next;
}LNODE;
#define LEN sizeof(LNODE)
/*栈的需要变量*/
typedef enum {false,true}bool; /*定义bool类型*/
static LNODE *p_stack=NULL; /*定义栈指针变量*/
/*
==================================================================
栈空
| |
|_____|
|_____|
|_____|
NUll <---p_stack
出栈前
| |
|_____|
|__1__|<---p_stack
|__0__|
出栈后
| |
|_____|
|__1__|
|__0__|<---p_stack
从上图可知:
1、出栈前，栈顶指针指向的是栈顶元素的地址；
2、出栈后，栈顶指针指向的是原栈顶元素下一个元素的地址。
3、这种链接栈显然更符合栈的定义。相比之下，它比数组（或指针）更容易理解一些。
4、显然若我们用POP()栈顶值后，用*p_stack取值，则得到值不和pop()出来的值一模一样。
5、注意到上面的4和前面数组（或指针）栈的4有很大的差别就是根据栈顶指针取出来的值不同，
这样导致我们可以用数组（或指针）栈可以方便实现求Ackermann函数A(n,x,y)，而链接栈则
不能实现，除非我们改结构。
======================================================================
*/
/*
======================================================================
注意到链接栈比数组（或指针）栈少了几个函数，上面的变量也少了。
======================================================================
*/
/*
==============================
功能：判断栈是否为空
返回：true or false
==============================
*/
bool Empty()
{
/*栈顶指针等于NULL,则栈空*/
return (p_stack==NULL);
}
/*
==============================
功能：入栈
返回：true or false
==============================
*/
bool Push(NODE p)
{
static LNODE *stack=NULL;
stack = (LNODE *)malloc(LEN); /*开辟一个节点的空间*/
if (stack != NULL)
{
stack->data = p; /*入栈*/
stack->next = p_stack; /*新节点的next指向原栈顶*/
p_stack = stack; /*栈顶指针指向新节点*/
free(stack); /*释放栈的内存*/
stack = NULL;
return true;
}
else
{
return false;
}
}
/*
==============================
功能：出栈
返回：出栈元素
==============================
*/
NODE Pop()
{
NODE p;
if (!Empty())
{
p = p_stack->data; /*出栈元素*/
p_stack = p_stack->next; /*更改栈顶指针*/
return p;
}
else
{
printf("stack is empty !\n");
}
}
void main(void)
{
NODE node1 = {3,1,2};
Push(node1);
printf("n=%d, x=%.2f, y=%.2f\n",(p_stack->data).n,(p_stack->data).x,(p_stack->data).y);
Pop();
/*根据下面的语句结果，我们可以判断以上实现的栈是否正确的：1正确，其他错误。*/
printf("%d",p_stack==NULL);
printf("\n");
system("pause");
}
