侧边栏壁纸
博主头像
buukle博主等级

布壳儿

  • 累计撰写 109 篇文章
  • 累计创建 17 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

数据结构(3) - 栈和队列

administrator
2021-03-16 / 0 评论 / 1 点赞 / 187 阅读 / 1015 字

栈和队列

1.栈的概念

限定存取规则的线性表(FILO : first in last out)

1.分类

  • 普通栈
  • 双端栈
    (两个栈公用一条内存区域,栈底分别位于存储区的两端)

2.队列的概念

限定存取规则的线性表(FIFO : first in first out)

1.分类

  • 顺序存储队列
    顺序存储队列伪满时需要改懂所有元素的位置,性能不是很好;
  • 链存储队列
    比较适合用来解决队列的问题.

3.应用

1.栈的应用-迷宫问题

应用栈存储动子的足迹,用数组标表示格局(即地图,棋盘等),这样我们就能在格局数组中对格局的点位操作状态,同时在栈中操作动子运行的轨迹,自动化试探问题的解.

2.队列的应用-舞伴问题

应用队列存储男女,先进先出的规则,搭配那女舞伴即可.

3.递归与分治

1.四项原则

  • (1) 原问题能够被分解成性质相同的规模较小的子问题;
  • (2) 子问题能直接求解;
  • (3) 所有子问题求解后,原问题能被求解;
  • (4) 子问题间不应重叠;

2.举例

  • 汉诺塔问题 hanoi
1

评论区