学步园

顺序堆栈的存储结构类型描述如下：

#define M 1000     /* 定义堆栈的最大容量 */
SElemType STACK[ M ];
int top;           /* 栈顶指针变量 */

下面是基本算法描述，很简单：

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

#define M 1000     /* 定义堆栈的最大容量 */

/* 初始化一个堆栈 */
void initials( int *top ){
	*top = -1;
}

/* 测试堆栈是否为空, 当堆栈为空时，算法返回1，否则返回0 */
int isEmpty( int top ){
	return top == -1;
}

/* 测试堆栈是否已满, 当堆栈已满时，算法返回1，否则返回0 */
int isFull( int top ){
	return top == M -1;
}

/* 取当前栈顶元素，将当前栈顶元素取出送变量item，需测试堆栈是否为空 */
int getTop( int *st, int top, int *item ){
	if( isEmpty( top ) )  /* 堆栈为空，操作失败，返回0 */
		return 0;
	else{
		*item = st[ top ];   /* 保存栈顶元素 */
		return 1;            /* 堆栈非空，操作成功，返回1 */
	}
}

/* 进栈,需测试堆栈是否已满 */
int push( int *st, int *top, int item ){
	if( isFull( *top ) )     /* 堆栈已满，插入失败，返回0 */
		return 0;
	else{
		st[ ++( *top ) ] = item;
		return 1;           /* 插入成功，返回1 */
	}	
}

/* 退栈，需测试堆栈是否为空 */
int pop( int *st, int *top, int *item ){
	if( isEmpty( *top ) )
		return 0;             /* 堆栈为空，删除失败，返回0 */
	else{
		*item = st[ ( *top )-- ];
		return 1;           /* 删除成功，返回1 */
	}
}

下面是测试上述算法是否正确的代码：

/* 打印堆栈 */
void printStack( int *st, int top ){
	while( top != -1 ){
		printf( "%d\n", st[ top ] );
		top--;
	}
}

int main(){
	int stack[ M ];
	int top;
	initials( &top );
	push( stack, &top, 5 );
	push( stack, &top, 8 );
	push( stack, &top, 9 );
	push( stack, &top, 2 );
	printStack( stack, top );

	printf( "the stack is full %d\n", isFull( top ) );	
	
	int item;
	pop( stack, &top, &item );
	printf( "the pop elem is %d\n", item );

	getTop( stack, top, &item );
	printf( "the top elem is %d\n", item );

	pop( stack, &top, &item );
	pop( stack, &top, &item );
	pop( stack, &top, &item );
	
	printf( "the stack is empty: %d\n", isEmpty( top ) );

	return 0;
}