栈

栈：只允许在一段进行插入或者删除操作的线性表

（First in last out）

1.栈的顺序表示

int main(){
    SqStack S;
    InitStack(S);
    Push(S,1);
    Push(S,2);
    Push(S,3);
    ElemType res;
    Pop(S,res);
    printf("pop_res->%d\n",res);
    return 0;
}

初始化栈

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack &S)
{
    S.top=-1;
}

判断栈是否为空

bool StackEmpty(SqStack S)
{
    if(S.top==-1)
    {
        return true;
    } else{
        return false;
    }
}

向栈中增加元素

bool Push(SqStack &S,ElemType x)
{
    if(S.top==MaxSize-1)
    {
        return false;
    }
    S.data[++S.top]=x;
    return true;
}

取栈顶元素

bool GetTop(SqStack S,ElemType &x)
{
    if(S.top==-1)
    {
        return false;
    }
    x=S.data[S.top];
    return true;
}

弹出栈顶元素

bool Pop(SqStack &S,ElemType &x)
{
    if(S.top==-1)
    {
        return false;
    }
    x=S.data[S.top--];
    return true;
}

2.栈的链式表示

#include <stdio.h>
#include <stdlib.h>


typedef int element_type;
typedef struct LStack{
    element_type data;
    struct LStack *next;
}LStack,*LinkStack;

int main()
{
    LinkStack S;
    InitStack(S);
    element_type insert_num_1,insert_num_2,insert_num_3;
    insert_num_1 = 1;
    insert_num_2 = 2;
    insert_num_3 = 3;
    Push(S,insert_num_1);
    Push(S,insert_num_2);
    Push(S,insert_num_3);
    PrintLStack(S);
}

bool InitStack(LinkStack &S)
{
    S = (LinkStack) malloc(sizeof (LStack));
    S->next = NULL;
    return true;
}

bool Push(LinkStack &S,element_type e)
{
    LinkStack new_one;
    new_one = (LinkStack) malloc(sizeof (LStack));
    new_one->data = e;
    new_one->next = S->next;
    S->next = new_one;
}

void PrintLStack(LinkStack S)
{
    LinkStack point;
    point = S->next;
    while (point!=NULL)
    {
        printf("%3d\n",point->data);
        point = point->next;
    }
}