数据结构中栈在过河问题中的应用

　　摘要：栈是数据结构中的一种基本而重要的存储结构。栈是一种限定仅在一段进行插入与删除操作的线性表，插入或删除是限定在表尾进行的，我们通常将表尾称之为栈顶。相反的，将表头端称之为栈底。在栈中，先插入的元素被压在栈底，最后才能出栈，所以栈也被称为后进先出表。因而，实际应用中，凡是符合后进先出的问题，我们都可以用堆栈来处理和实现。栈的典型应用包括：递归函数的调用，进制转换，括号比配问题，背包问题，中缀表达式求值等等。过河问题是一个非常经典的智力问题，很多竞赛中都使用过这个题材，该文中我们将讨论栈对于过河问题的应用。

 

　　关键词：栈；数据结构；计算机编程；过河问题

 

　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）31-7279-03

 

　　Abstract： Stack is a basic and important storage of data structure. Stack is a limit for the insert table of linear and delete operations in only one paragraph， insert or delete is defined in the rear， we usually set the table tail call stack top. On the contrary， the header end called the bottom of stack. On the stack， first insert the element is pressed on the bottom of the stack， and finally to the stack， so the stack is also called the LIFO list.Therefore， in practical application， in line with all the LIFO problem， we can be used to deal with the stack and the implementation. Including the typical application stack： a recursive function calls， hexadecimal conversion，parentheses matching problem， knapsack problem， infix expression etc..Crossiong river is a very classic intellectual problem， lots of competition use this subject， in this paper， we will discuss the application stack for acrossing river problem.

 

　　Key words： stack；data structure； computer programming；crossing river problem

 

　　1 问题描述与分析

 

　　问题描述如下：M个坏人，N个好人过河，只有1条船，这条船每次只能至多只能载2个人过河（包括开船的），船开过了河还要有一个人把船开回来。在船的两岸坏人数量不能多于好人，否则坏人会欺负好人。要怎样将3个好人和3个坏人平安送达对岸。

 

　　问题分析：在此，我们假定共有3个坏人3个好人（M=3、N=3），原本这6个人在左岸，要到右岸去，对问题进行具体分析。由于船上只能一次载2个人，因而每次过河共有5种方案供选择：1个坏人一个好人；两个坏人；两个好人；一个坏人；一个好人。我们可以使用试探法，用这5种方案轮流进行过河流程，并计算两岸剩下的好人与坏人人数，如果符合规定，就保留这个方案，否则尝试其他方案，直到6个人顺利过河。

 

　　2 核心算法思想

 

　　在此我们定义结构体包含4个成员：好人个数，坏人个数，船的状态（左岸、右岸），以及已经尝试的乘船方案（共5种方案）。轮流尝试5种过河方案，使用堆栈保存正确的方案步骤，同时计算两岸好人与坏人个数，如果不符合坏人不多于好人的规则，则弹出栈中已经保存的方案步骤，否则如果符合坏人不多于好人的规则，则继续尝试方案寻找下一过河方案。如此反复一直到6个人正确到达右岸。