数据结构与算法——顺序栈的实现

数据结构栈——一列数据，表尾入栈，表尾出栈，类似于子弹弹匣，压入子弹和拿出子弹都是从最上方进出。

结构体

struct Stack{
	int *arr;
	int capacity;     //数组容量
	int top;          //存储栈顶元素的下标 
};

初始化栈

int InitStack(struct Stack *stack){
	stack->arr=malloc(sizeof(struct Stack)*8);           //给数组分配空间
	if(stack->arr==NULL) return 0;                       //判断是否分配成功
	stack->capacity=8;                                   //将数组容量改为分配好的空间大小
	stack->top=-1;                                       
	return 1;
}

初始化栈做的事情和顺序表一样，分配数组空间，并且将结构体中其它的元素设置为合适的值，方便后续对栈进行操作。注意，此时栈中元素数量为0，而栈的第一个元素的数组下标是0，所以现在栈空时的stack->top=-1。

入栈操作

int PushStack(struct Stack *stack,int element){
	stack->top++;
	if((stack->top+1)==stack->capacity){
		int newcapacity=stack->capacity*2;
		int *newarr=realloc(stack->arr,newcapacity*sizeof(struct Stack));
		if (newarr==NULL) return -1;
		stack->arr=newarr;
		stack->capacity=newcapacity;	
	}
	stack->arr[stack->top]=element;
	return 1;
}

将stack->top加1，并将新入栈的元素存于下标为stack->top的位置。注意和顺序表一样的是，入栈时需要判断是否栈满，如果栈满则需要扩容，扩容操作和顺序表相同。

判断栈是否为空

int IsEmpty(struct Stack *stack){
	if(stack->top==-1){
		return 0;
	}else{
		return 1;
	}
}

如果栈空，stack->top的值为-1，用这个来判断栈是否为空。如果为空，返回1，如果不为空，则返回0。

出栈操作

int PopStack(struct Stack *stack){
	int temp;
	if(IsEmpty(stack)){
		temp=stack->arr[stack->top];
		stack->top--;
		return temp;
	}
	return 0;
}

出栈操作首先需要判断栈是否为空，如果为空则没有元素可以出栈，返回错误信息0。如果不为空，则将栈顶元素的值给一个临时变量，将stack->top的值减1，最后返回临时变量得到出栈元素。

打印输出

void PrintStack(struct Stack *stack){
	int i=0;
	for(i=0;i<=stack->top;i++){
		printf("%d ",stack->arr[i]);
	}
	printf("\n");
}

通过循环遍历栈，将每一个元素打印输出。和顺序表相比，栈的打印输出需要注意，出栈操作是从数组尾部取出元素，而打印输出是通过从头开始循环遍历打印。如果我们需要多次循环出栈操作，打印出栈元素的顺序是和这里的打印输出的顺序不同的。

完整代码

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

struct Stack{
	int *arr;
	int capacity;
	int top;          //存储栈顶元素的下标 
};

int InitStack(struct Stack *stack){
	stack->arr=malloc(sizeof(int)*8);
	if(stack->arr==NULL) return 0;
	stack->capacity=8;
	stack->top=-1;
	return 1;
}

int PushStack(struct Stack *stack,int element){
	stack->top++;
	if((stack->top+1)==stack->capacity){
		int newcapacity=stack->capacity*2;
		int *newarr=realloc(stack->arr,newcapacity*sizeof(int));
		if (newarr==NULL) return -1;
		stack->arr=newarr;
		stack->capacity=newcapacity;	
	}
	stack->arr[stack->top]=element;
	return 1;
}

int IsEmpty(struct Stack *stack){
	if(stack->top==-1){
		return 0;
	}else{
		return 1;
	}
}

int PopStack(struct Stack *stack){
	int temp;
	if(IsEmpty(stack)){
		temp=stack->arr[stack->top];
		stack->top--;
		return temp;
	}
	return 0;
}

void PrintStack(struct Stack *stack){
	int i=0;
	for(i=0;i<=stack->top;i++){
		printf("%d ",stack->arr[i]);
	}
	printf("\n");
}

int main(){
	...
	return 0;
}