数据结构-栈

2018-06-13

　　生活中我们常常碰到这样的情况：浏览网页时，按后退键是一个返回刚刚浏览的一个网址,而不是最先开始浏览的或者是前几个任何一个的网址。为什么呢？？？这其实就是利用了栈后进先出的原理。

一、栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。把允许插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。
栈的插入操作叫做进栈，也称压栈、入栈；栈的删除操作叫做出栈，也有的叫做弹栈。

二、进栈出栈变化形式

　　栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制。即在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

三、栈的顺序存储结构及实现

1、栈的结构定义，如下：

#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
#define MAXSIZE 20                 /* 存储空间初始分配量 */  
typedef int Status;   
typedef int SElemType;             /* SElemType类型根据实际情况而定，这里假设为int */  
/* 顺序栈结构 */  
typedef struct  
{  
        SElemType data[MAXSIZE];  
        int top;                   /* 用于栈顶指针 */  
}SqStack;

2、栈的不同情况示意图，如下：

3、进栈操作：进栈示意图如下：

实现代码如下：

/* 插入元素e为新的栈顶元素 */  
Status Push(SqStack *S, SElemType e)  
{  
    if(S->top == MAXSIZE -1) /* 栈满 */  
    {  
        return ERROR;  
    }  
    S->top++;                 /* 栈顶指针增加1 */  
    S->data[S->top] = e;     /* 将新插入元素赋值给栈顶空间 */  
    return OK;  
}

4、出栈操作：代码如下：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */  
Status Pop(SqStack *S, SElemType *e)  
{   
    if(S->top == -1)  
    {  
        return ERROR;  
    }         
    *e = S->data[S->top]; /* 将要删除的栈顶元素赋值给e */  
    S->top--;                /* 栈顶指针减1 */  
    return OK;  
}

5、顺序栈的进栈和出栈操作时间复杂度：两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。

四、两栈共享空间（顺序栈）

1、两个相同类型的栈用一个数组来存储它们，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为数组长度n-1处。如下图。

2、两栈共享空间的结构的代码如下：

#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
#define MAXSIZE 20                      /* 存储空间初始分配量 */  
typedef int Status;   
typedef int SElemType;                  /* SElemType类型根据实际情况而定，这里假设为int */  
/* 两栈共享空间结构 */  
typedef struct   
{  
        SElemType data[MAXSIZE];  
        int top1;                       /* 栈1栈顶指针 */  
        int top2;                       /* 栈2栈顶指针 */  
}SqDoubleStack;

3、进栈操作：代码如下

/* 插入元素e为新的栈顶元素 */  
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)  
{  
    if (S->top1+1==S->top2)                /* 栈已满，不能再push新元素了 */  
    {  
        return ERROR;  
    }             
    if (stackNumber == 1)                /* 栈1有元素进栈 */  
    {  
        S->data[++S->top1] = e;          /* 若是栈1则先top1+1后给数组元素赋值 */  
    }          
    else if (stackNumber == 2)           /* 栈2有元素进栈 */  
    {  
        S->data[--S->top2] = e;          /* 若是栈2则先top2-1后给数组元素赋值 */  
    }          
    return OK;  
}

4、出栈操作：代码如下

Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)  
{   
    if (stackNumber == 1)   
    {  
        if (S->top1 == -1)   
        {  
            return ERROR;            /* 说明栈1已经是空栈 */  
        }         
        *e = S->data[S->top1--];     /* 将栈1的栈顶元素出栈 */  
    }  
    else if (stackNumber == 2)  
    {   
        if (S->top2 == MAXSIZE)   
        {  
            return ERROR;            /* 说明栈2已经是空栈 */  
        }      
        *e = S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */  
    }  
    return OK;  
}

5、两栈共享空间这样的数据结构通常是用在当两个栈的空间需求有相反关系时。

五、栈的链式存储结构及实现

1、栈的链式存储结构简称链栈。

2、由于单链表有头指针，而栈顶指针也是必须的，所以比较好的做法是把栈顶放在单链表的头部；另外由于已有了栈顶在头部了，所以通常对于链栈来说是不需要头结点的。如下图.

3、对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

4、链栈的结构代码如下：

#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
#define MAXSIZE 20 /* 存储空间初始分配量 */  
typedef int Status;   
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */  
/* 链栈结构 */  
struct StackNode  
{  
    SElemType data;  
    struct StackNode *next;  
};  
typedef struct StackNode *LinkStackPtr;  
typedef struct  
{  
    LinkStackPtr top;  
    int count;  
}LinkStack;

5、进栈操作：进栈操作示意图如下

实现代码：

/* 插入元素e为新的栈顶元素 */  
Status Push(LinkStack *S, SElemType e)  
{  
    LinkStackPtr lsptr = (LinkStackPtr)malloc(sizeof(struct StackNode));   
    lsptr->data = e;   
    lsptr->next = S->top;   /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */  
    S->top = lsptr;           /* 将新的结点s赋值给栈顶指针，见图中② */  
    S->count++;  
    return OK;  
}

6、出栈操作：删除示意图如下

判断链栈是否为空实现代码：

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */  
Status StackEmpty(LinkStack S)  
{   
    if (S.count == 0)  
    {  
        return TRUE;  
    }     
    else  
    {  
        return FALSE;  
    }     
}

出栈代码：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */  
Status Pop(LinkStack *S, SElemType *e)  
{   
    LinkStackPtr p;  
    if(StackEmpty(*S))  
    {  
        return ERROR;  
    }         
    *e = S->top->data;  
    p = S->top;                  /* 将栈顶结点赋值给p，见图中③ */  
    S->top=S->top->next;        /* 使得栈顶指针下移一位，指向后一结点，见图中④ */  
    free(p);                    /* 释放结点p */          
    S->count--;  
    return OK;  
}

7、链栈的进栈和出栈时间复杂度：时间复杂度均为O(1)。

六、栈的作用

1、栈的应用——递归：编译器使用栈来实现递归。简答的就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码段其余部分，也就是恢复了调用的状态。

2、栈的应用——四则运算表达式求值

　　2.1 后缀（逆波兰）表示法定义：把平时所用的标准四则运算表达式“9 + (3 - 1) * 3 + 10 / 2”叫做中缀表达式，因为所有的运算符号都在两数字的中间；而“9 3 1 - 3 * + 10 2 / +”这样的表达式称为后缀表达式，因为所有的符号都是在要运算数字的后面出现。

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

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