數據結構－棧(C描述)

1.鏈式棧

stackli.h

typedef int ElementType;
#ifndef STACKLI_H_INCLUDED
#define STACKLI_H_INCLUDED
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
int IsEmpty(Stack S);
Stack CreateStack();
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
#endif // STACKLI_H_INCLUDED

fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str)　　　　　　　　FatalError(Str)
#define FatalError(Str)　　 fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED

stackli.c
#include "stackli.h"
#include "fatal.h"
struct Node
{
　　　　ElementType Element;
　　　　PtrToNode　　 Next;
};
int IsEmpty(Stack S)
{
　　　　return S->Next == NULL;
}
Stack CreateStack()
{
　　　　Stack S;
　　　　S = malloc(sizeof(struct Node));
　　　　if(S == NULL)
　　　　　　　　FatalError("Out of space!!!");
　　　　S->Next = NULL;
　　　　return S;
}
void MakeEmpty(Stack S)
{
　　　　if(S == NULL)
　　　　　　　　Error("Must use CreateStack first");
　　　　else
　　　　　　　　while(!IsEmpty(S))
　　　　　　　　　　　　Pop(S);
}
void DisposeStack(Stack S)
{
　　　　MakeEmpty(S);
　　　　free(S);
}
void Push(ElementType X, Stack S)
{
　　　　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))
　　　　　　　　return S->Next->Element;
　　　　Error("Empty stack");
　　　　return 0;　　/* Return value used to avoid warning */
}
void Pop(Stack S)
{
　　　　PtrToNode FirstCell;
　　　　if(IsEmpty(S))
　　　　　　　　Error("Empty stack");
　　　　else
　　　　{
　　　　　　　　FirstCell = S->Next;
　　　　　　　　S->Next = S->Next->Next;
　　　　　　　　free(FirstCell);
　　　　}
}

2.數組棧

stackar.h
typedef int ElementType;
#ifndef STACKAR_H_INCLUDED
#define STACKAR_H_INCLUDED
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 // STACKAR_H_INCLUDED

stackar.c
#include "stackar.h"
#include "fatal.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 - 1;
}
Stack CreateStack(int MaxElements)
{
　　　　Stack S;
　　　　if(MaxElements < MinStackSize)
　　　　　　　　Error("Stack size is too small");
　　　　S = malloc(sizeof(struct StackRecord));
　　　　if(S == NULL)
　　　　　　　　FatalError("Out of space!!!");
　　　　S->Array = malloc(sizeof(ElementType) * MaxElements);
　　　　if(S->Array == NULL)
　　　　　　　　FatalError("Out of space!!!");
　　　　S->Capacity = MaxElements;
　　　　MakeEmpty(S);
　　　　return S;
}
void MakeEmpty(Stack S)
{
　　　　S->TopOfStack = EmptyTOS;
}
void DisposeStack(Stack S)
{
　　　　if(S != NULL)
　　　　{
　　　　　　　　free(S->Array);
　　　　　　　　free(S);
　　　　}
}
void Push(ElementType X, Stack S)
{
　　　　if(IsFull(S))
　　　　　　　　Error("Full stack");
　　　　else
　　　　　　　　S->Array[++S->TopOfStack] = X;
}
ElementType Top(Stack S)
{
　　　　if(!IsEmpty(S))
　　　　　　　　return S->Array[S->TopOfStack];
　　　　Error("Empty stack");
　　　　return 0;　　/* Return value used to avoid warning */
}
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;　　/* Return value used to avoid warning */
}