栈和队列

栈

一、基本概念

1、定义

​ 栈：只能在一端删除或者插入的线性表叫做栈。

​ 栈顶：允许删除或者插入的那端叫做栈顶

​ 栈底：与栈顶相对应的一端。

2、特点

​ 先进后出（FILO）：先进入栈的数据元素后出栈。

二、栈的存储结构、算法和应用

（一）、顺序栈

1、定义

typedef struct{
    int data[max];
    int top;
}SqStack;

2、初始化栈

void initStack(SqStack &st){
    st.top = -1;
}

3、判断栈空

int isEmpty(SqStack st){
    if(st.top==-1)
        return 1;
    return 0;
}

4、进栈

int push(SqStack &st,int x){
    if(st.top == max-1)
        return 0;
    ++st.top;
    st.data[st.top] = x;
    return 1;
}

5、出栈

int pop(SqStack &st,int &x){
    if(st.top == -1)
        return 0;
    x = st.data[st.top];
    --st.top;
    return 1;
}

（二）、链栈

1、定义

typedef struct LNode{
    int data[max];
    struct SqStack *next;
}LNode;

2、初始化

void initStack(LNode *&list){
    list = (LNode*)malloc(sizeof(LNode));
    list->next = NULL;
}

3、判断栈空

int isEmpty(LNode *list){
    if(list->next == NULL){
        return 1;
    }else{
        return 0;
    }
}

4、进栈

void push(LNode *list,int x){
    LNode *p;
    p = (LNode*)malloc(sizeof(LNode));
    p->next = NULL;

    p->data = x;
    p->next = list->next;
    list->next = p;
}

5、出栈

int pop(LNode *list,int x){
    LNode *p; //定义一个结点
    if(list->next ==NULL){
        return 0;
    }
    p=list->next; 
    x=p->data;
    list->next = p->next;
    free(p);
    return 1;
}