#ifndef _CONST_H_
#define _CONST_H_

#include <stdio.h>
#include <stdlib.h>

typedef enum
{
False = 0,
True,
}Bool;

typedef int ElemType;

#define QUEUE_MAX_SIZE 10

#define STACK_INIT_SIZE 10
#define STACK_INCREMENT_SIZE 2

#define Null ((void *)0)

typedef enum
{
NORMAL = 0,
ERROR,
UNDERFLOW,
OVERFLOW,
STATUSCOUNT,
}Status;

#endif

#ifndef _DYNAMIC_STACK_H_
#define _DYNAMIC_STACK_H_

#include "Const.h"

typedef struct stacknode
{
ElemType data;
struct stacknode *pNext;
}StackNode, *pStackNode;

typedef struct dynamicstack
{
pStackNode ptop;
pStackNode pbase;
}DynamicStack, *pDynamicStack;

Status InitDynamicStack(pDynamicStack pDS);

Bool IsDynamicStackEmpty(pDynamicStack pDS);

Bool PushDynamicStack(pDynamicStack pDS, ElemType elem);

Bool PopDynamicStack(pDynamicStack pDS, ElemType *e);

void DestoryDynamicStack(pDynamicStack pDS);

void ClearDynamicStack(pDynamicStack pDS);

Status GetDynamicStackHead(pDynamicStack pDS, ElemType *e);

int GetDynamicStackLength(pDynamicStack pDS);

#endif

#include "DynamicStack.h"
#include "Const.h"

Status InitDynamicStack(pDynamicStack pDS)
{
pStackNode pN = (pStackNode)malloc(sizeof(StackNode));
if (pN == Null)
{
printf("No accessable free memory.\n");
return ERROR;
}
pN->pNext = Null;
pDS->ptop = pN;
pDS->pbase = pN;
return NORMAL;
}

Bool IsDynamicStackEmpty(pDynamicStack pDS)
{
if (pDS->ptop == pDS->pbase)
{
return True;
}
else
{
return False;
}
}

Bool PushDynamicStack(pDynamicStack pDS, ElemType elem)
{
pStackNode pTempStackNode = (pStackNode)malloc(sizeof(StackNode));
if (pTempStackNode == Null)
{
printf("No accessable free memory.\n");
return False;
}

pTempStackNode->data = elem;
pTempStackNode->pNext = pDS->ptop;
pDS->ptop = pTempStackNode;
return True;
}

Bool PopDynamicStack(pDynamicStack pDS, ElemType *e)
{
if (IsDynamicStackEmpty(pDS))
{
printf("The Queue Is Empty.\n");
return False;
}
else
{
*e = pDS->ptop->data;
pStackNode pTempStackNode = pDS->ptop;
pDS->ptop = pDS->ptop->pNext;
free(pTempStackNode);
return True;
}
}

void DestoryDynamicStack(pDynamicStack pDS)
{
pStackNode p = pDS->ptop;
pStackNode q = Null;
while(p != Null)
{
q = p;
p = p->pNext;
free(q);
}
pDS->ptop = Null;
pDS->pbase = Null;
}

void ClearDynamicStack(pDynamicStack pDS)
{
pStackNode p = pDS->ptop;
pStackNode q = Null;
while(p != pDS->pbase)
{
q = p;
p = p->pNext;
free(q);
}
pDS->pbase->pNext = Null;
pDS->ptop = pDS->pbase;
}

Status GetDynamicStackHead(pDynamicStack pDS, ElemType *e)
{
if (IsDynamicStackEmpty(pDS))
{
printf("The linked queue is empty.\n");
return ERROR;
}
*e = pDS->ptop->data;
return NORMAL;
}

int GetDynamicStackLength(pDynamicStack pDS)
{
if (IsDynamicStackEmpty(pDS))
{
return 0;
}
int Count = 0;
pStackNode pTemp = pDS->ptop;

while(pTemp->pNext != Null)
{
Count++;
pTemp = pTemp->pNext;
}
return Count;
}