栈

  • 栈的概念 一种特殊的线性表，只允许从一端插入和删除数据
  • 特点：后进先出
  • 顺序栈 顺序堆栈和顺序表数据成员相同，不同之处，顺序堆栈 的入栈和出栈操作只允许对当前栈顶进行

    栈/队列/链表 - 图1
  • 链式栈 头插头删

    栈/队列/链表 - 图2

  • 共享栈 :一个数组实现两个栈

  • 原理
    既然是两个栈共享一段空间，向中间靠拢，数组两端表示 两个栈的栈底，栈顶一直向中间靠近

栈/队列/链表 - 图3

  • 应用场景
    两个栈空间需求有相反的关系，也就是一个增长一个缩短 的场景

队列

  • 概念：只允许在一端插入数据，在另一端删除数据的特殊线性表
  • 顺序队列
    • 实现方式一 队头不动出队列时所有元素向前移动
    • 实现方式二 出队列时，队头向后移动一个位置
  • 假溢出现象
    多次入队列、出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出

    栈/队列/链表 - 图4
  • 真溢出现象 最大存储空间已经存储满，继续进行入队列操作

  • 循环队列
    头尾相接的顺序存储队列就是循环队列

    • 队列满队列空的判断

      • 少用一个存储空间
        队尾指针加一等于队头指针就是队列满的判断条件 (rear+1)%maxsize=front
        判空条件是尾和头相等 front=rear
      • 设计一个标记flag
        初始flag置为0，入队列成功flag=1，出队列成功flag置为 0
        队空条件 rear==front && flag=0,
        堆满条件 rear==front && flag=1

      • 设置一个计数器
        初始时count=0,入队列成功，count+1,出队列成功count 1
        队列空的条件count==0
        队列满的条件 count>0 && rear==front 或者count== MaxSize

      • 以下是少用一个存储空间示意图

        栈/队列/链表 - 图5

  • 链式队列
    队列的链式存储结构，其实就是线性表的单链表，只不过 它只能尾进，头出而已。为了操作上方便，一般将队头指针指向链队列的头结点，而队尾指针指向终端结点
    栈/队列/链表 - 图6
  • 优先级队列
    带有优先级的队列 优先级高的先出队列，优先级相同的遵守先进先出规则

链表

  • 链表
  • 双向链表
    栈/队列/链表 - 图7