数据结构-栈和队列的应用

前言

本篇文章使用两个例子说明栈和队列的应用，
对于迷宫问题，使用栈实现深度优先策略解决迷宫问题；
对于农夫过河问题，使用队列实现广度优先策略解决农夫过河问题。

一、栈的应用（迷宫问题）

1.1 问题描述

从入口进入迷宫，如何可以尽快找到迷宫的出口？这是一个十分有趣的经典游戏。
迷宫可用如图1.1所示的方块表示，其中每个元素或为通道（以空白方块表示），或为墙（以带阴影的方块表示）。迷宫问题要求的是：从入口到出口的一个以空白方块构成的（无环路径）。

图1.1 迷宫的图形表示

1.2 算法选择

求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续往前走；否则沿原路返回，换一方向再进行探索，直到找到了一个出口，或者所有可能的探索都以失败而告终。这类探索方法统称为回溯法，也可以称为深度优先探索方法。实现深度优先探索的工具是栈。
其算法的基本框架如下：

mazeFrame(void)
{创建一个（保存探索过程）空栈；把入口位置压入栈中；while(栈不为空){取栈顶位置并设置为当前位置；while(当前位置存在试探的可能性){取下一试探位置；if(下一位置是出口)打印栈中保存的探索过程然后返回；if(下一位置是通道)把下一位置进栈并且设置为当前位置；}}	
}

1.3 算法精化

在求解程序中，迷宫可用二维数组maze[m][n]表示，其中数组中元素是0表示通道，1表示墙。
入口坐标为(1,1)
出口坐标为(6,9)

图1.2 迷宫的二维数组表示

为了细化前面的框架，还要考虑试探方向的表示
假设某时刻所在迷宫的位置坐标为(i,j)，相邻的四个位置分别标E、S、W、N表示东、南、西、北方向；
为了简化算法，可以建立一个数组direction，这个数组给出了相对于位置(i,j)的4个方向上,i和j的增量值
使用一个变量elem_d表示试探方向，
0-表示方向E
1-表示方向S
2-表示方向W
3-表示方向N
则某个方向的试探位置i和j的变化值为

new_i = i + direction[elem_d][0] （新的行坐标）
new_j = j + direction[elem_d][1] （新的列坐标）例如,当位置坐标为(3,4)时
elem_d = 0 表示试探方向为E
则试探坐标为
new_i = i + direction[0][0] = 3 + 0 = 3
new_j = j + direction[0][1] = 4 + 1  = 5
则新坐标为(3,5)

图1.3 迷宫中方向的表示

另外，为了避免走到已经试探过的位置（包括现在探索路径上的和曾经在探索路径上的位置），凡是已经探索过的位置都应该做上标记。根据约定，值为1表示墙，0表示通道，那么，凡是探索过的位置可以赋予一个既非0又非1的值，假设取值为2（这样做可以节省空间，缺点是破坏了maze数组的状态；否则要设置一个与迷宫那样大小的数组来保存标记）。一旦将某一位置(i,j)纳入到当前路径中，就将maze[i][j]设置为2。为了记录探索路径中当前位置以及在该位置上的试探方向，算法设置了一个栈，栈中元素包括三项，分别记录当前位置的行坐标、列坐标和以及在该位置上的试探方向。

//栈数据元素类型
struct ElemType {int x;			//行坐标int y;			//列坐标int direction;	//试探方向
};

1.4 算法实现

经过上述设计，求迷宫中一条路径上的算法可以从入口开始，对每个当前位置都从E方向(elem_d = 0)开始试探，若不能通过，则顺时针依次试探S方向、W方向和N方向。当选定一个可以前进的位置，要把当前所在的位置纳入探索路径中，并将当前所在位置以及试探方向记录下来，以便走不通时可以顺序原路一步步回退，每退一步以后接着试探在该位置上的其他未试探过的方向，如此循环，直到找到出口。

