The array-based stack implementation introduced in class uses a fixed length array. As a result, it is possible for the stack to become full.

1. Rewrite the \(\texttt{push}\) method so that it doubles the length of the array when the array is full.
2. Rewrite the \(\texttt{pop}\) method so that it halves the length of the array when the array is less than half full.

typedef char element;
typedef struct dynStack {
	element *data; 
	int top;
	int capacity;
} *stack;

stack CreateStack()
{
	stack p = (stack) malloc(sizeof(stack));
	if(!p) return NULL;
	p->capacity=1;
	p->top = -1;
	p->data = (element*) malloc(p->capacity * sizeof(element));
	if(!p->data) return NULL;
	return p;
}

void DoubleStack(stack *p)
{
	(*p)->capacity*=2;
	(*p)->data=(element*) realloc((*p)->data,(*p)->capacity);
}

int Push(stack *p, element e)
{
	if (isFullStack(*p)) DoubleStack(p);
	(*p)->data[++(*p)->top] = e;
	return 1;
}

int Pop(stack *p)
{
	if (isEmptyStack(*p)) return 0;
	if ((*p)->top <= (*p)->capacity / 2)
	{
		(*p)->capacity/=2;
		(*p)->data=(element*) realloc((*p)->data,(*p)->capacity);
	}
	(*p)->top--;
	return 1;
}

int Top(stack p, element *e)
{
	if (isEmptyStack(p)) return 0;
	*e = p->data[p->top];
	return 1;
}

int isEmptyStack(stack p)
{
	return (p->top == -1);
}

int isFullStack(stack p)
{
	return (p->top == p->capacity-1);
}