请选择 进入手机版 | 继续访问电脑版

数据结构-栈和队列

[复制链接]
丶禁飞 发表于 2020-12-31 17:53:26 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题

  • 线性表、栈和队列都是线性布局,可以在线性表的任何 位置插入和删除元素;对于栈只能栈顶插入和删除元素;对于队列只在队尾插入元素,而且只在队头删除元素。
  • 栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底
  • 向栈中压入元素的操作是先移动栈顶指针,后存入元素
  • 从栈中弹出元素的操作是先取出元素,后移动栈顶指针
  • 一个递归算法必须包括终止条件和递归部门
  • 栈中元素的收支原则是后进先出
  • 队列的特点是先进先出
  • 将递归算法转换成非递归算法时,通常要借助的数据布局是
  • 在做进栈运算时,应先鉴别栈是否;在做退栈运算时,应先鉴别栈是否。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为n。为了增加内存空间的使用率和淘汰溢出的大概性,由两个栈共享一片一连的内存空间时,应将两栈的栈底分别设在这片内存空间的两头,这样,只有当两个栈的栈顶在达栈空间的某一位置相遇时,才产生上溢。
  • 顺序栈四要素:
    栈空的条件:s->top==-1;
    栈满的条件:s->top==最大下标-1;
    元素进栈操作:先将栈顶指针增1,然后将元素放在栈顶指针处。
    出栈操作:先将栈顶指针处的元素取出,然后将栈顶指针减1。
  • 共享栈四要素:
    栈空的条件:top1==-1 top2==‘最大下标 。
    栈满的条件:s->top==top2-1。
    元素进栈操作:进栈1的操作为:top1++;data[top1]=x;进栈2的操作为:top2–;data[top2]=x。
    出栈操作:出栈1的操作为:x=data[top1];top1–;出栈2的操作为:x=dara[top2];top2++;
  • 链栈四要素:
    栈空的条件:s->next==NULL.
    栈满的条件:由于只有内存溢出时才出现栈满,通常看作不存在栈满。
    元素进栈操作:新建一个结点存放元素(由p指向它),将结点p插入到头结点之后。
    出栈操作:取首结点的data值并将其删除。
  • 顺序队四要素:
    队空的条件:q->front== q->rear.
    队满的条件:q->rear== 数组最大下标-1.
    元素的进队操作:先将rear增1,然后将元素放在rear的位置。
    出队操作:先将front增1,然后取出front位置的元素。
  • 链队四要素:
    队空的条件:q->rear== NULL(q->front==NULL)
    队满的条件:不思量
    元素的进队操作:新建一个结点存放元素(由p指向它),将结点p插入作为尾结点,
    出队操作:取出队首结点的data值并将其删除。
  • 一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中另有空位置,这就叫**“假溢出**”
  • 循环队列的引入,目的是为了降服队列的假溢出
  • 在具有n个单位的循环队列中,队满时共有n-1 个元素。
  • 为解决计算机主机与打印机之间的速度不匹配问题,通常设计一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑布局应该是队列
  • 最适合做链式队列的链表是只带队尾指针的循环单链表
  • 栈和队列的共同点是只允许在端点处插入和删除
  • 最大容量为n的循环队列,队尾指针是rear,队头是front,则队满的条件是**(rear+1) MOD n==front**。
  • 最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是rear==front

来源:https://blog.csdn.net/ordinary_pq/article/details/111904620
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )