/* 栈ADT链表实现的类型声明 */
struct Node;
typedef struct Ndoe *PtrToNode;
typedef PtrToNode Stack;
struct Node{
ElementType Element;
Stack Next;
};
/* 测试是否为空栈 */
int
IsEmpty( Stack S )
{
return S->Next == NULL;
}
/* 创建空栈 */
Stack
CreateStack(void)
{
Stack S;
S = malloc(sizeof(struct Node));
if(S == NULL)
FatalError("no space");
S->Next = NULL;
return S;
}
/* 清空栈 */
/* 直接删除链表与无数次Pop异曲同工 */
void
MakeEmpty( Stack S)
{
Stack p,TmpCell;
p = S->Next;
S->Next = NULL;
while(p != NULL )
{
TmpCell = p->Next;
free(p);
p = TmpCell;
}
}
/* 书上的实现方法 */
void
MakeEmpty( Stack S )
{
if(S == NULL)
Error("Must create a stack");
else
{
while(!IsEmpty(S))
Pop(S);
}
}
/* Pop 例程 */
void
Pop( Stack S )
{
PtrToNode FirstCell;
FirstCelll = S->Next;
S->Next = FirstCell->Next;
free(FirstCell);
}
/* Push 进栈操作 */
void
Push( Stack S, ElementType X )
{
PtrToNode TmpCell;
TmpCell = malloc( sizeof( struct Node ) );
if( TmpCell == NULL )
FatalError("out of space");
else
{
TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
}
/* 返回栈顶元素 */
ElementType
Top( Stack S )
{
if( IsEmpty( S ) )
Fata
}