学一样东西首先要要明白学它有什么用。那么问题来了：栈使用来干么的？

先说点无聊但是很必要的东西：

简单来说：栈是一种数据结构，在计算机术语中是十分重要的。因为栈在 计算机中的应用很多。其中最重要的是应用于函数的调用，也经常用作临时性数据的存储等等。栈又名堆栈，实质上是一种线性表。只不过栈作为一种线性表是很特殊的存在。因为它的运算受到了限制：只能在表头进行插入或者删除的操作。

如果你是初学者只需要记住：

实质：运算受限的线性表（线性表，你懂的），只能在表头执行插入或者删除等操作。

特点：后进先出（因为每次进入的数据都在栈顶，所以出去的时候肯定是先出去）。

就够了。

既然说栈是一种线性表，那么它的简单实现就有两种：顺序存储（即数组）；链式存储（即链表）

由于链表相对于数组来说难那么一丢丢，所以以下讲解使用链表来完成，当然我也会贴出顺序存储的实现。

故事：

从前有个人小领。

没错就是小领，他本来是一位未来的IT大神，但是由于他经常学C++，所以眼睛瞎掉了。为了能娶到如花，他到 一家饭店去洗盘子挣钱。现在在他的面前有一对摞在一起的盘子，老板告诉他这堆盘子有100个。洗完之后可以得到1毛钱。

把盘子看做一个数据 节点：

（要注意的是链栈是采用头插法建的）

typedef struct LinkNode
{
	int data;
	struct LinkNode *next;
}LiStack;

那么小领要这摞在一起的盘子洗完的话，首先要找到一个地方放洗好的盘子：

初始化栈：建立一个空栈：

void InitStack(LiStack *&s)
{
	s = (LiStack *)malloc(sizeof(LiStack));  //为数据节点申请空间
	s->next = NULL;
}

那么洗盘子的时候他首先要从摞在一起的盘子顶部取一个盘子（洗盘子过程是两个栈，一个是盘子本身的占据的，一个是我们新建的）

即出栈：

bool Pop(LiStack *&s)
{
	LiStack *p;
	if (s->next == NULL)    //如果洗完了，就没得洗了。
		return false;
		p = s->next;     // 如果没洗完 ，我们让下一个盘子位于栈顶（相当于把这个盘子隔过去）
		s->next = p->next;
		free(p);            //释放被取的盘子所占的空间
		return true;
}

取到了这个盘子，小领放在水里泡了一下，就认为洗干净了（他很傻），洗完之后他将这个盘子放在我们空好的位置的最顶上：

进栈：

void Push(LiStack *s, int e)
{
	LiStack *p;
	p = (LiStack*)malloc(sizeof(LiStack));   //申请一个空间
	p->data = e;
	p->next = s->next;                       //让新加入的盘子位于顶部
	s->next = p;
}

由于小领的数学不好，只能查到10，他现在想知道盘子洗完没有，所以他用手去摸了摸还有没有盘子剩余：

判断栈是否为空：

bool IsEmpty(LiStack *s)
{
	return (s->next== NULL);
}

小领终于把盘子洗完了，兴高采烈的跳起来了桑巴舞。但是由于动作过于夸张，把盘子全都打碎了。他想到了如果被发现盘子被打碎了还要赔一毛钱，所以小领把盘子全部都从窗户扔到了外边，然后逃走了。

销毁栈：

void Destory(LiStack *&s)
{
	LiStack *p = s, *q = s->next;
	while (q != NULL)
	{
		free(p);
		p = q;
		q = p->next;
	}
	free(p);          //最后一个数据节点为p，所以我们需要销毁p
}

最终，小领通过卖Upan成功 娶到了如花。

（是不是觉得栈的操作好少，是 的，栈的操作很少，以至于好好学的人很少）

以下贴出来顺序储存的代码实现：

#define MAX 1001
typedef struct Stack
{
	int data[MAX];              //栈存储的数据
	int top;
}SqStack;

