数据结构与算法：09 栈与递归

程序员文章站 2022-05-26 16:15:15

...

09 栈

知识结构：

数据结构与算法：09 栈与递归

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

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

1. 栈的定义与操作

1.1 栈的定义

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

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

数据结构与算法：09 栈与递归

1.2 栈的操作

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

数据结构与算法：09 栈与递归

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. 栈的顺序存储（顺序栈）

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

实现：

数据结构与算法：09 栈与递归

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>接口，但在入栈和出栈时，会移动大量的元素，效率比较低。故把入栈和出栈放到顺序表的尾部进行，这样可以提升效率。

数据结构与算法：09 栈与递归

入栈：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. 栈的链式存储（链栈）

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

实现：

数据结构与算法：09 栈与递归

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）给出了按所要求的次序重新排列后的结果。

数据结构与算法：09 栈与递归

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）所示。

数据结构与算法：09 栈与递归

接下来处理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中删除编号最小的车厢minH
            Console.WriteLine("移动车厢：{0}从缓冲轨{1}到出轨。", minH, minS);

            //通过检查所有的栈顶，搜索新的minH和minS
            minH = 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 输出结果

数据结构与算法：09 栈与递归

相关标签： C#学习数据结构与算法

上一篇： Python数据结构与算法-栈和递归函数

下一篇：小预算的大数据解决方案

数据结构与算法：09 栈与递归

09 栈

1. 栈的定义与操作

1.1 栈的定义

1.2 栈的操作

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

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

4. 栈的应用

C语言算法书籍推荐（算法与数据结构书籍推荐）

C语言算法书籍推荐（算法与数据结构书籍推荐）

C#数据结构与算法揭秘三链表

C#数据结构与算法揭秘一

C#数据结构与算法揭秘五栈和队列

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二

C#数据结构与算法揭秘四双向链表

Python栈算法的实现与简单应用示例

数据结构与算法（3）- C++ STL与java se中的vector

数据结构与算法：09 栈与递归

09 栈

1. 栈的定义与操作

1.1 栈的定义

1.2 栈的操作

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

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

4. 栈的应用

C语言算法书籍推荐（算法与数据结构书籍推荐）

C语言算法书籍推荐（算法与数据结构书籍推荐）

C#数据结构与算法揭秘三 链表

C#数据结构与算法揭秘一

C#数据结构与算法揭秘五 栈和队列

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

C#数据结构与算法揭秘二

C#数据结构与算法揭秘四 双向链表

Python栈算法的实现与简单应用示例

数据结构与算法（3）- C++ STL与java se中的vector

C#数据结构与算法揭秘三链表

C#数据结构与算法揭秘五栈和队列

C#数据结构与算法揭秘四双向链表