美文网首页
数据结构与算法栈和队列

数据结构与算法栈和队列

作者: 傻疯子 | 来源:发表于2022-02-22 17:06 被阅读0次

    1.栈的基本概念
    只允许在一端进行插入或删除操作的线性表,先进后出

    结构:
    栈顶(Top):线性表允许进行插入和删除的那一端
    栈低(Bottom):固定的,不允许进行插入和删除的另一端

    卡特兰数:n个不同元素进栈,出栈元素不同排列的个数为 \frac{1}{n+1}C_{2n}^{n}

    2.栈的顺序存储结构
    顺序栈:采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈低到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置

    共享栈:让两个顺序栈共享一个一维数组空间,将两个栈的栈低分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸

    3.栈的链式存储结构
    采用单链表实现,并规定所有操作都是在单链表的表头进行
    优点:便于多个栈共享存储空间和提高效率,且不存在栈满上溢的情况

    4.队列的基本概念
    队列的定义:是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除,先进先出

    结构:
    队头Front:允许删除的一端又称队首
    队尾Rear:允许插入的一端
    空队列:不含任何元素的空表

    5.队列的顺序存储结构
    队列的顺序存储:分配一端连续的存储单元存放队列中的元素,并附设两个指针

    循环队列:把存储队列元素的表从逻辑上视为一个环

    6.队列的链式存储结构
    队列的链式表示称为链队列,是一个同时带有队头和队尾的单链表

    优点:适合于数据元素变动比较大的情形,不存在队列满且产生溢出的问题

    7.双端队列
    概述:双端队列是指允许两端都可以进行入队和出对操作的队列,逻辑结构仍是线性结构,将队列的两端分别称为前端和后端,两端都可以入队和出对

    分类:
    输出受限的双端队列:允许在一端进行插入和删除,但在另一端只允许插入的双端队列
    输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列

    相关文章

      网友评论

          本文标题:数据结构与算法栈和队列

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