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

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