考研数据结构-栈

(一)、栈的基本概念

         栈是一种只能在一端进行插入或者删除操作的线性表。允许插入或者删除的一端称为栈顶。栈顶由一个称为栈顶指针的位置指示器(是一个变量，对于顺序栈，就是记录栈顶元素所在数组位置符号的一个整型变量；对于链式栈，就是记录栈顶元素所在结点地址的指针)来指示，它是动态变化的。表的另一端称为栈底，栈底是固定不变的。栈的插入和删除操作一般称为入栈和出栈。

        栈的主要特点是先进后出(FILO)。先进入栈的元素后出来，最后进入栈的元素先出来。

        栈的存储结构分为——顺序表和链表来表示，也就是分为顺序栈和链式栈。栈是一种在操作上稍加限制的线性表，即栈的本质上是线性表。

(二)、栈的存储结构、算法      

           顺序栈的定义

typedef struct SqStack
{
    /* data */
    int data[maxSize]; // 存放栈中的元素，MaxSize已经定义
    int top;    //栈顶指针
}SqStack;

        链栈的定义

/*链栈结点定义*/
typedef struct LNode
{
    /* data */
    int data; //数据域
    struct LNode *next;
}LNode;

        顺序栈

        对于顺序栈st，一共包含4个要素，包含两个特殊状态和两个操作。两个状态分别为：栈空状态。st.top==-1。栈满状态。st.top==maxSize-1；两种操作分别为：元素x进栈操作：++(st.top);st.data[st.top]=x。元素x出栈操作：x=st.data[st.top];--(st.top)。

        初始化栈的代码

void initStack(SqStack *st)
{
    st->top = -1; // 只需要将栈顶指针设为-1
}

        判断栈中代码

/*判断栈空代码，栈st空时返回1，否则返回0*/
int isEmpty(SqStack st)
{
    if (st.top == -1)
    {
        /* code */
        return 1;
    }else{
        return 0;
    }
}

        进栈代码

/*进栈代码*/
int push(SqStack *st,int x)
{
    if (st->top == maxSize - 1) // 栈满
    {
        /* code */
        return 0;
    }

    st->top = st->top + 1;
    st->data[st->top] = x;
    return 1;
    
}

        出栈代码

int pop(SqStack *st,int *x)
{
    if(st->top == -1)
        {
            return 0;
        }

    x = st->data[st->top];
    st->top = st->top - 1;
    return 1;
}

        高效的代码书写

/*栈的定义*/
int stack[maxSize];int top = -1;
/*元素x进栈*/
stack[++top]=x;
/*元素x出栈*/
x=stack[top--];

        链栈

        和顺序栈对应，链栈也有4个要素，包含两个特殊状态和两个操作。

        链栈的初始化代码

void initStack(LNode *lst)
{
    lst = (LNode*)malloc(sizeof(LNode*)); //制造一个头结点
    lst->next=NULL;
}

        判断栈空代码

/*判断栈空代码*/
int isEmpty(LNode *lst){

    if (lst->next == NULL)
    {
        /* code */
        return 1;
    }else{
        return 0;
    }
    
}

        进栈代码

/*进栈代码*/
void push(LNode *lst,int x){

    LNode *p;
    p = (LNode*)malloc(sizeof(LNode*)); //为进栈元素申请空间
    p->next = NULL;

    /*链表的头插表*/
    p->data = x;
    p->next = lst->next;
    lst->next = p;
}

        出栈代码

void pop(LNode *lst,int *x){ //需要改变的变量要用引用型
    LNode *p;
    if (lst->next == NULL) //若为空，则不能出栈
    {
        /* code */
        return 0;
    }

    p = lst->next;
    x = p->data;

    lst->next = p->next;
    free(p);
    return 1;
    
}