【图解】数据结构代码领背-14

01

链栈的基本运算：出栈

在前面的学习中，我们介绍了链栈的初始化，判断栈空以及入栈。这一次我们来介绍链栈的最后一项基本运算----出栈，也顺便对栈这一数据结构的学习进行一次总结。

01

图例

前面我们提到，链栈的基本操作其实本质都可以转化为链表的基本运算，那么出栈这一操作也就对应着链表中删除这一结点的操作。但是因为栈的出入操作都是在栈的一端完成，是一个后进先出的数据结构，所以每次删除的是位于栈顶的结点即可。

这里我们回忆一下链表的删除操作，在单链表中，想要实现删除操作，就是将它的前继结点绕过，指向它的后继结点即可，如图1所示：

图1

实际上就是一步，p->next = p->next->next，用q来取代p->next，即是：q = p->next ; p->next = p->next->next。这里只是带大家简单回顾，具体的内容我们可以到代码领背6中进行复习。

所以我们结合起来看链栈的出栈，在链栈中若要将元素3出栈，根据"先进后出"的原则，要先将元素4出栈，也就是从链表中摘除，然后元素3才能出栈，整个操作过程如图下所示：

a）初始链栈：head -> 4 -> 3 -> 2 -> 1 -> NULL

b）元素4出栈：head -> 3 ->2 -> 1 -> NULL

c）元素3出栈：head -> 2 -> 1 -> NULL

02

代码

在对链栈的出栈操作有了基本的认识后，我们来看代码：

03

总结

我们可以把整个思路整理成3步：

1.判断是否为空：出栈前判断栈是否为空，如果栈空，那么出栈操作也就不存在。

2. 找到出栈结点：遍找到要删除的结点即要出栈的结点。

3. 进行删除操作：把要删除结点的前驱的后继变为被删除的结点的后继，即之前举例介绍的那个操作。

可以用一句话来帮助记忆：判栈空（lst->next == NULL），找栈顶（p = lst->next），删栈顶（lst->next = p->next）。

我们只需要把它作为链表的头插法操作代码来进行记忆，就会十分容易。还是如上节所说，我们需要把这一部分的知识与链表紧密结合，才能达到最好的学习效果。

而在学完了顺序栈和链栈的内容后，我们对两者进行一个比较。同样是栈数据结构，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内,建议使用顺序栈会更好一些。