• 复习四：栈

    一、栈的定义

    栈 （Stack）是 只允许在一端 进行插入或删除操作的 线性表 。
    栈顶 ( Top) 。 线性表允许进行插入删除的那一端 。
    栈底 ( Bottom) 。 固定的 ， 不允许进行插入和删除的另一端 。
    栈的操作特性可以明显地概括为 后进先出。
    栈的数学性质∶ n 个不同元素进栈，出栈元素不同排列的个数为

     栈的基本操作

    二、栈的顺序存储结构

    采用顺序存储的栈称为顺序栈

    栈顶指针 ： S . top, 初始时设置 S . top=-l ； 栈顶元素 ： S . data [S . top] 。
    进栈操作 ： 栈不满时 ， 栈顶指针先加 1, 再送值到栈顶元素 。
    出栈操作 ： 栈非空时 ， 先取栈顶元素值 ， 再将栈顶指针减 1 。
    栈空条件 ： S.top==-1 ； 栈满条件 ： S.top==MaxSize-l ； 栈长 ： S.top+1。
    由于 顺序栈的入栈操作受数组上界的约束 ， 当对栈的最大使用空间估计不足时 ， 有可能发生
    栈上溢 ， 此时应及时向用户报告消息 ， 以便及时处理 ， 避免出错

     

     

    注意 ∶这里top指向的是栈顶元素，所以进栈操作为 S.data【++S.top】=x，出栈操作为
    x=S.data【S.top--】。若栈顶指针初始化为S.top=0，即top 指向栈顶元素的下一位置，则
    入栈操作变为S.data【S.top++】=x;出栈操作变为x=S.data【--S.top】。相应的栈空、栈
    满条件也会发生变化
    共享栈：
    利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分
    别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
    两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize 时1号栈为空;仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时 top0 先加 1 再赋值，1号栈进栈时top1先减1再赋值∶出栈时则刚好相反。
    共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为0(1),所以对存取效率没有什么影响。

    三、栈的链式存储结构

    采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，目不存
    在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的【也就是说链栈的插入操作是通过头插法实现的，没有尾插法】。

     

                                                                   习题       

    参考答案：B

     参考答案：C

     参考答案C

     

     

     参考答案：C    题目要选的是错误的是

  • 相关阅读:
    【应用笔记】Sub-1G系列产品CW32W031单片机CAD应用参考
    1012 数字分类【PAT (Basic Level) Practice （中文）】
    chapter 01 字符串的那些事
    【Java复习】线程安全的 HashMap --- ConcurrentHashMap
    基于JAVA婚纱影楼服务管理计算机毕业设计源码+系统+mysql数据库+lw文档+部署
    x-pack的破解方式和免费jar包！！可直接用！！
    AI监管规则：各国为科技监管开辟了不同的道路
    UE5 虚幻引擎，打开空间蓝图，出现未识别的选项卡
    Nginx中server_name指令介绍
    Xcode中给UIView在xib中添加可视化的属性
  • 原文地址：https://blog.csdn.net/yyy_zxc/article/details/126771974