void InitStack(SqStack *&s)        //初始化栈
{
	s = (SqStack *)malloc(sizeof(SqStack));// 申请空间，并让top为-1，（意思是空栈，栈存储是从0 开始）
	s->top = -1;
}

bool Push(SqStack *&s, int e)    //进栈
{
	if (s->top == MAX - 1)        //如果栈已经满了，则不进栈
		return  false;
	s->top++;
	s->data[s->top] = e;
	return true;

}

bool Pop(SqStack *&s)
{
	if (s->top == -1)                   //如果当前栈里面没有数据，就不出栈
		return false;
	s->top--;                           //有数据就出栈，top--
	return true;
}

bool StackEmpty(SqStack *s)             //是否为空（通过top的值判断）
{
	return (s->top == -1);
}

bool GetTop(SqStack *s, int &e)           //取栈顶元素
{
	if (s->top == -1)                 //如果栈为空，则不取
		return false;
	e = s->data[s->top];
	return true;
}

void Destory(SqStack *&s)              //销毁栈。
{ 
	free(s);                        //释放空间
}

栈的应用：

1.括号的匹配（链栈实现）

括号 的匹配很容易理解，意思就是给定一个字符串里面包含了许多的括号，我们要做的就是判断括号的使用是否合法。例如：[][[]]]]、())()[][]是不合法的，而[][][]等是合法的。理解题意就ok了，那么你可能会问，对于不是括号的字符怎么处理，答案：不做处理，只看括号。

（一定要注意判断括号的匹配采用的是头插法建表）

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct Stack       //数据节点             
{
	char data;                //数据信息
	struct Stack *next;
}LiStack;

bool Push(LiStack *&s, char e)          //入栈
{
	LiStack *p;
	p = (LiStack *)malloc(sizeof(LiStack));  //注意数据是放在顶端（即头插的头部）
	p->data = e;
	p->next = s->next;
	s->next = p;

	return true;
}

bool Pop(LiStack *&s)                //出栈
{
	LiStack *p;
	if (s->next != NULL)           //如果栈不为空，就出栈
	{
		p = s->next;
		s->next = p->next;
		free(p);

		return true;
	}
	return false;
}

bool IsEmpty(LiStack* &s)   //栈是否为空
{
	return s->next == NULL;
}

bool GetTop(LiStack *s, char e, int num)       //判断括号是否匹配，要注意的是"("  与 “)” 在ASCII表中相差1，而“[” 与“]”相差的是2.
{
	if (s->next == NULL)
	{
		return false;
	}
	else
	{
		if (e == s->next->data + num)         //如果匹配返回真。
			return true;
		else
			return false;
	}
}

int main()
{
	LiStack *L;
	L = (LiStack *)malloc(sizeof(LiStack));
	L->next = NULL;

	char str[100];
	scanf("%s", str);

	int i;
	int len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if ((str[i] == '(') || (str[i] == '['))           //如果是括号的左部分，则将其入栈。
		{
			Push(L, str[i]);
			continue;
		}
		else if (str[i] == ']')                           //如果是“]”
		{
			if (IsEmpty(L) == true)                   //则判断当前栈是否为空，如果为空，则这个字符串中的括号使用是不合法的。
			{
				printf("NO");
				return 0;
			}
			else
			{
				if (GetTop(L, str[i], 2) == true)   //如果栈不为空，则判断“]”与栈顶元素是否匹配，如果匹配，则出栈。
				{
					Pop(L);
				}
			}
		}
		else if (str[i] == ')')                           //如果是“）”
		{
			if (IsEmpty(L) == true)                   //则判断当前栈是否为空，如果为空，则这个字符串中的括号使用是不合法的。
			{
				printf("NO");
				return 0;
			}
			else
			{
				if (GetTop(L, str[i], 1) == true)   //如果栈不为空，则判断“）”与栈顶元素是否匹配，如果匹配，则出栈。
				{
					Pop(L);
				}
			}
		}
	}
	if (IsEmpty(L) == true)               //最后只需要判断 栈是否为空就可以了，对于那些不是括号的字符，我们根本就没入栈，所以嘿嘿嘿。
	{
		printf("YES");
	}
	else
	{
		printf("NO");
	}
	return 0;
}

