REN

Stack is a data structure which allows data in it come or go with a FILO (First In Last Out) sequence. Stack could either be implemented with arrays or linked lists. In this article, I'll use array to describe stack in C Language.

typedef struct Stack {
	elementType *base;
	int size;
	int top;
} Stack;

Compared with being implemented in linked list, the stack implemented in array has a stack size and we set a stack "top pointer" top always indicates the top of the stack. When the stack is empty, the top equals -1, and when top equals to the size of stack minus 1, the stack is full. The data structure of stack is quite simple. Note that the type of base field could be any other types, even a struct.

Initialize

To initialize the stack, we need to set the size of the stack, applying for the dynamic memory space for it. In addition, don't forget to set "stack pointer" to -1.

int initialStack(Stack *s, int size){
	if (NULL == s)
		return -1;
	s->base = (elementType*)malloc(size*sizeof(elementType))	
	if (NULL == s->base)
		return -1;
	s->size = size;
	s->top = -1;
	return 0;
}

Push

Push an element into the stack. Before pushing, we need to check whether the stack is full or not. when top equals to the size of stack minus 1, the stack is full.

int push(Stack *s, elementType element){
	if (NULL == s)
		return -1;
	if (s->size - 1 == s->top)
		return -1;	// full
	s->base[++s->top] = element;
	return 0;
}

Pop

Pop an element from the stack. Before poping, we need to check whether the stack is empty or not. when top equals to -1, the stack is empty.

int pop(Stack *s, elementType *element){
	if (NULL == s)
		return -1;
	if (s->top < 0)
		return -1;	// empty
	*element = s->base[s->top--];
	return 0;
}

Top

Get the top element of the stack. Before get the top, we need to check whether the stack is empty or not. when top equals to -1, the stack is empty.

int pop(Stack s, elementType *element){
	if (s.top < 0)
		return -1;	// empty
	*element = s.base[s.top];
	return 0;
}

Destroy

Free the dynamic memory for the stack.

void destroyStack(Stack s){
	if (NULL == s.base)
		return;
	free(s.base);
}