/*
int(*maze)[11] 数组指针类型，表示传入迷宫数组
int(*direction)[2] 数组指针类型，表示传入direction数组
int entrance_x  入口行坐标
int entrance_y  入口列坐标
int eixt_x		出口行坐标
int exit_y 		出口纵坐标
*/
void mazePath(int (*maze)[11], int(*direction)[2], int entrance_x, int entrance_y, int exit_x, int exit_y)
{int elem_x = 0;int elem_y = 0;int elem_d = 0;int newDirection_x = 0;int newDirection_y = 0;//初始化栈SeqStack stack = { 0 };initSeqStack(&stack);//初始化入口坐标元素SElemType element = { 0 };maze[entrance_x][entrance_y] = 2; //从入口开始标记element.x = entrance_x;			 element.y = entrance_y;element.direction = -1;		     //未试探任何方向if (!pushSeqStack(&stack, element))	 //将入口点进栈{destroySeqStack(&stack);return;}while (!isEmptySeqStack(&stack))   //走不通时，一步步回退{if (!popSeqStack(&stack, &element))  //获取栈顶元素并出栈{destroySeqStack(&stack);return;}elem_x = element.x;elem_y = element.y;elem_d = element.direction+1;while (elem_d <= 3)  //一次试探一个方向{newDirection_x = elem_x + direction[elem_d][0];newDirection_y = elem_y + direction[elem_d][1];if (newDirection_x == exit_x && newDirection_y == exit_y && maze[newDirection_x][newDirection_y] == 0)//走到出口{element.x = elem_x;element.y = elem_y;element.direction = elem_d;if (!pushSeqStack(&stack, element)){destroySeqStack(&stack);return;}element.x = newDirection_x;element.y = newDirection_y;element.direction = 4;if (!pushSeqStack(&stack, element)){destroySeqStack(&stack);return;}printf("The revers path is:\n"); //打印路径while (!isEmptySeqStack(&stack)){if (!popSeqStack(&stack, &element)){destroySeqStack(&stack);return;}printf("The node is: (%d %d)\n", element.x, element.y);}//销毁栈destroySeqStack(&stack);return;}if (maze[newDirection_x][newDirection_y] == 0) //走到没走过的点{maze[newDirection_x][newDirection_y] = 2;   //标记走过的点element.x = elem_x;element.y = elem_y;element.direction = elem_d;if (!pushSeqStack(&stack, element))  //进栈{destroySeqStack(&stack);return;}elem_x = newDirection_x;  //下一点转换成当前点elem_y = newDirection_y;elem_d = -1;}elem_d++;}}printf("The path has not been found!\n");//销毁栈destroySeqStack(&stack);
}

注意： 顺序栈的代码已经省略

1.5 问题结果

二、队列的应用（农夫过河问题）

2.1 问题描述

一个农夫带着一只狼、一只羊和一颗白菜，身处河的南岸。农夫要把这些东西全部运到河的北岸。问题是农夫只有一条小船，船小到只能容下农夫和一件物品，当然，船只有农夫能撑。另外，因为狼能吃羊，而羊能吃白菜，所以，农夫不能留下羊和狼或者羊和白菜单独在河一边，自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案，才能将所有的东西安全运过河呢？

2.2 算法选择

求解这个问题的最简单的方法是逐步进行试探。每一步都在前一步选择基础上搜素下一步的所有可能的状态。用计算机实现上述系统搜索过程，可以采用两种不同的策略，一种是广度优先搜索（breadth first）；另一种是深度优先搜索(depth first)。实现广度优先搜索的工具是队列；实现深度优先搜索的工具是栈。本节讨论队列的应用，所以重点介绍广度优先搜索策略。
广度优先搜索的思想就是，在搜索过程中，总是首先搜索下面一步的所有可能情况，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构，把每一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，在处理中又再把下一步的情况全部放在队列里。由于队列的操作原则是先进先出，所以，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。
以遍历二叉树为例，使用广度优先搜索策略，进行层序遍历。

图2.1 广度优先遍历二叉树

