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)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。
领取专属 10元无门槛券
私享最新 技术干货