栈

栈也是线性结构的一种特例。与队列不同，他只有一个口，只能从这里读或者写数据，这个口称为栈顶（top）。栈是一种先进后出的数据结构。先进来的元素会放入栈底，而后进来的元素被放在它的上面，最后进来的元素的上面的位置，称为栈顶。
栈所提供的操作比一般的线性表要少很多，只提供：初始化、销毁、判断是否为空、求栈的长度、清空栈、将数据压入栈、将数据弹出栈、或得栈顶元素这几种操作。其中将数据压入栈、将数据弹出栈、获得栈顶元素是最重要的。有人可能觉得，将栈顶元素弹出与获得栈顶元素是不是有点重复，其实它们主要的目的在于，很多时候你只想知道当前栈顶的元素是谁，而并不想将它弹出。这样做可以简单一点。
了解了栈的基本结构和操作以后，自然而然的想到用数组来实现栈：因为前面的元素并不发生变化，只能在最后面入栈或者出栈。让我们看看程序：

typedef int ElemType;

typedef struct Stack
{
	ElemType *data;
	//栈顶指针
	ElemType *top;
	//栈的容量
	int stackSize;
	
}Stack;

//初始化一个空栈
bool initStack(Stack *s,int size)
{
	s->data = (ElemType*)malloc(sizeof(Stack)*size);
	if(s->data == NULL)
		return false;
	s->stackSize = size;
	s->top = s->data;
	return true;
}

//销毁栈
void destroyStack(Stack *s)
{
	free(s->data);
	s->data = NULL;
	s->stackSize = 0;
	s->top = NULL;
}

//清空栈
void clearStack(Stack *s)
{
	s->top = s->data;
}

//判断栈是否为空
bool is_empty(Stack *s)
{
	if(s->top == s->data)
	{
		printf("the stack is empty!\n");
		return true;
	}
	else
		return false;
}

//返回栈的长度
int stackLength(Stack *s)
{
	return s->top-s->data;
}

//入栈
bool push(Stack *s,ElemType e)
{
	//如果栈已经满了，重新非配内存
	if(stackLength(s)== s->stackSize)
	{
		s->data = (ElemType *)realloc(s->data,sizeof(Stack)*s->stackSize*2);
		if(NULL == s->data )
			return false;
		s->stackSize *= 2;
	}
	//先将top的位置放入e，再将top位置加1
	*(s->top)++ = e;
	return true;
}

//出栈
bool pop(Stack *s,ElemType *e)
{
	if(is_empty(s))
		return false;
	else
	{
		//将top位置减1，然后返回这个位置的值
		*e = *(--s->top);
		return true;
	}
}

//返回栈顶元素
bool gerHead(Stack *s,ElemType *e)
{
	//如果栈为空，返回错误
	if(is_empty(s))
		return false;
	else
	{
		//top的下一个位置就是栈顶元素
		*e = *(s->top-1);
		return true;
	}

}

感觉简单了不少啊！

栈在在平时很有很多重要的应用，比如当函数调用时，就会用到栈，将当前的数据保存起来，等调用结束以后再弹出。下面举一个简单的例子：10进制到2进制的转化。

int main()
{

	int a = 0;
	int b ,c;
	Stack myStack;
	initStack(&myStack,50);
	printf("please enter a number: ");
	scanf("%d",&a);
	printf("%d in binary system is : ",a);
	do{
		c = a%2;
		a = a/2;		
		push(&myStack,c);
		
	}while(a != 0);
	
	while(!is_empty(&myStack))
	{
		pop(&myStack,&b);
		printf("%d",b);
	}
	destroyStack(&myStack);
	return 0;
}

其实就是把每次除以2的余数先压入栈，然后在弹出，就行了。

我们再三强调，队列和栈都是特殊的线性结构。所以在C++中的STL库中，并没有定义这种类型的容器，而是用“容器适配器”的方法实现了它们。