09 栈与递归

知识结构：

栈是我们经常使用的一种数据结构，比如，手枪发射子弹的顺序与子弹压入弹夹的顺序是相反，即后压入弹夹的子弹先发射出来。又比如，我们使用的Word、Excel、Photoshop等软件系统中的撤销操作，也是栈的具体应用，最后做的操作，一定是最先撤销的。

下面我们就来详细介绍“栈”这种数据结构。

1. 栈的定义与操作

1.1 栈的定义

插入（入栈）和删除（出栈）操作只能在一端（栈顶）进行的线性表。即先进后出（First In Last Out）的线性表。

例1 ：线性表$(a_0,a_1,⋯,a_{n-1)}$进栈与出栈演示。

1.2 栈的操作

• 入栈操作：将数据元素插入栈顶。
• 出栈操作：移除栈顶的数据元素。
• 是否为空：判断栈中是否包含数据元素。
• 得到栈深：获取栈中实际包含数据元素的个数。
• 清空操作：移除栈中的所有数据元素。
• 获取栈顶元素。

using System;namespace LinearStruct
{/// <summary>/// 栈的抽象数据类型/// </summary>/// <typeparam name="T">栈中元素的类型</typeparam>public interface IStack<T> where T : IComparable<T>{/// <summary>/// 获取栈中实际包含元素的个数/// </summary>int Length { get; }/// <summary>/// 获取栈顶元素/// </summary>T StackTop { get; }/// <summary>/// 数据元素入栈/// </summary>/// <param name="data">要入栈的元素</param>void Push(T data);/// <summary>/// 数据元素出栈/// </summary>void Pop();/// <summary>/// 判断栈中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>bool IsEmpty();/// <summary>/// 从栈中移除所有元素/// </summary>void Clear();}
}

2. 栈的顺序存储（顺序栈）

顺序栈：利用顺序表实现的栈。

实现：

using System;namespace LinearStruct
{/// <summary>/// 用顺序存储结构实现的栈/// </summary>/// <typeparam name="T">顺序栈中元素的类型</typeparam>public class SeqStack<T> : IStack<T> where T : IComparable<T>{private readonly SeqList<T> _lst;/// <summary>/// 初始化SeqStack类的新实例/// </summary>/// <param name="max">SeqStack中最多包含元素的个数</param>public SeqStack(int max){if (max <= 0)throw new ArgumentOutOfRangeException();_lst = new SeqList<T>(max);}/// <summary>/// 获取SeqStack中实际包含元素的个数/// </summary>public int Length{get { return _lst.Length; }}/// <summary>/// 获取SeqStack中最多包含元素的个数/// </summary>public int MaxSize{get { return _lst.MaxSize; }}/// <summary>/// 获取SeqStack中的栈顶元素/// </summary>public T StackTop{get{if (_lst.IsEmpty())throw new Exception("栈为空.");return _lst[0];}}/// <summary>/// 数据元素入栈/// </summary>/// <param name="data">要入栈的元素</param>public void Push(T data){if (_lst.Length == _lst.MaxSize)throw new Exception("栈已达到最大容量.");_lst.Insert(0, data);}/// <summary>/// 数据元素出栈/// </summary>public void Pop(){if (_lst.IsEmpty())throw new Exception("栈为空.");_lst.Remove(0);}/// <summary>/// 判断SeqStack中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return _lst.IsEmpty();}/// <summary>/// 从SeqStack中移除所有元素/// </summary>public void Clear(){_lst.Clear();}}
}

应用：

