由一个例子学习栈的内容介绍
/*
================================================================= 作者：rerli 时间：2003-12-03(修改稿） 目的：由一个例子学习栈。栈应用详解：
栈的实现可以用数组，亦可用链表。
下面讲讲这两种实现栈结构的详细程序，并分别看看： 用栈改递归为非递归，计算Ackermann函数A(n,x,y)。 ================================================================== *//*
================================================================== 第二种：链表 用链表实现的栈称为链接栈。很显然链接栈没有栈满之说了，它是来者不拒啊！ 栈顶是链表的第一个元素； 栈底是链表的最后一个元素； 链表的头指针就是栈顶指针。 =================================================================== */#include <stdlib.h>
#include <stdio.h> #define NULL 0typedef 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"); }