数据结构——栈

1.栈的定义以及常用术语

[1] 栈：栈是只允许在一端进行插入和删除操作的线性表。

[2]常用术语：栈顶、栈底以及空栈。

栈顶：允许插入和删除的一端。

栈底：不允许进行插入和删除操作的一端。

空栈：不含任何数据元素的栈。

[3]栈的特点:后进先出

现在可以看一个图像去理解栈顶和栈底

栈的逻辑结构与普通的线性表相同，但是在数据的运算方面只能够在栈顶进行插入和删除操作，而不能在其他位置

栈的定义代码实现：

#define MAXSIZE 10  //定义栈中元素的最大个数
typedef int ElemType;//根据实际需要自定义数据类型
typedef struct
{
    ElemType data[MAXSIZE];//静态数组存放栈中元素
    int top;//栈顶指针
} SqStack;

2.顺序栈的基本操作以及共享栈

(1)顺序栈的基本操作：创、增、删、查、判空或判满

[1]创：初始化栈，创建一个空栈S分配内存空间（lnitstack）

void initstack(SqStack *S)//初始化栈
{
    S.top=-1;//初始化栈顶指针
}

[2]增：进栈，若栈S未满，则将元素x加入，使其成为新的栈顶（push）

//进栈
bool Push(SqStack *S,ElemType e)
{
    if(S.top==MAXSIZE-1)//栈顶元素达到上限
    {
        return false;//说明进栈失败
    }
    S.top++;//栈顶指针+1，说明要进来一个元素
    S.date[S.top]=e;//将元素进行进栈
    return true;
}

[3]删:出栈，若栈S非空，则弹出栈顶元素，并用x返回（pop）

//出栈
bool Pop(SqStack *S,ElemType *x)
{
    if(S.top==-1)//栈顶指针指向-1，说明栈已经空了
    {
        return false;//没法出栈了，直接返回错误
    }
    x=S.date[S.top];//输出栈顶元素
    S.top--;//栈顶指针-1，更新新的栈顶元素
    return true;
}

[4]查：读取栈顶元素，若栈S非空，则用x返回栈顶元素（gettop）

读取栈顶元素与出栈代码很相似。

//读取栈顶元素
bool GetTop(SqStack S, ElemType *x)
{
    if(S.top==-1)//当空栈之后，没有栈顶元素，直接错误就可以
    {
        return false;
    }
    x=S.date[S.top];
    return true;
}

出栈会将栈顶元素从逻辑上删除，而读取栈顶元素则不会

[5]判空，判断一个栈S是否为空，若S为空则返回true，若不为空，则返回flase（stackempty）

//判空
bool StackEmpty(SqStack S)
{
    if(S.top == -1)
    {
        return true;    //栈空
    }
    else
    {
        return false;   //不空
    }
}

（2）共享栈：两个栈共享一片空间。

共享栈的定义：（可以结合上图来看）

//共享栈的定义
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   
typedef struct
{
    ElemType data[MAXSIZE];
    int top1;	//1号栈栈顶指针
    int top2;	//2号栈栈顶指针
} SqDoubleStack;

共享栈的进栈：（1号栈从前往后存储，2号栈从后往前存储）

//共享栈的出栈
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber)
{
    if(S.top1+1 == S.top2)    //栈满
    {
        return false;
    }
    if(stackNumber == 0)    //栈0有元素进栈
    {
        S.data[++S.top1] = e; //若栈0则先top0+1后给数组元素赋值
    }
    else if(satckNumber == 1)   //栈1有元素进栈
    {
        S.data[--S.top2] = e; //若栈1则先top1-1后给数组元素赋值
    }
    return true;
}

共享栈的出栈：

//共享栈的出栈
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber)
{
    if(stackNumber == 0)
    {
        if(S.top1 == -1)
        {
            return ERROR;   //说明1号栈已经是空栈，溢出
        }
        *e = S.data[S.top1--]; //将1号栈的栈顶元素出栈，随后栈顶指针减1
    }
    else if(stackNumber == 1)
    {
        if(S.top1 == MAXSIZE)
        {
            return ERROR;   //说明2号栈是空栈，溢出
        }
        *e = S.data[S.top1++];    //将2号栈的栈顶元素出栈，随后栈顶指针加1
    }
    return OK;
}

3.栈的常考题型

进栈顺序是栈常考的题目，就是说可能会让你通过模拟栈的视线来判断输入的数据是否的合理的栈输出，话不多说，来一个典型的题来说明一下

例题：验证栈序列

这题就是一个模拟栈进出的过程若符合，则能够满足栈的标准输出

#include<stdio.h>
int a[100001],b[100001],c[100001]; 
//a数组用来表示入栈序列，b数组用于表示出栈序列，c数组用于模拟
int main()
{
    int q;
    scanf("%d",&q);//输入询问次数
    int a1,b1,c1;
    while(q--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]); // 输入入栈序列
        }
        for(int i=0; i<n; i++)
        {
            scanf("%d",&b[i]); // 输入出栈序列
        }
        a1=0,b1=0,c1=0;
        int flag=1;
        while(b1!=n)
        {
            c[c1]=a[a1]; // 模拟入栈
            while(c[c1]==b[b1]&&b1!=n&&c1>=0) // 当栈顶元素与出栈序列匹配时，出栈
            {
                c1--;
                b1++;
            }
            c1++;
            a1++;
            if(a1==n&&b1!=n) // 如果入栈序列已经遍历完，但出栈序列还有剩余，则无法匹配
            {
                flag=0;
                break;
            }

        }
        if(flag==0)
        {
            printf("No\n"); // 无法匹配
        }
        else
        {
            printf("Yes\n"); // 能够匹配
        }
    }
    return 0;
}