数据结构【DS】栈

共享栈

共享栈的目的是什么？

• 目的:有效利用存储空间。

共享栈的存取数据时间复杂度为？

• 存取数据时间复杂度为O(1)

共享栈如何判空？如何判满？

• 两个栈的栈顶指针都指向栈顶元素，𝑡𝑜𝑝0=−1时0号栈为空；𝑡𝑜𝑝1=𝑀𝑎𝑥𝑆𝑖𝑧𝑒 时1号栈为空;
• 仅当两个栈顶指针相邻(𝑡𝑜𝑝1−𝑡𝑜𝑝0=1) 时，判断为栈满。

链栈

链栈的优点是什么？

• 不存在栈满上溢。

链栈的操作在哪进行？

• 通常采用单链表实现，规定所有操作都在单链表表头进行。

链栈的基本操作

//定义栈结点

typedef struct SNode{                        //定义单链表结点类型

    int data;                                        //每个节点存放一个数据元素

    struct SNode *next;                        //指针指向下一个节点

}SNode, *LiStack;

//初始化一个链栈（单链表实现，栈顶在链头）

bool InitStack(LiStack &S) {

    S = (SNode *) malloc(sizeof(SNode)); //分配一个头结点

    S->next = NULL;         //头结点之后暂时还没有节点

    return true;

}

//判断栈是否为空

bool StackEmpty(LiStack S){

    if(S->next==NULL)   //头结点后面没有结点

        return true;    //返回true，表示栈为空

    else

        return false;

}

//入栈（本质上是单链表的“头插法”）

bool Push (LiStack &S, int x){

    SNode * p = (SNode *) malloc(sizeof(SNode));    //新分配一个结点

    p->data = x;     //存入新元素

    p->next = S->next;

    S->next = p;     //新结点插入到头结点后面

    return true;

}

//出栈（本质上是单链表的“头删法”）

bool Pop (LiStack &S, int &x){

    if (StackEmpty(S))      //栈空，出栈操作失败

        return false;

    SNode * p = S->next;     //栈不空，链头结点出栈

    x = p->data;             //x返回栈顶元素

    S->next = p->next;       //头删法，栈顶元素"断链"

    free(p);                 //释放结点

    return true;

}