C语言：栈（Stack）的实现

栈呢，废话不多说，上图！

如上图，A B C D 争先恐后地从栈顶进入，A 跑的最快，所以他先到达栈底。B 紧随其后，接着是C ，然后是 D 。而这时候，A 被其他三个人压着喘不过气来了，他想出去，可是大家想想，他出的去吗？嘿嘿嘿，当然出不去呀，所以他只能等 B 走了......而 B 想出去，也得先等 C 走，C 想出去得等 D 走，而 D 么......想什么时候走就什么时候走！他就是那个最自由的男人！A B C 这时候肯定后悔了：早知道我在下一个人进来之前就出去了！

栈又名堆栈，总的来说，是一种仅在表尾进行插入和删除操作的线性表。我们学习过链表和顺序表，他们俩都是线性表，又可以对表尾进行增加和删除，那么，栈就可以用链表或者顺序表的方式来表示！

栈的“先进后出”原则

使用栈存储数据元素，对数据元素的“存”和“取”有严格的规定：数据按一定的顺序存储到栈中，当需要调取栈中某数据元素时，需要将在该数据元素之后进栈的数据元素先出栈，该数据元素才能从栈中提取出来。
如上图 ，栈中存放了 4 个数据元素，进栈的顺序是 A 先进栈，然后 B 进，然后 C 进，最后 D 进栈；当需要调取 A 时，首先 D 出栈，然后 C 出栈，然后 B 出栈，最后 A 才能出栈被调用。

别急着写代码！我们先来看两道题充实一下对栈入栈出栈机制的了解：

 如果大家的答案分别是 B 和 C ，恭喜你们，可以继续往下看啦，这里就不多解释了。

栈操作数据元素的方法

栈操作数据元素只有两种动作：

1. 数据元素用栈的数据结构存储起来，称为“入栈”，也叫“压栈”。
2. 数据元素由于某种原因需要从栈结构中提取出来，称为“出栈”，也叫“弹栈”。

栈的两种表示方式

既然栈也是线性表，那么它就同样有线性表的两种表示形式：顺序栈 和 链式栈。

到底是用顺序表表示栈呢，还是用链表表示栈呢？每个结构都有每个结构的优点。顺序表在扩容的时候需要扩容原先容量的2倍，比较耗费空间，可是他可以轻轻松松地对末尾元素进行操作。链式栈每次入栈只开阔一个空间，比较节省空间，但是操作最后一个节点需要从头遍历到最后一个节点（双向循环链表除外）。

下面，我们就用顺序表来表示栈：

//创建栈
typedef struct Stack{
	int * a;
	int capacity;
	int top;
}ST;

//栈的初始化
void stackInit(ST * ps){
	ps->a=NULL;
	ps->capacity=0;
	ps->top=0; 
}

//入栈
void stackPush(ST * ps,int num){
	//判断栈是否存满，若存满，则扩展栈
	if(ps->top==ps->capacity){
		int newCapacity=ps->capacity==0?4:ps->capacity*2;
		int * temp=(int *)realloc(ps->a,sizeof(int)*newCapacity);
		if(temp==NULL){
			printf("栈扩容失败！");
			exit(-1);
		}
		ps->a=temp;
		ps ->capacity=newCapacity;
	}
	//添加栈节点
	ps->a[ps->top]=num;
	ps->top++;
}

//出栈
void stackPop(ST * ps){
	if(ps->top==0){
		printf("空栈！出栈失败！");
		return;
	}
	ps->top--;
}

//栈的遍历
void stackPrint(ST * ps){
	while(ps->top!=0){
		printf("%d\t",ps->a[ps->top-1]);
		ps->top--;
	}
	printf("\n");
}

//栈的清空
void stackDestroy(ST * ps){
	free(ps->a);
	ps->a=NULL;
	ps->capacity=ps->top=0;
}

//返回栈顶
int stackTop(ST *ps){
	if(ps->top==0){
		printf("空栈！");
		return -1;
	}
	return ps->a[ps->top-1];
}

//返回栈的容量
int stackSize(ST * ps){
	return ps->top;
}

//判断栈是否为空
void stackEmpty(ST * ps){
	if(ps->top==0){
		printf("栈为空\n");
	}else{
		printf("栈不为空\n");
	}
}

测试代码：

int main()
{
	ST st;
	stackInit(&st);
	stackPush(&st,1);
	stackPush(&st,2);
	stackPush(&st,3);
	stackPush(&st,4);
	stackPush(&st,5);
	stackPrint(&st);
	stackDestroy(&st);
	stackEmpty(&st);
	system("pause");
}

只要大家学习过顺序表，并对栈的机制有着基本的了解，创建出一个顺序栈根本不是问题！

此文章到此结束，如有错误或者不足，欢迎大家指点~