数据结构------栈和队列

一、栈的基本概念:只允许在一端进行插入或者删除操作的线性表  <后进先出>

  栈顺序存储结构:

    共享栈:将两个栈底设置在共享空间的两端,栈顶向空间中间延伸

       判空:0号栈 top == -1    1号栈 top == MaxSize

       栈满:top1 - top0 == 1

       优点:存取时间复杂度仍未O(1),但空间利用更加有效

栈链式存储结构:

  链栈 采用链式存储的栈  → 所有的操作都在表头进行

四、队列的基本概念: 

只允许在表的一端进行插入,表的另一端进行删除操作的线性表<先进先出>

队列的顺序存储:

  循环队列:把存储队列的顺序队列在逻辑上视为一个环

    牺牲一个存储单元

      判断队空条件:Q.front == Q.rear

      判断队满条件:Q.front == (Q.rear + 1) %(取余) MaxSize

    增加一个变量代表元素的个数

    增加tag标识

队列的链式存储结构

  链队:采用链式存储的队列

相关推荐