美文网首页
03 - 栈和队列认识

03 - 栈和队列认识

作者: iOS之文一 | 来源:发表于2021-10-26 12:33 被阅读0次

    数据结构和算法学习汇总

    栈和队列也是一种线性表,但是相关运算有特殊性,所以是一种受限的线性表。

    栈是一种只能在一端进行插入或删除的线性表,且遵循后进先出的原则。

    • 表中允许进行插入、删除操作的一端为栈顶
    • 栈顶的当前位置是动态的,有一个称为栈顶的指针的位置指示器指示
    • 表的另一端称为栈底
    • 添加元素叫入栈,移除元素叫出栈

    特点: 后进先出

    栈可以由动态数组和链表来实现,所以有两种栈,顺序栈和链式栈

    链栈:

    • 栈不一定是顺序存储结构,也可以是链式存储结构
    • 采用顺序存储的栈称为顺序栈,采用链式存储的称为链式栈
    • 链式存储结构的栈需要规定所有的操作只能在单链表的表头进行,
    • 所以它并没有一般意义上的链表的便于增删的优点
    • 链栈的优点是不存在栈满上溢的情况

    注意:

    • 此处所说的栈是一种线性表,与五大内存区域的栈空间不是一个概念。

    队列

    队列是一种只能在一端进行插入,在另一端进行删除的线性表,遵循先进先出原则
    插入的那一段称为队尾,删除的那一端称为队头。注意队头队尾不要反了。

    存储结构包括顺序存储结构和链式存储结构

    特点: 先进先出

    顺序存储结构

    需要使用一个数组和两个整数型变量来实现,利用数组顺序存储队列中的所有元素,利用两个整型变量分别存储队首元素和队尾元素的下标位置,分别称为队首指针和队尾指针。

    顺序队列

    • 队尾指针总是指向当前队列中队尾的元素
    • 队头指针总是指向队列中队头元素的前一个位置

    假溢出问题:

    • 进队操作会将队尾指针+1,出队操作会将队头指针+1,
    • 而队满的条件是队尾指向最后一个空间地址
    • 此时出队若干元素,队头并没有指向第一个位置,就会造成队列中有空位置,但仍然会得到队满的信息,这就是假溢出

    环形队列

    环形队列可以解决顺序队列的假溢出问题,为了解决假溢出,能够充分使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,就是环形队列。

    队列操作:

    • 在顺序队列的基础上,需要进行取余运算
    • 队首指针进1:front = (front+1)%MaxSize
    • 队尾指针进1:rear = (rear+1)%MaxSize

    队满判断条件:

    • 约定进队时少用一个数据元素空间
    • (q->rear+1))%MaxSize==q->front

    队空判断条件:

    • q->rear == q->front

    链式存储结构

    通过节点构成的单链表来实现,只允许在单链表的表首进行删除操作和再单链表表尾进行插入操作,叫做链队。

    总结

    • 队列和栈都属于线性表
    • 队列遵循先进先出原则,栈遵循后进先出原则

    相关文章

      网友评论

          本文标题:03 - 栈和队列认识

          本文链接:https://www.haomeiwen.com/subject/jynealtx.html