Stack

//用链表实现的栈
#ifndef _Stack_h
//#define _Stack_h
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void Push(ElementType X, Stack S);
void Pop(Stack S);
ElementType Top(Stack S);

#endif

#include<malloc.h>
#include<stdio.h>
#include<stdbool.h>
#include"stack.h"
#include"error.h"
struct Node
{
	ElementType data;
	PtrToNode Next;
};

int IsEmpty(Stack S)
{
	return S->Next == NULL;	
}
void MakeEmpty(Stack S)
{
	if(S == NULL)
		Error("Must use CreateStack first");
	while(!IsEmpty(S))
		Pop(S);
}

Stack CreateStack(void)
{
	Stack S = (Stack)malloc(sizeof(struct Node));
	if(S == NULL)
		FatalError("Out of space in CreateStack");
	MakeEmpty(S);
	return S;
}
void DisposeStack(Stack S)
{
	MakeEmpty(S);
	free(S);
}
void Push(ElementType X, Stack S)
{
	PtrToNode TmpCell = (PtrToNode)malloc(sizeof(struct Node));
	if(TmpCell == NULL )
		FatalError("Out of space in Push");
	else
	{
		TmpCell->data = X;
		TmpCell->Next = S->Next;
		S->Next = TmpCell;
	}
	
}
void Pop(Stack S)
{
	PtrToNode TmpCell;
	if(IsEmpty(S))
		Error("Empty Stack");
	TmpCell = S->Next;
	S->Next = S->Next->Next;
	free(TmpCell);
}
ElementType Top(Stack S)
{
	if(IsEmpty(S))
		Error("Empty Stack");
	return S->Next->data;
}


//用数组实现的栈
#ifndef _STACK_H

typedef int ElementType;
struct StackRecord;
typedef struct StackRecord *Stack;
int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
ElementType Top(Stack S);
void Push(ElementType X, Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);

#endif

#include<stdio.h>
#include"Stack.h"
#include"error.h"
#define EmptyTOS      (-1)
#define MinStackSize  (5 )
struct StackRecord
{
	int Capacity;
	int TopOfStack;
	ElementType *Array;
};

int IsEmpty(Stack S)
{
	return S->TopOfStack == EmptyTOS; 	
}

int IsFull(Stack S)
{
	return S->TopOfStack == S->Capacity;
}

Stack CreateStack(int MaxElements)
{
	Stack S;
	if(MaxElements < MinStackSize)
		Error("Stack size is too small");
	S = (Stack)malloc(sizeof(struct StackRecord));
	if(S == NULL)
		FatalError("Out of space!!");
	S->Array = (ElementType *)malloc(sizeof(ElementType) * MaxElements);
	if(S->Array == NULL)
		FatalError("Out of space!!");
	S->Capacity = MaxElements;
	MakeEmpty(S);
	return S;
}
void DisposeStack(Stack S)
{
	if(S != NULL)
	{
		free(S->Array);
		free(S);
	}
}
void MakeEmpty(Stack S)
{
	S->TopOfStack = EmptyTOS;		
}
ElementType Top(Stack S)
{
	if(!IsEmpty(S))
		return S->Array[S->TopOfStack];
	Error("Empty Stack");
	return 0;
}
void Push(ElementType X, Stack S)
{
	if(IsFull(S))
		Error("Full stack");
	else
		S->Array[++S->TopOfStack] = X;
}

void Pop(Stack S)
{
	if(IsEmpty(S))
		Error("Empty Stack");
	else
		S->TopOfStack --;
}

ElementType TopAndPop(Stack S)
{
	if(!IsEmpty(S))
		return S->Array[S->TopOfStack --];
	Error("Empty stack");
	return 0;
}