栈 | Personal Blog

栈

发表于

1.栈是一种限定性线性表

栈只允许在一个端点进行操作，称为栈顶，由栈顶指示器指针指向，其初值为-1.

2.结构

栈由一个存储元素的数组和栈顶指示器构成

顺序栈

进栈

若数组没有空间，再进行进栈操作则会发生上溢

若数组仍有空间： 1.栈顶指示器指针自增一 2.对数组中以当前栈顶指示器指针为下标的元素进行赋值

出栈

若栈区没有元素，再进行出栈操作则会发生下溢

若栈区有元素： 1.将栈顶元素储存至指定位置 2.栈顶指示器自减一

两栈共享的数据结构

一个栈自前向后储存，另一个自后向前储存；设置两个栈顶指示器指针；即入栈时，一个栈顶指示器指针自增一，另一个自减一，直至两栈顶指针相差一

定义：

1
2
3
4
5
6
7
#define M 100

typedef struct
{
    StackElementType Stack[M];
    StackElementType top[2];
}DqStack;

初始化：

1
2
3
4
5
void InitStack(DqStack *S)
{
    S->top[0]=-1;
    S->top[1]=M;
}

进栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Push(DqStack *S.StackElementType x,int i)
{
    if(S->top[0]+1==S->top[1]) //判断是否发生上溢
    {
        return (FALSE);
    }
    switch(i)
    {
        case 0:S->top[0]++;S->Stack[S->top[0]]=x;break;
        case 1:S->top[0]--;S->Stack[S->top[1]]=x;break;
        default :return(FALSE)
    }
    return(TRUE);
}

出栈：

1
2
3
4
5
6
7
8
9
10
11
12
int Push(DqStack *S.StackElementType x,int i)
{
    swich(i)
    {
        case 0:if(S->top[0]==-1) return(FALSE);
        *x=S->Stack[S->top[0]];S->top[0]--;break;
        case 1:if(S->top[0]==M) return (FALSE);
        *x=S->Stack[S->top[1]];S->top[1]++;break;
        default:ruturn(FALSE);
    }
    return(TRUE);
}

链栈

链栈的相关操作与顺序栈类似，入栈相当于头插入一个结点，出栈则相当于删除头结点所指向的结点。

中断

在计算机执行程序A的过程中，需要执行程序B，将程序A打断，此时需要构造一个栈架，将A程序的相关信息层层入栈，进行现场保护，执行完B程序后再依次出栈，恢复现场。

算数表达式

1.自左向右扫描，运算数进入运算数栈，运算符进入运算符栈 2.当前运算符优先级小于或等于运算符栈栈顶运算符时，运算符栈出栈一次，运算数栈出栈两次，计算，将得到的运算结果入栈运算数栈