2.3 算法精化

要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的方法是用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如，用0表示农夫或某物品在河的南岸，1表示在河的北岸。因此，整数5（其二进制表示为0101）表示农夫和白菜在河的南岸，而狼和羊在北岸。这时，农夫不在，因此狼会把羊吃掉，所以是一种不安全的状态。问题的初始状态是整数0（其二进制为0000）；而问题的终结状态是整数15（其二进制表示为1111）。

图2.2 二进制位置表示图

用整数location表示用上述方法描述的状态，可以用下面的4个函数从上述状态得到每个角色所在位置的代码。函数返回值为真（1）表示农夫或物品的位置在河的北岸，否则在南岸。

//农夫过河问题
//个体判断函数
/*	四位二进制数分别表示农夫，狼，白菜，羊的位置0 表示在南岸  1 表示在北岸初始状态 location = 0000（二进制） 表示农夫，狼，白菜，羊都位于河的南岸使用按位 & 操作，取出每个位置的信息，例如 location & 0x08 取出农夫的位置信息
*///取出农夫位置信息
int farmer(int location)
{return (0 != (location & 0x08));
}//取出狼位置信息
int wolf(int location)
{return (0 != (location & 0x04));
}//取出白菜位置信息
int cabbage(int location)
{return (0 != (location & 0x02));
}//取出羊位置信息
int goat(int location)
{return (0 != (location & 0x01));
}

此外，还应该分析问题中的所有角色构成的状态，确定其中那些状态是安全的，哪些是不安全的。因为，单独留下白菜和羊或单独留下狼和羊在某一岸是不安全的，所以安全状态的判断可以使用下面的函数实现。

//安全状态的判断函数
/*不能单独留下狼和羊，例如 location = 0101 是一种不安全的状态不能单独留下白菜和羊，例如 location = 1100 是一种不安全的转态安全返回 1不安全返回 0
*/int safe(int location)
{//判断羊和白菜是否单独if ((goat(location) == cabbage(location)) && (farmer(location) != goat(location))){return 0;}//判断狼和羊是否单独if ((wolf(location) == goat(location)) && (farmer(location) != goat(location))){return 0;}return 1;   //其他状态安全
}

2.4 算法实现

完成了上面的准备工作后，现在的问题变成：从初始状态二进制0000出发，寻找一种全部由安全状态构成的、能够实现的状态变迁序列（序列中的每状态都可以从前一状态通过农夫带东西划船过河到达），到达最终状态二进制1111.为避免不必要的重复，在序列中不应该出现重复的状态。
根据广度优先搜索的思想，算法中需要使用一个整数队列moveTo，把搜索过程中每一步所有可能到达的状态都保存起来。队列中的每个元素表示可以安全到达的中间状态。
另外，使用一个整数数组rooute记录已被访问过的各个状态，以及已被发现的能够到达这些状态的前驱状态。由于在这个问题中需要列举的所有状态（二进制0000~1111）一共16种，所以route数组只需要使用16个元素。route的每个元素初始化为-1，每当在队列中加入一个新的状态时，就把route中以该状态作下标的元素的值改为达到这个状态的前一转态的下标值。所以数组的第i个元素不仅记录了状态i是否已经被访问过，同时对于以及被访问过的状态，还保存了这个状态的前驱状态下标。算法结束后，可以利用route数组元素的值生成一个正确的路径。

图2.3 route数组

代码实现如下：