（可以 在Swust oj 962）提交通过。

括号的匹配不难，按照思路一点一点写出来就ok了。但是 要注意括号在ASCII码表中的位置关系。

2.中缀表达式转换成后缀表达式

数据结构书上讲的太过繁琐，又是什么左运算符，又运算符什么的，无聊。

我们在此用两个栈，s1，s2。s1为运算符的临时存储栈，s2为最终结果 的存储栈。

简单来说分以下情况：

从左 到右依次取数据 。

1.如果是数据，直接入s1栈顶。

2.如果是（，直接入s1栈顶。

3.如果是  ），则将距离s1栈顶 最近的“ ）”之间的元素，逐个出栈，并入栈s2.

4.如果是 运算符，则将该运算符与s1栈顶的元素比较，如果该元素 的优先级大，则直接入s1栈顶，否则将s1栈顶元素出栈，并把 出栈的元素入栈s2，直到s1栈顶元素的优先级高于该元素。

重复操作，直到数据取完，是不是很简单，

那么模拟一下：

中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+”

1. 初始化一空栈，用来对符号进出栈使用。

2. 第一个字符是数字9，输出9，后面是符号“+”，进栈。

3. 第三个字符是“(”,依然是符号，因其只是左括号，还未配对，故进栈。

4. 第四个字符是数字3，输出，总表达式为9 3,接着是“-”进栈。

5. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”，总的输出表达式为9 3 1 -

6. 接着是数字3，输出，总的表达式为9 3 1 - 3 。紧接着是符号“*”，因为此时的栈顶符号为“+”号，优先级低于“*”，因此不输出，进栈。

7. 之后是符号“+”，此时当前栈顶元素比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”，而下图中的栈底（也是栈顶）的“+”是指“9+(3-1)*3+”中的最后一个“+”。

8. 紧接着数字10，输出，总表达式变为9 3 1-3 * + 10。

9. 最后一个数字2,输出，总的表达式为 9 3 1-3*+ 10 2

10. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+

code：C语言实现

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define MAX 1001
typedef struct Stack
{
	char data[MAX];
	int top;
}SqStack;
int cmp(char ch)    //判断优先级（ * / 的优先级最高，次之 是+ -，最后是 （ ））
{
	switch (ch)
	{
	case'+':
	case'-':
		return 1;
	case'*':
	case'/':
		return 2;
	default:
		return 0;
	}
}

void InitStack(SqStack *&s)       //初始化栈
{
	s = (SqStack*)malloc(sizeof(SqStack));
	s->top = -1;
}

bool Push(SqStack *&s, char e)        //数据入栈
{
	if (s->top == MAX)
		return false;
	else
		s->data[++s->top] = e;
	return true;
}

bool Pop(SqStack *&s)                       //数据出栈                 
{
	if (s->top == -1)
		return false;
	else
		s->top--;
	return true;
}

bool IsEmpty(SqStack *s)                 //判断栈是否为空
{
	return s->top == -1;
}

int main()
{
	SqStack *s1, *s2;
	InitStack(s1), InitStack(s2);
	char str[1001], int i;
	scanf("%s", str);
	int len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] == '(')         //如果当前数据是“（”，直接入栈
			Push(s1, str[i]);
		else if (str[i] == ')')             //如果是“）”，则在s1中找到最近的“（”元素，将两者之间的数据出栈，并入栈到s2.
		{
			while (s1->data[s1->top] != '(')
			{
				Push(s2, s1->data[s1->top]);
				Pop(s1);
			}
			Pop(s1);
		}
		else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')  //如果是运算符
		{
			while (cmp(s1->data[s1->top]) >= cmp(str[i]))     //判断优先级，该运算符优先级较s1栈顶元素的优先级低的话
			{
				Push(s2, s1->data[s1->top]);  //将s1栈顶元素出栈并入栈到s2，直到该元素的运算符优先级较高。
				Pop(s1);
			}
			Push(s1, str[i]);             //然后将这个 元素入栈s1.
		}
		else
			Push(s2, str[i]); //如果是操作数据直接入站s2.
	}
	while (IsEmpty(s1) == false)// 将s1最终还存储其中 的数据转移到s2
	{ 
		Push(s2, s1->data[s1->top]); 
		Pop(s1); 
	}
	for (i = 0; i <= s2->top; i++)	//完成。
	
		printf("%c", s2->data[i]);
	return 0;
}

