數據結構中棧在過河問題中的應用

李橙　李海燕　丁國棟

摘要：棧是數據結構中的一種基本而重要的存儲結構。棧是一種限定僅在一段進行插入與刪除操作的線性表，插入或刪除是限定在表尾進行的，我們通常將表尾稱之為棧頂。相反的，將表頭端稱之為棧底。在棧中，先插入的元素被壓在棧底，最后才能出棧，所以棧也被稱為后進先出表。因而，實際應用中，凡是符合后進先出的問題，我們都可以用堆棧來處理和實現。棧的典型應用包括：遞歸函數的調用，進制轉換，括號比配問題，背包問題，中綴表達式求值等等。過河問題是一個非常經典的智力問題，很多競賽中都使用過這個題材，該文中我們將討論棧對于過河問題的應用。

關鍵詞：棧；數據結構；計算機編程；過河問題

中圖分類號：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個人順利過河。……