数据结构(三):栈

栈概念

  • 栈是仅在表尾(栈顶)进行插入和删除操作的线性表,是后进先出的线性表,简称 LIFO 结构,不含任何元素的栈称为空栈
  • 栈的插入操作也叫做进栈,栈的删除操作也叫做出栈
yQOsp.png

栈(stack)的抽象

  • Data(数据元素):同线性表,元素具有相同的类型,相邻元素具有前驱和后继关系
  • 基本操作
方法 描述
InitStack(*S) 初始化操作,建立一个空栈 S
DestoryStack(*S) 销毁一个栈
ClearStack(*S) 清空栈
StackEmpty(S) 若栈为空,返回true,否则false
GetTop(S,*e) 若栈存在且非空,返回 S 的栈顶元素
Push(*S,e) 插入新元素 e 到栈 s 中并成为栈顶元素
Pop(S,e) 删除栈 s 中的顶元素,返回其值
StackLength(S) 返回栈 S 元素个数

栈的链式存储结构

  • 将栈顶放在链表的头部
  • 对于链表来说基本不存在栈满情况,除非没有内存可以使用

栈的进栈 push 与出栈 pop

  • 进出栈操作都很简单,没有任何循环操作,时间复杂度为 O(1)
  • 顺序栈与链表栈的区别是顺序栈需要确定长度,可能会存在内存空间浪费问题,但优势是存取定位方便,而链表栈每个元素都有指针域,会增加一点内存开销,但栈长度无限制

最先进栈的一定最后出栈?

  • 最先进栈的不一定最后出栈,如有3个整形数字元素1、2、3依次进栈,会有以下几个出栈顺序:
    • 第一种:1、2、3 进,再 3、2、1 出,出栈顺序为 321
    • 第二种:1进,1出,2进,2出,3进,3出,出栈顺序为 123
    • 第三种:1进、2进,2出,1出,3进,3出,出栈顺序为 213
    • 第四种:1进,1出,2进,3进,3出,2出,出栈顺序为 132
    • 第五种:1进、2进、2出、3进、3出,1出,出栈顺序为 231
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,936评论 0 7
  • 3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: (...
    云时之间阅读 2,208评论 0 3
  • 通常程序开发中内存管理是非常重要的,而内存主要分为占内存和堆内存。那么栈和堆内存有什么区别呢?希望在这篇文章里能带...
    xiaoyouPrince阅读 667评论 0 3
  • 五月底六月初,原本已经是盛夏光年,但却有一种烟雨蒙秋的感觉。窗外的风没有吹麦浪的清新凉爽,反而有点微凉,我加了一件...
    sui无言阅读 350评论 0 0
  • 32.13-32.16 来自致良知四合院 【32.13】 夫拔本塞源之论不明于天下,则天下之学圣人者,将日繁日难,...
    石竹阅读 1,925评论 4 6