数据结构基础----链栈

1、基于单链表的栈

头结点的插入和删除操作，时间复杂度均是O(1)，而末节点的插入操作是O(1)，删除操作是O(n)。相比而言，头结点插入和删除效率较高

以链表为底层的数据结构时，以链表头为作为栈顶较为合适，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部；

2、顺序栈、链栈比较

进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。顺序栈和链栈图解：

顺序栈是分配一段连续的空间，需要两个指针，base指向栈底，top指向栈顶。而链栈每个结点的地址是不连续的，只需要一个栈顶指针即可。

从上图可以看出，链栈的每个结点都包含两个域，数据域和指针域，是不是和单链表一模一样？那么我们就可以按单链表的定义。

3、链栈的结构体定义：

链栈的结点定义和单链表一样，只不过它只能在栈顶操作而已。

4、链栈操作

下面讲解链栈的初始化、入栈，出栈，取栈顶元素等操作（元素以int类型为例）。

1. 链栈初始化

初始化一个空栈，只需要让栈顶指针为空即可。

bool InitStack(LinkStack &S) //构造一个空栈S

{

    S=NULL;

    return true;

}

2. 入栈

入栈前要创建一个新结点，将元素e存入该结点的数值域：

 

p = new Snode; //生成新结点

p->data = e; //将e放在新结点数据域

然后将该结点的指针域指向S，再修改S指针指向该结点。

bool Push(LinkStack &S, int e) //在栈顶插入元素e

{

    LinkStack p;

    p = new Snode; //生成新结点

    p->data = e; //将e放在新结点数据域

    p->next = S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域

    S = p; //修改栈顶指针为p

    return true;

}

3. 出栈

出栈就是要把栈顶元素删除，让栈顶指针指向下一个结点，然后释放该结点空间。因此先用指针p指向栈顶元素（S指针指向的结点），即p=S；然后栈顶指针S指向它的下一个结点，即S=S->next；最后释放p指向的结点，即delete p。

bool Pop(LinkStack &S, int &e) //删除S的栈顶元素，用e保存其值

{

    LinkStack p;

    if (S == NULL) //栈空

        return false;

    e = S->data; //将栈顶元素赋给e

    p = S; //用p保存栈顶元素地址，以备释放

    S = S->next; //修改栈顶指针，指向下一个结点

    delete p; //释放原栈顶元素的空间

    return true;

}

4. 取栈顶元素

取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈顶指针并没有改变，而出栈是指删除栈顶元素，栈顶指针指向了下一个元素。

int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针

{

    if (S != NULL) //栈非空

        return S->data; //返回栈顶元素的值，栈顶指针不变

  else

      return -1;

}