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

栈和队列

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