栈、队列的实现与应用 1.分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作

栈、队列的实现与应用 1.分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作

链表实现的栈：
//--------* Header File------------------------------------------------------------------------

#ifndef __STACK_H__
#define __STACK_H__

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

#endif

//----------------------------------------------------------------------------------------------

//--------* Implementation File--------------------------------------------------------------
//节点结构
struct Node
{
ElementType Element;
PtrToNode Next;
};

//----------------------------------------------------------------------------------------------
//测试堆栈是否为空
int IsEmpty(Stack S)
{
return S->Next == NULL;
}

//----------------------------------------------------------------------------------------------
//创建一个空栈
Stack CreateStack(void)
{
Stack S;

S = (Node *) malloc ( sizeof(struct Node) ); //分配一个节点的空间给栈S
if(S==NULL) exit(1); //分配失败

S->Next = NULL;
MakeEmpty(S);

return S;
}

//----------------------------------------------------------------------------------------------
//将栈清空
void MakeEmpty(Stack S)
{
if(S == NULL) exit(1);
else{
while(!IsEmpty(S))
Pop(S);
}
}

//----------------------------------------------------------------------------------------------
//进栈Push
void Push(ElementType X, Stack S)
{
PtrToNode TmpCell;

TmpCell = malloc(sizeof(struct Node));
if(TmpCell == NULL) exit(1);
else
{
TmpCell->Element = X;
TmpCell->Next = S->next;
S->next = TmpCell;
}
}

//----------------------------------------------------------------------------------------------
//返回栈顶元素
ElementType Top(Stack S)
{
if(!IsEmpty(S))
return S->Next->Element;
printf("Empty Stack");
return 0;
}

//----------------------------------------------------------------------------------------------
//出栈Pop
void Pop(Stack S)
{
PtrToNode FirstCell;

if(IsEmpty(S))
printf("Empty Stack");
else
{
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}
}

数组实现的栈：
//--------* Header File------------------------------------------------------------------------

#ifndef __STACK_H__
#define __STACK_H__

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);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);

#endif

//----------------------------------------------------------------------------------------------

//--------* Implementation File--------------------------------------------------------------
//栈信息结构
#define EmptyTOS (-1)
#define MinStackSize (5)

struct StackRecord
{
int Capacity; //栈容量
int TopOfStack; //栈顶
ElementType *Array; //用来做栈容器的数组
};

//----------------------------------------------------------------------------------------------
//创建一个空栈
Stack CreateStack(int MaxElements)
{
Stack S;

if( MaxElements < MinStackSize )
printf("Stack size is too small");

S = (StackRecord*)malloc(sizeof(struct StackRecord)); //分配空间记录栈信息
if(S==NULL) exit(1); //分配失败

S->Array = (ElementType*)malloc(MaxElements * sizeof(ElementType)); //分配栈空间
if(S->Array==NULL) exit(1); //分配失败
S->Capacity = MaxElements; //设定栈容量
MakeEmpty(S); //将栈清空

return S; //返回栈结构基址
}

//----------------------------------------------------------------------------------------------
//释放栈
void DisposeStack(Stack S)
{
if( S!=NULL )
{
free( S->Array );
free( S );
}
}

//----------------------------------------------------------------------------------------------
//测试堆栈是否为空
int IsEmpty(Stack S)
{
return S->TopOfStack == EmptyTOS;
}

//----------------------------------------------------------------------------------------------
//测试堆栈是否为满
int IsFull(Stack S)
{
return S->TopOfStack == MaxElements-1;
}

//----------------------------------------------------------------------------------------------
//将栈清空
void MakeEmpty(Stack S)
{
S->TopOfStack == EmptyTOS;
}

//----------------------------------------------------------------------------------------------
//进栈Push
void Push(ElementType X, Stack S)
{
if( IsFull(S) )
printf("Full stack");
else
S->Array[++S->TopOfStack] = X;
}

//----------------------------------------------------------------------------------------------
//返回栈顶元素
ElementType Top(Stack S)
{
if(!IsEmpty(S))
return S->Array[S->TopOfStack];
printf("Empty Stack");
return 0;
}

//----------------------------------------------------------------------------------------------
//出栈Pop
void Pop(Stack S)
{
if(IsEmpty(S))
printf("Empty Stack");
else
S->TopOfStack--;
}

//----------------------------------------------------------------------------------------------
//返回栈顶元素并从栈弹出
ElementType TopAndPop(Stack S)
{
if(!IsEmpty(S))
return S->Array[S->TopOfStack--];
printf("Empty Stack");
return 0;
}