栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”。向一个栈内插入元素称为是进栈，push；从一个栈删除元素称为是出栈，pop。特点 ：后进先出（LIFO）。 

栈的存储

栈的存储方式分为顺序存储和链式存储。

栈的顺序存储结构需要使用连续的存储空间，并且需要一个元素来确定它的栈顶。利用数组来顺序存储栈中的所有元素，利用整型变量存储栈顶元素的下标位置，可以把这个变量称为栈顶指针。

可以使用下面的结构体来描述栈：

typedef int data_t;

#define SIZE 100;

struct Stack 

{

data_t data[SIZE];

int top;

};

也可以使用动态分配内存的办法描述栈：

struct Stack

{

data_t * pData;

int top;

int maxSize;

};

top=-1表示栈空。

栈的链式存储结构

栈的链式存储结构是通过由结点构成的单链表实现的。此时，表头指针被称为是栈顶指针，由栈顶指针指向的表头结点被称为是栈顶结点，整个单链表被称为是链栈。对于链栈的入栈和出栈都是在表头进行。

可以使用下面的数据结构来描述栈：

typedef int data_t;

struct stackNode

{

data_t   data;

struct stackNode * pNext;

};

如果想要一个确定大结点数的链栈，可以将单链表的头结点的数据域强转为保存结点个数的值。头结点指针域的值为NULL时，表示空栈。

栈的应用

简单应用

1.输入之后逆序输出

2.语法检查：括号匹配

每当扫描到大中小的括号后，令其进栈，当扫描到右括号时，则检查栈顶是否为相应的左括号，若是，则出栈处理，若不是，则出现了语法错误。当扫描到文件结尾，若栈为空则表明没有发现括号配对错误。

3.数制转换

十进制转八进制。例如(1348)十进制= (2504)八进制,它基于如下的原理:

   N             N/8                N%8

 1348            168                   4

  168             21                   0

   21              2                   5

    2              0                   2

 

所以很明显，N不断的除8，每次的余数就是结果的其中一个因子，注意先出来的因子是低位的数，可以考虑用栈来保存每次取余的结果，那么出栈的顺序就是实际的结果顺序。

代码如下：

int decimalToOctonary(int decimalNumber)  

{

double octNumber = 0;

    int nCount = 0;

    int nTemp = 0;

struct stack * pNumberStack;

    //定义栈，pNumberStack并且初始化该栈  代码略

    pNumberStack = createStack();

 

while (decimalNumber)

    {

nTemp = (int)decimalNumber%8;    

//将nTemp入栈pNumberStack  代码略 

push(pNumberStack, nTemp);

decimalNumber = decimalNumber/8; 

}  

nCount = CountOfStack(numberStack);//元素个数也就是位数

while(!IsEmptyStack(numberStack))      

{          

//将栈numberStack中的元素出栈，并且赋值给nTemp  代码略

pop(pNumberStack, &nTemp);

        octNumber += (nTemp*pow(10.0, --nCount));   

} 

//销毁栈numberStack

    DestroyStack(&numberStack);  

//返回转换后的八进制数

return (int)octNumber;  

}

中缀和后缀表达式的转换及计算

1.两种表达式

中缀表达式：人使用的类似于(2+3*5)，运算符号在数字中间的表达式。计算需要注意优先级、括号这些问题，和运算符的实际运算次序往往同它们在表达式中的先后次序不一致，所以波兰科学家提出了后缀表达式，把运算符放在两个运算对象的后面。

在后缀表达式中看，不存在括号，也不存在运算符优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需扫描一遍便可完成。

2.中缀表达式转换成后缀表达式的转化规则和思路

利用栈，可以实现中缀表达式转化为后缀表达式。也可以实现后缀表达式的计算。这里主要实现难度较大的中缀表达式向后缀表达式的转化。中缀算术表达式转换成对应的后缀算术表达式的规则是：把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。

为了转换正确，必须设定一个运算符栈，并在栈底存放一个特殊运算符，假定为’@’，让它具有低的运算符优先级，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，等待它的两个运算对象都放入到后缀表达式后，再令其出栈并写入后缀表达式中。转换的过程如下：

转换过程如下：从头到尾扫描中缀表达式，若遇到数字则直接写入后缀表达式，若遇到运算符，则比较栈顶元素和该运算符的优先级，当该运算符的优先级大于栈顶元素的时候，表明该运算符的后一个运算对象还没有进入后缀表达式，应该把该运算符暂存于运算符栈中，然后把它的后一个运算对象写入到后缀表达式中，再令其出栈并写入后缀表达式中；若遇到的运算符优先级小于等于栈顶元素的优先级，表明栈顶运算符的两个运算对象已经被写入后缀表达式，应将栈顶元素出栈并写入后缀表达式，对于新的栈顶元素仍进行比较和处理，直到栈顶元素的优先级小于当前等待处理的运算符的优先级为止，然后令该运算符进栈即可。

按照上述过程扫描到中缀表达式的末尾，把剩余的运算符依次出栈并写入后缀表达式即可。

（对于左括号直接进栈，右括号则使左右两个括号内的运算符都出栈）。

后缀表达式求值

后缀表达式求值也需要一个栈，其元素类型为操作数的类型，此栈存储后缀表达式中的操作数、计算过程的中间结果及后结果。

计算过程如下：扫描后缀表达式，若遇到操作数则进栈，若遇到操作符则弹出两个操作数进行计算，然后将结果压进栈，直到后扫描完毕，栈中应该保存着终结果。

以上是关于栈及栈的常见的应用的一个总结。