//农夫问题求解/*从初始状态二进制0000出发，寻找一种全部由安全状态构成、能够实现的状态变迁序列（序列中的每个状态都可以从前一状态通过农夫带东西划船过河到达）到达最终的状态1111。为避免不必要的重复，在序列中不应该出现重复的状态整数队列moveTo：把搜索过程中每一步所有可能到达的状态都保存起来。队列中的每个元素表示可以安全到达的中间状态整数数组route：用于记录已被访问过的各个状态，以及已被发现的能够到达这些状态的前驱状态由于在这个问题中需要列举的状态（二进制0000~1111）一共16种，则数组长度大小为16每个数组的元素值初始化为-1每当在队列中加入一个新的状态时，就把route中以该状态做下标的元素的值改为达到这个状态的下标值数组的第i个元素不仅记录状态i是否已被访问过，同时对于已被访问过的状态，还保存了这个状态的前驱状态算法结束后，可以利用route数组元素的值生成一个正确的状态路径
*/void farmerProblem()
{int movers, location, newlocation;int route[16];				//用于记录已考虑的状态路径struct SeqQueue moveTo;		//用于记录可以安全到达的中间状态initSeqQueue(&moveTo);		//初始化队列enSeqQueue(&moveTo, 0x00);	//初始状态二进制0000入队for (int i = 0; i < 16; i++)//初始化数组route{route[i] = -1;}route[0] = 0;while (!isEmptySeqQueue(&moveTo) && (route[15] == -1)){getQElemSeqQueue(&moveTo, &location);	//取出队头状态为当前状态QElemType e;deSeqQueue(&moveTo, &e);//循环值依次表示羊、白菜、狼、农夫的移动情况//movers的值用二进制表示依次为0001(羊)、0010(白菜)、0100(狼)、1000(农夫)for (movers = 1; movers <= 8; movers <<= 1){if ((0 != (location & 0x08)) == (0 != (location & movers))) //农夫与移动的物品在同一岸{// 0x08 | movers 得到的结果表明农夫或物品应该在船上，物品无法单独过河// location ^ (0x08 | movers) 把坐船过河的农夫与物品的状态翻转newlocation = location ^ (0x08 | movers);			//计算新状态if (safe(newlocation) && route[newlocation] == -1)	//新状态安全且未处理{route[newlocation] = location;					//记录旧状态且作为新状态的前驱enSeqQueue(&moveTo, newlocation);				//将新状态入队}}}}if (route[15] != -1){printf("The reverse path is :\n");for (location = 15; location >= 0; location = route[location]){printf("The location is : %d\n", location);if (location == 0){exit(0);}}}else{printf("No solution\n");}
}

注意：这里实现队列的代码已省略，感兴趣可查看文章：https://blog.csdn.net/pyc68/article/details/145093486?spm=1001.2014.3001.5501

算法开始时，把初始状态为0（表明人和物都在南岸）放入队列中。while循环时，只要队列不为空便取出队头元素，for循环用于列举所有可以移动的角色（包括农夫本身，用movers表示），for循环的增量表达式里使用了左移位操作，循环值依次为1、2、4、8，分别表示羊、白菜、狼和农夫的移动情况。由于在每一次移动时，农夫都必须改变状态，所以只有农夫与被移动的东西在同一岸时，农夫才可以将其带走。当然，农夫可以什么都不带，单独过河。将变量movers与二进制0x08进行按位异或运算，所得结果为1，表明相应的农夫或物品应该在船上，再将原有状态与这个结果进行一次按位异或运算，得到移动后的一个新状态。最后检验新状态是否安全，是否未被处理过。如果成立，就确认这个状态转换可行（把这个状态放入队列中，并且修改route数组的值）

2.5 问题结果

图2.4标出了送入队列的各个状态（位置）和广度优先搜索的顺序编号。
通过图2.4得出一条从0000到达1111的路径：
0000-1001：农夫把羊从南岸带到北岸
1001-0001：农夫独自从北岸回到南岸
0001-1011：农夫把白菜从南岸带到北岸
1011-0010：农夫把羊从北岸带回南岸
0010-1110：农夫把狼从南岸带到北岸
1110-0110：农夫独自从北岸回到南岸
0110-1111：农夫把羊从南岸带到北岸

图2.4 广度优先搜索的结果和顺序图

总结

迷宫问题完整代码: https://gitee.com/PYSpring/data-structure/tree/master/maze_code
农夫过河问题完整代码：https://gitee.com/PYSpring/data-structure/tree/master/queue_code