是不是很简单，有效代码很少，精髓在于运算符优先级判断的cmp函数。

可以通过Swust Oj 1042；(题数据弱。。。)

3.后缀表达式求值

后缀表达式的求值：

将中缀表达式转换成等价的后缀表达式后，求值时，只需从左到右扫描一遍后缀表达式即可，而不需要考虑到运算符优先级问题。具体求值步骤为：从左到右扫描后缀表 达式，遇到运算符就把表达式中该运算符前面两个操作数取出并运算，然后把结果带回后缀表达式；继续扫描直到后缀表达式最后一个表达式。 后缀表达式的求值的算法：

设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的 放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct Stack
{
	struct Stack *next;
	int  data;

}LiStack;

bool Push(LiStack *&s, int e)  //元素进栈
{
	LiStack *p;
	p = (LiStack *)malloc(sizeof(LiStack));
	p->data = e;
	p->next = s->next;
	s->next = p;
	return true;
}

bool Pop(LiStack *&s)               ///元素出栈
{
	if (s->next == NULL)
	{
		return false;
	}
	s->next = s->next->next;
	return true;
}
int main()
{
	int i = 0;
	char str[1001];
	while (1)                          //要注意输入的时候数据之间是有空格的
	{
		scanf("%c", &str[i]);
		if (str[i] == '\n')
			break;
		else
		{
			i++;
		}
	}
	LiStack *L;
	L = (LiStack *)malloc(sizeof(LiStack));
	L->next = NULL;
	int len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= '0' && str[i] <= '9')  //如果是操作数，直接进栈
		{

			int data = str[i] - 48;
			Push(L, data);
		}
		else if (str[i] == '+')                           //如果是加号，然后栈顶和栈顶的下个元素求和，对这两个数据出栈，将结果入栈
		{

			int data = L->next->next->data + L->next->data;
			Pop(L);
			Pop(L);
			Push(L, data);
		}
		else if (str[i] == '-')
		{
			int data = L->next->next->data - L->next->data;//如果是减号，栈顶下个元素 - 栈顶元素，这两个数据出栈，计算结果入栈
			Pop(L);
			Pop(L);
			Push(L, data);
		}
		else if (str[i] == '*')                       //如果是乘号，栈顶下个元素 * 栈顶元素，这两个数据出栈，结果入栈
		{
			int data = L->next->next->data * L->next->data;
			Pop(L);
			Pop(L);
			Push(L, data);
		}
		else if (str[i] == '/') //如果是除号，栈顶下个元素 / 栈顶元素，这两个数据出栈，结果入栈
		{
			int data = L->next->next->data / L->next->data;
			Pop(L);
			Pop(L);
			Push(L, data);
		}
	}
	printf("%d", L->next->data);             //最终栈中只剩余一个值就是最后的计算结果
	return 0;
}

是不是很简单，是的。

代码可通过Swust oj 1043

如果是刚接触数据结构，能将括号的匹配，中缀变后缀，后缀表达式的求值理解并能使用就已经差不多了。

如果对栈有兴趣的同学可以去学习一下关于栈是在函数调用中的运用等等。

ok，如有错，请留言。