using System;
using LinearStruct;namespace ExampleStack
{class Program{static void Main(string[] args){StackTest(new SeqStack<string>(20));}private static void StackTest(IStack<string> stack){stack.Push("a1");stack.Push("a2");stack.Push("a3");while (stack.IsEmpty() == false){Console.WriteLine(stack.StackTop);stack.Pop();}// a3// a2// a1}}
}

SeqStack<T>虽然实现了IStack<T>接口，但在入栈和出栈时，会移动大量的元素，效率比较低。故把入栈和出栈放到顺序表的尾部进行，这样可以提升效率。

• 入栈：Insert(Length, data)
• 出栈：Remove(Length - 1)
• 栈顶元素：SeqList[Length - 1]

using System;namespace LinearStruct
{/// <summary>/// 用顺序存储结构实现的栈/// </summary>/// <typeparam name="T">顺序栈中元素的类型</typeparam>public class SeqStack_1<T> : IStack<T> where T : IComparable<T>{private readonly SeqList<T> _lst;/// <summary>/// 初始化SeqStack类的新实例/// </summary>/// <param name="max">SeqStack中最多包含元素的个数</param>public SeqStack_1(int max){if (max <= 0)throw new ArgumentOutOfRangeException();_lst = new SeqList<T>(max);}/// <summary>/// 获取SeqStack中实际包含元素的个数/// </summary>public int Length{get { return _lst.Length; }}/// <summary>/// 获取SeqStack中最多包含元素的个数/// </summary>public int MaxSize{get { return _lst.MaxSize; }}/// <summary>/// 获取SeqStack中的栈顶元素/// </summary>public T StackTop{get{if (_lst.IsEmpty())throw new Exception("栈为空.");return _lst[Length - 1];}}/// <summary>/// 数据元素入栈/// </summary>/// <param name="data">要入栈的元素</param>public void Push(T data){if (_lst.Length == _lst.MaxSize)throw new Exception("栈已达到最大容量.");_lst.Insert(Length, data);}/// <summary>/// 数据元素出栈/// </summary>public void Pop(){if (_lst.IsEmpty())throw new Exception("栈为空.");_lst.Remove(Length - 1);}/// <summary>/// 判断SeqStack中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return _lst.IsEmpty();}/// <summary>/// 从SeqStack中移除所有元素/// </summary>public void Clear(){_lst.Clear();}}
}

应用：

using System;
using LinearStruct;namespace ExampleStack
{class Program{static void Main(string[] args){StackTest(new SeqStack_1<string>(20));}private static void StackTest(IStack<string> stack){stack.Push("a1");stack.Push("a2");stack.Push("a3");while (stack.IsEmpty() == false){Console.WriteLine(stack.StackTop);stack.Pop();}// a3// a2// a1}}
}

3. 栈的链式存储（链栈）

链栈：利用单链表实现的栈。

实现：

using System;namespace LinearStruct
{/// <summary>/// 用链式存储结构实现的栈/// </summary>/// <typeparam name="T">栈中元素的类型</typeparam>public class LinkStack<T> : IStack<T> where T : IComparable<T>{private readonly SLinkList<T> _lst;/// <summary>/// 初始化LinkStack类的新实例/// </summary>public LinkStack(){_lst = new SLinkList<T>();}/// <summary>/// 获取LinkStack中实际包含元素的个数/// </summary>public int Length{get { return _lst.Length; }}/// <summary>/// 获取LinkStack中的栈顶元素/// </summary>public T StackTop{get{if (_lst.Length == 0)throw new Exception("栈为空.");return _lst[0];}}/// <summary>/// 数据元素入栈/// </summary>/// <param name="data">要入栈的元素</param>public void Push(T data){_lst.InsertAtFirst(data);}/// <summary>/// 数据元素出栈/// </summary>public void Pop(){if (_lst.Length == 0)throw new Exception("栈为空.");_lst.Remove(0);}/// <summary>/// 判断LinkStack中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return _lst.IsEmpty();}/// <summary>/// 从LinkStack中移除所有元素/// </summary>public void Clear(){_lst.Clear();}}
}

应用：

using System;
using LinearStruct;namespace ExampleStack
{class Program{static void Main(string[] args){StackTest(new LinkStack<string>());}private static void StackTest(IStack<string> stack){stack.Push("a1");stack.Push("a2");stack.Push("a3");while (stack.IsEmpty() == false){Console.WriteLine(stack.StackTop);stack.Pop();}// a3// a2// a1}}
}

4. 栈的应用

4.1 问题描述

假设一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1至n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1至n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图1（a）给出一个转轨站，其中有k个（k=3）缓冲铁轨H1，H2和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至n的次序离开转轨站（通过出轨处）。在图1（a）中，n=9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图1（b）给出了按所要求的次序重新排列后的结果。

4.2 问题分析

现在分析图1，为了重排车厢，需从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。缓冲铁轨上车厢的进和出只能在缓冲铁轨的尾部进行。在重排车厢过程中，仅允许以下移动：

1、车厢可以从入轨移动到一个缓冲铁轨的尾部或进入出轨接在重排的列车后。

2、车厢可以从一个缓冲铁轨的尾部移动到出轨接在重排的列车后。

考察图1（a），3号车厢在入轨的前部，但由于它必须位于1号和2号车厢的后面，因此不能立即输出3号车厢，可把3号车厢送入缓冲铁轨H1。下一节车厢是6号车厢，也必须送入缓冲铁轨。如果把6号车厢送入H1，那么重排过程将无法完成，因为3号车厢位于6号车厢的后面，而按照重排的要求，3号车厢必须在6号车厢之前输出。因此可把6号车厢送入H2。下一节车厢是9号车厢，被送入H3，因为如果把它送入H1或H2，重排过程也将无法完成。至此，缓冲铁轨的当前状态如图2（a）所示。

接下来处理2号车厢，它可以被送入任一个缓冲铁轨，因为它能满足缓冲铁轨上车厢编号必须递增排列的要求，不过，应优先把2号车厢送入H1，因为如果把它送入H3，将没有空间来移动7号车厢和8号车厢。如果把2号车厢送入H2，那么接下来的4号车厢必须被送入H3，这样将无法移动后面的5号、7号和8号车厢。新的车厢u应送入这样的缓冲铁轨：其底部的车厢编号v满足v > u，且v是所有满足这种条件的缓冲轨顶部车厢编号中最小的一个编号。只有这样才能使后续的车厢重排所受到的限制最小。

接下来处理4号车厢时，三个缓冲铁轨顶部的车厢分别为2号、6号和9号车厢。根据分配规则，4号车厢应送入H2。这之后，7号车厢被送入H3。图2（b）给出了当前的状态。

接下来，1号车厢被送至出轨，这时，可以把H1中的2号车厢送至出轨。之后，从H1输出3号车厢， 输出4号车厢。至此，没有可以立即输出的车厢了。接下来的8号车厢被送入H1，然后5号车厢从入轨处直接输出到出轨处。这之后，从H2输出6号车厢，从H3输出7号车厢，从H1输出8号车厢，最后从H3输出9号车厢。

到此为止，整个“入轨，出轨”完毕！让我们整理一下算法思路：

• 第一步：若需出轨的编号恰是入轨编号，则直接出轨。
• 第二步：若需出轨的编号恰是缓冲轨的最小编号，则直接出轨。
• 第三步：将入轨编号放入缓冲轨。（规则：放到满足小于缓冲轨栈顶元素编号且栈顶元素最小的上面。）

4.3 参考代码

using System;
using LinearStruct;namespace TrainArrange
{class Program{/// <summary>/// 车厢重排算法/// </summary>/// <param name="p">入轨序列</param>/// <param name="k">缓冲轨条数</param>/// <returns>重排是否成功</returns>static bool RailRoad(int[] p, int k){LinkStack<int>[] h = new LinkStack<int>[k];for (int i = 0; i < h.Length; i++)h[i] = new LinkStack<int>();int nowOut = 1; //下一次要输出的车厢号int minH = int.MaxValue; //缓冲铁轨中编号最小的车厢int minS = -1; //minH号车厢对应的缓冲铁轨for (int i = 0; i < p.Length; i++){if (p[i] == nowOut){Console.WriteLine("移动车厢：{0}从入轨到出轨。", p[i]);nowOut++;//从缓冲铁轨中输出while (minH == nowOut){Output(ref minH, ref minS, h); //出轨nowOut++;}}else{//将p[i]送入某个缓冲铁轨if (Input(p[i], ref minH, ref minS, h) == false){return false;}}}return true;}/// <summary>/// 从缓冲轨移除车厢出轨/// </summary>/// <param name="minH">缓冲铁轨中编号最小的车厢</param>/// <param name="minS">minH号车厢对应的缓冲铁轨</param>/// <param name="h">缓冲轨道的集合</param>static void Output(ref int minH, ref int minS, LinkStack<int>[] h){h[minS].Pop(); //从堆栈minS中删除编号最小的车厢minHConsole.WriteLine("移动车厢：{0}从缓冲轨{1}到出轨。", minH, minS);//通过检查所有的栈顶，搜索新的minH和minSminH = int.MaxValue;minS = -1;for (int i = 0; i < h.Length; i++){if (h[i].IsEmpty() == false && h[i].StackTop < minH){minH = h[i].StackTop;minS = i;}}}/// <summary>/// 在一个缓冲铁轨中放入车厢c/// </summary>/// <param name="c">放入车厢编号</param>/// <param name="minH">栈顶编号的最小值</param>/// <param name="minS">栈顶编号最小值所在堆栈的编号</param>/// <param name="h">缓冲轨道的集合</param>/// <returns>如果没有可用的缓冲铁轨，则返回false，否则返回true。</returns>static bool Input(int c, ref int minH, ref int minS, LinkStack<int>[] h){int bestTrack = -1; //目前最优的铁轨int bestTop = int.MaxValue; //最优铁轨上的头辆车厢for (int i = 0; i < h.Length; i++){if (h[i].IsEmpty() == false){int x = h[i].StackTop;if (c < x && x < bestTop){bestTop = x;bestTrack = i;}}else{if (bestTrack == -1){bestTrack = i;break;}}}if (bestTrack == -1)return false;h[bestTrack].Push(c);Console.WriteLine("移动车厢：{0}从入轨到缓冲轨{1}。", c, bestTrack);if (c < minH){minH = c;minS = bestTrack;}return true;}static void Main(string[] args){int[] p = new int[] { 3, 6, 9, 2, 4, 7, 1, 8, 5 };int k = 3;bool result = RailRoad(p, k);do{if (result == false){Console.WriteLine("需要更多的缓冲轨道,请输入需要添加的数量:");k = k + Convert.ToInt32(Console.ReadLine());result = RailRoad(p, k);}} while (result == false);}}
}

4.4 输出结果

5. 递归

如果一个函数在内部调用自身本身，这个函数就是递归函数。

【例1】：求n的阶乘

n! = 1 x 2 x 3 x ... x n

循环：

static int factorial(int n)
{if (n < 1)throw new ArgumentOutOfRangeException();int result = n;for (int i = 1; i < n; i++){result *= i;}return result;
}static void Main(string[] args)
{Console.WriteLine(factorial(5));//120
}

递归：

static int factorial(int n)
{if (n < 1)throw new ArgumentOutOfRangeException();if (n == 1)return 1;return n * factorial(n - 1);
}static void Main(string[] args)
{Console.WriteLine(factorial(5));//120
}

【例2】：斐波那契数列

f(n)=f(n-1)+f(n-2), f(0)=0 f(1)=1

循环：

static int[] recur_fibo(int n)
{if (n < 2)throw new ArgumentOutOfRangeException();int[] result = new int[n];result[0]= 0;result[1] = 1;for (int i = 2; i < n; i++){result[i] = result[i - 1] + result[i - 2];}return result;
}static void Main(string[] args)
{int[] r = recur_fibo(11);for (int i = 0; i < r.Length; i++){Console.Write(r[i]+" ");}Console.WriteLine();// 0 1 1 2 3 5 8 13 21 34 55
}

递归：

static int recur_fibo(int n)
{if (n <= 1)return n;return recur_fibo(n - 1) + recur_fibo(n - 2);
}static void Main(string[] args)
{int[] result = new int[11];for (int i = 0; i < result.Length; i++){result[i] = recur_fibo(i);Console.Write(result[i] + " ");}Console.WriteLine();// 0 1 1 2 3 5 8 13 21 34 55
}

【例3】：汉诺塔问题

汉诺塔问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

如果我们要思考每一步怎么移可能会非常复杂，但是可以将问题简化。

我们可以先假设除 a 柱最下面的盘子之外，已经成功地将 a 柱上面的 63个盘子移到了 b 柱，这时我们只要再将最下面的盘子由 a 柱移动到 c 柱即可。

当我们将最大的盘子由 a 柱移到 c 柱后，b 柱上便是余下的 63 个盘子，a 柱为空。因此现在的目标就变成了将这 63 个盘子由 b 柱移到 c 柱。这个问题和原来的问题完全一样，只是由 a 柱换为了 b 柱，规模由 64 变为了 63。因此可以采用相同的方法，先将上面的 62 个盘子由 b 柱移到 a 柱，再将最下面的盘子移到 c 柱。

以此内推，再以 b 柱为缓冲，将 a 柱上面的 62 个圆盘最上面的 61 个圆盘移动到 b 柱，并将最后一块圆盘移到 c 柱。

我们已经发现规律，我们每次都是以 a 或 b 中一根柱子为缓冲，然后先将除了最下面的圆盘之外的其它圆盘移动到辅助柱子上，再将最底下的圆盘移到 c 柱子上，不断重复此过程。

这个反复移动圆盘的过程就是递归，例如我们每次想解决 n 个圆盘的移动问题，就要先解决（n-1）个盘子进行同样操作的问题。

于是可以编写一个函数，move(n, a, b, c)。可以这样理解：move(盘子数量, 起点, 缓冲, 终点)。

1. a 上只有一个盘子的情况，直接搬到 c，代码如下:

if(n == 1)Console.WriteLine(a, '-->', c)

2. a 上不止有一个盘子的情况:

首先，需要把 n-1 个盘子搬到 b 柱子缓冲。打印出的效果是：a --> b。

move(n - 1, a, c, b)

再把最大的盘子搬到 c 柱子，也是最大尺寸的一个。打印出：a–>c。

move(1, a, b, c)

最后，把剩下 b 柱的 n-1 个盘子搬到 c 上，此时缓冲变成了起点，起点变成了缓冲。

move(n - 1, b, a, c)

利用 C# 实现汉诺塔问题

class Program
{private static int i = 0;static void Move(int n, string a, string b, string c){if (n == 1){Console.WriteLine("移动第 {0} 次 {1}-->{2}", ++i, a, c);return;}Move(n - 1, a, c, b);Move(1, a, b, c);Move(n - 1, b, a, c);}static void Main(string[] args){Move(3, "a", "b", "c");}
}
// 移动第 1 次 a --> c
// 移动第 2 次 a --> b
// 移动第 3 次 c --> b
// 移动第 4 次 a --> c
// 移动第 5 次 b --> a
// 移动第 6 次 b --> c
// 移动第 7 次 a --> c

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：