数据结构与算法——队列的应用

一、队列的应用

只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构
- 调度或缓冲
  - 消息缓冲器
  - 邮件缓冲器
  - 计算机硬设备之间的通信也需要队列作为数据缓冲
  - 操作系统的资源管理
- 宽度优先搜索
广度优先搜索：搜索该步的所有可能状态，再进一步考虑后面的各种情况；（队列应用）
- 树的层次遍历
深度优先搜索：沿某一状态走下去，不行再回头。（栈应用）
- 树的先序、中序、后续遍历

二、农夫过河问题

问题抽象：
- “人狼羊菜”乘船过河
- 只有人能撑船，船只有两个位置（包括人）
- 狼羊、羊菜不能在没有人时共处

数据抽象：

对每个角色的位置进行描述，农夫、狼、羊和菜，四个目标依次各用一位，目标在起始岸位置：0，目标岸：1。如 0110 表示农夫、白菜在起始岸，而狼、羊在目标岸（此状态为不安全状态）
用整数 status 表示上述四位二进制描述的状态，如整数 0x08 表示的状态 1000，整数 0x0F 表示的状态 1111
如何从上述状态中得到每个角色所在位置？

bool farmer(int status){ 
    return ((status & 0x08) != 0); 
}
bool wolf(int status){ 
    return ((status & 0x04) != 0); 
}
bool goat(int status){ 
    return ((status & 0x02) != 0); 
}
bool cabbage(int status){ 
    return ((status & 0x01) != 0); 
}

人狼羊菜状态

安全状态判断

bool safe(int status) // 返回 true:安全，false:不安全
{
    if ((goat(status) == cabbage(status)) && (goat(status) != farmer(status)))
        return(false); // 羊吃白菜
    if ((goat(status) == wolf(status)) && (goat(status) != farmer(status)))
        return(false); // 狼吃羊
    return(true); // 其它状态为安全
}

问题求解：试探法
算法抽象：问题变为从状态 0000（整数0）出发，寻找全部由安全状态构成的状态序列，以状态 1111（整数15）为最终目标。
- 状态序列中每个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。
- 序列中不能出现重复状态
算法设计
- 定义一个整数队列 moveTo，它的每个元素表示一个可以安全到达的中间状态
- 还需要定义一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径
  - 用顺序表 route 的第 i 个元素记录状态 i 是否已被访问过
  - 若 route[i] 已被访问过，则在这个顺序表元素中记入前驱状态值；-1 表示未被访问
  - route 的大小（长度）为 16

算法实现

void solve() {
    int movers, i, location, newlocation;
    vector<int> route(END+1, -1);  // 记录已考虑的状态路径
    queue<int> moveTo;
    // 准备初值
    moveTo.push(0x00);
    route[0]=0;
    while (!moveTo.empty() && route[15] == -1) {
        // 得到现在的状态
        int status = moveTo.front();
        moveTo.pop();
        for (movers = 1; movers <= 8; movers <<= 1) {
            // 农夫总是在移动，随农夫移动的也只能是在农夫同侧的东西
            if (farmer(status) == (bool)(status & movers)) {
                // 随农夫移动以后的状态
                int newstatus = status ^ (0x08 | movers);
                // 安全的，并且未考虑过的走法
                // 确保状态不能重复，重复状态没有意义，还有可能造成死循环
                if (safe(newstatus) && (route[newstatus] == -1)) {
                    route[newstatus] = status;
                    moveTo.push(newstatus); 
                }
            }
        }
    }
    // 反向打印出路径
    if (route[15] != -1) { 
        cout << "The reverse path is : " << endl;
        for (int status = 15; status >= 0; status = route[status]) {
            cout << "The status is : " << bitset<4>(status) << endl;
            if (status == 0) break;
        }
    }
    else{
        cout << "No solution." << endl;
    }
}

输出：

The reverse path is : 
The status is : 1111
The status is : 0101
The status is : 1101
The status is : 0001
The status is : 1011
The status is : 0010
The status is : 1010
The status is : 0000

总结：这个算法只能输出其中的一种解，这个问题还有另一种路径

三、另一个思考题

五人提灯过独木桥：

有一盏灯能使用 30 秒，要在灯灭前过这座独木桥
一家五口人，每人过桥的速度不同：哥哥 1 秒，弟弟 3 秒，爸爸 6 秒，妈妈 8 秒，奶奶 12 秒
每次只能过 2 个人，而且天黑，过桥时必须有灯照明

一、队列的应用#

二、农夫过河问题#

三、另一个思考题#

一、队列的应用

二、农夫过河问题

三、另一个思考题