栈

数据结构

1. 栈的定义

栈（stack):是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top)，另一端称为栈底（bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out)的线性表，简称LIFO结构。

2. 栈的抽象数据类型

ADT 栈（stack)
DATA
通线性表，元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
    InitStack(*s):初始化操作，建立一个空栈；
    DestroyStack(*s):若栈存在，则销毁它；
    ClearStack(*s):将栈清空；
    StackEmpty(*S):若栈为空，则返回true,否则返回false;
    GetTop(*s,*e):若栈存在且非空，则用e返回s栈顶元素；
    Push(*s,e):若栈s存在，插入新元素e到栈s中并成为栈顶元素
    Pop(*s,*e):删除栈s中栈元素，并用e返回其值；
    StackLength(*s):返回栈s的元素个数
end  ADT

2.1 栈的顺序存储结构及其实现

#ifndef STACK_H
#define STACK_H
typedef int ElemType;
#define MAX_SIZE 20
typedef struct 
{
    ElemType data[MAX_SIZE];
    int top;/*用于栈顶指针*/
}SqStack;
void InitStack(SqStack*s);
bool Push(SqStack*s,ElemType e);
bool Pop(SqStack*s,ElemType &e);
#endif

#include "stack.h"
/*数组存储栈系列操作*/
/* 栈初始化*/
void InitStack(SqStack* s)
{
    s->top = -1;
}
/*入栈*/
bool Push(SqStack*s,ElemType e)
{
    if (s->top == MAX_SIZE - 1)/*栈满*/
        return false;
    s->top++;
    s->data[s->top] = e;
    return true;
}
/*出栈*/
bool Pop(SqStack*s,ElemType &e)
{
    if (s->top < 0)/*栈为空*/
        return false;
    e = s->data[s->top];
    s->top--;
    return true;
}

2.2 栈的链式存储结构及实现

#ifndef STACK_H
#define STACK_H
typedef int ElemType;
typedef struct StackNode
{
    ElemType data;
    struct StackNode* next;
}StackNode,*LinkStackPtr;
typedef struct 
{
    int count;/*元素个数计数*/
    LinkStackPtr top;/*用于栈顶指针*/
}LinkStack;
void InitStack(LinkStack *s);
bool Push(LinkStack*s, ElemType e);
bool Pop(LinkStack*s, ElemType &e);
#endif

#include "stack.h"
#include<cstdlib>
/*数组存储栈系列操作*/
/* 栈初始化*/
void InitStack(LinkStack *s)
{
    s->top = NULL;
    s->count = 0;
}
/*入栈*/
bool Push(LinkStack*s, ElemType e)
{
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!temp)/*内存申请失败*/
        return false;
    temp->data = e;
    temp->next = s->top;
    s->top = temp;
    s->count++;
    return true;
}
/*出栈*/
bool Pop(LinkStack*s, ElemType &e)
{
    if (s->count < 0)/*栈为空*/
        return false;
    e = s->top->data;
    LinkStackPtr p = s->top;/*取出栈顶*/
    s->top = p->next;//更新栈顶指针
    free(p);
    p = NULL;
    s->count--;
    return true;
}

#include<cstdio>
#include<cstdlib>
#include"stack.h"
int main()
{
    LinkStack s;
    InitStack(&s);
    int e;
    for (int i = 0; i < 10; i++)
        Push(&s, i);
    Pop(&s, e);
    printf("%d", e);
}

3. 栈的应用---四则运算表达式

3.1 后缀（逆波兰）表达式求值

eg:中缀表达式：9+(3-1)*3+10/2
对应的后缀表达式：9 3 1 - 3 * + 10 2 / +

后缀表达式求值策略：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

3.2 中缀表达式转后缀表达式

标准四则运算表达式：'9+(3-1)*3+10/2' 叫做中缀表达式。
转化为对应的后缀表达式：‘9 3 1 - 3 * + 10 2 / +’

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级不高于栈顶符号（乘除优先加减），则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。

参考：《大话数据结构》清华大学出版社，程杰著；
http://www.cnblogs.com/cj723/archive/2011/02/06/1949498.html