数据结构基础:栈(Stack)

什么是栈?

? ? 栈是限制插入和删除只能在同一个位置上进行的表,这个位置就是栈的顶端,对于栈的操作主要有三种形式:入栈(将元素插入到表中),出栈(将表最后的元素删除,也就是栈顶的元素),返回栈顶元素。栈有时又叫LIFO(后进先出)表。

栈的实现

栈可以有两种实现方式:1)数组实现 2)链表实现

栈的双向链表实现

    public class StackForLinked<T>
        {
                private int num = 0;
                public int count { get{return num;} }
                private Node<T> root = null;
                private class Node<T>
                {
                    public T data;  
                    public Node<T> prev;
                    public Node<T> next;
                    public Node(T value)
                    {
                            this.data = value;
                            this.prev=null;
                            this.next=null;
                    } 
                    public Node(T value,Node<T> prev,Node<T> next):this(value)
                    {
                            this.prev = prev;
                            this.next=next;
                    }
                }
                public void Push(T value)
                {
                    Node<T> node = new Node<T>(value);
                    if(root==null)
                    {
                            root = node;
                    }
                    else
                    {
                            var last= GetLastNode();
                            last.next = node;
                            node.prev= last;
                    }
                    num++;
                }
                public T Pop()
                {
                    var node=GetLastNode();
                    if(node==null)
                            throw new Exception();
                    node.prev.next=null;
                    num--;
                    return node.data;
                }
                public T GetTop()
                {
                    var node =GetLastNode();
                    if(node==null)
                            throw new Exception();
                    return node.data;
                }
                private Node<T> GetLastNode()
                {
                    Node<T> p = root;
                    if(root==null)
                    {
                         return null;
                    }
                    while(true)
                    {
                            if(p.next!=null)
                            {
                                p=p.next;
                            }
                            else 
                                break;
                    }
                    return p;
                }
        }

栈的数组实现

    public class StackForArray<T>
        {
                private static int length = 100;
                private T[] objList = new T[length]; 
                private int currentIndex = 0;
                public int count { get { return this.currentIndex;} }
                private void ensureCapcity(int capcity)
                {
                    if(capcity < currentIndex)
                    {
                            return;
                    }
                    T[] old = objList;
                    objList = new T[capcity];
                    for(int i=0;i<old.Length;i++)
                    {
                            objList[i] = old[i];
                    }
                }
                public void Push(T value)
                {
                    if(currentIndex == length)
                    {
                            ensureCapcity(currentIndex * 2 +1);
                    }
                    objList[currentIndex] = value;
                    currentIndex++;
                }
                public T Pop()
                {
                    if(currentIndex == 0)
                            throw new Exception();
                    currentIndex--;
                    return objList[currentIndex];
                }
                public T GetTop()
                {
                    if(currentIndex == 0)
                    {
                            throw new Exception();
                    }
                    return objList[currentIndex -1];
                }
        }

PS:对于链表在添加和删除方面是O(1), 但是在查找方面则是O(N);数组在查找方面是O(1)操作,但是在插入或者是删除方面涉及到表的中元素的位置上的移动,若数据中的元素较多会带来性能上的损失。所以在考虑使用链表还是使用数组进行存储数据的时候,应该考虑上述所说(数据量大小,插入和删除多还是查找的多)。当前这与栈的关系不太大,因为栈都是在一端进行操作,不会涉及元素移动的问题。

栈的应用

栈的应用有很多,这里只举一些简单的例子:
1.平衡符号:例如判断括号是否成对出现,通过将括号入栈然后碰见成对的括号就出栈,最后判断栈中的元素是否为空,为空则是成对出现,反之则不成对
2.中缀表达式转化为后缀表达式:
? ? 中缀表达式和后缀表达式: 例如表达式 a + b * c 这就是我们平时所见的正常的数学计算表达式,在数学上我们也知道怎么计算,但是你把这一段表达式告诉计算机,然后计算出结果,那么这个结果是怎么计算出来的呢?这里就涉及一个概念叫做后缀表达式,首先 a + b * c 会先通过栈转化为 a b c * + 然后再通过栈进行计算从而得出结果,前者通常叫做中缀表达式。随后会有一段代码的例子,可以让你真正的了解数学表达式是如何通过栈进行计算的
3.方法调用:类似于平衡符号的检测,所有的方法调用和返回都是成对的,在开始调用的时候需要在栈内存储一些信息(位置,对应变量的名字和返回地址等),方法完成后需要从栈中出栈拿到当初存储的信息然后做一些操作,这也正好印证了,当递归调用的时候,不当的递归会出现 Stackoverflow 异常,也就是说在栈(在window下,默认大小是1M )中已经存储不下每一次递归的信息了,就会报这个错误。

PS: 我这里说的都是同步方法,存在一个方法的调用需要等待另一个方法的完成,异步方法还不太了解,期待后续学习会有更多的收获

栈实现基本操作的运算

? ? 用栈来实现简单的基本数学运算:+ ,- ,* , / 和( )在数学中我们都知道这几种符号的优先级,那么计算机时怎么做到的呢? 下面我们以一个表达式为例子来实现一下计算机的计算过程
? ? 表达式:a + b * c + ( d * e + f ) * g ,除栈外,我们还需要一个输出字符串用来存储生成的后缀表达式,默认情况下为空,出于方便我会使用 [] 代表一个栈,[ 代表栈底,] 代表栈顶,用 | 分割每个元素。

原理

1.对常数输出,对操作符号入栈操作,根据优先级别判断是出栈还是入栈;
2.优先级低的不允许出现在优先级高的后面(栈中存在一个优先级高的符号,此时来了一个低优先级符号,需要进行先把高优先级的符号出栈,然后将低优先级的符号入栈);
3.同优先级的符号先出栈再入栈;
4.对于存在括号的情况,当前栈顶的元素是 ( 那么接下来的一个符号不比较优先级直接入栈,接下来的操作遵循前3条规则;
5.当遇见 )的时候,执行出栈操作直到遇见出栈的第一个( 为止;
6.得到后缀表达式之后再次使用栈进行计算,将后缀表达式中的值入栈,碰见操作符,出栈两个元素执行运算符计算,将计算的结果插入到栈中,直到后缀表达式的尽头,最终结果位于栈顶,出栈即可得到

步骤:

1.将中缀表达式转化为后缀表达式

Step 1 : 我们第一次读取的是常数 a ,直接输出,此时输出的字符串中的值为 a
Step 2 : 继续读取,接下来读取的是操作符号 + ,入栈操作,此时栈中的元素为 [ + ]
Step 3 : 继续读取,接下来读取的是常数 b , 直接输出,此时输出的字符串中的值为 a b
Step 4 : 继续读取,接下来读取的是操作符号 * , 入栈操作,此时栈中的元素为 [ + | * ]
Step 5 : 继续读取,接下来读取的是常数 c , 直接输出,此时输出的字符串中的值为 a b c
Step 6 : 继续读取,接下来读取的是操作符号 + , 栈顶元素 * 的优先级高于 + ,将 * 出栈,之后发现栈顶元素为 +,优先级相同,继续出栈,然后将 + 进栈,此时栈中的元素为[ + ],输出字符串中的值为 a b c * +
Step 7 : 继续读取,接下来读取的是操作符号 ( , 入栈操作,此时栈中的元素为 [ + | ( ]
Step 8 : 继续读取,接下来读取的是常数 d , 直接输出,此时输出的字符串中的值为 a b c * + d
Step 9 : 继续读取,接下来读取的是操作符号 * , 入栈操作,此时栈中的元素为[ + | ( | * ]
Step 10 : 继续读取,接下来读取的是常数 e , 直接输出,此时输出的字符串中的值为 a b c * + d e
Step 11 : 继续读取,接下来读取的是操作符号 + , 栈顶元素 * 的优先级高于 + ,先执行出栈操作,在执行 + 入栈操作,此时栈中的元素为[ + | ( | +] , 输出字符串中的值为 a b c * + d e *
Step 12 : 继续读取,接下来读取的是常数 f , 直接输出,此时输出的字符串中的值为 a b c * + d e * f
Step 13 : 继续读取,接下来读取的是操作符号 ) , 开始执行出栈操作,直到遇见第一个出栈的元素为 ( 停止,此时栈中的元素为[ + ] , 输出字符串中的值为 a b c * + d e * +
Step 14 : 继续读取,接下来读取的是操作符号 * , 入栈操作,此时栈中的元素为[ + | * ]
Step 15 : 继续读取,接下来读取的是常数 g , 直接输出,此时输出的字符串中的值为 a b c * + d e * f + g
Step 16: 继续读取,到达了末端,开始执行中出栈操作,直到栈为空,此时输出的字符串中的值为 a b c * + d e * f + g * + ,从而得出后缀表达式为:a b c * + d e * f + g * +

2.计算后缀表达式 (Step中的括号的使用是起到辅助清晰的作用,因为并没给字符实际的值)

Step 1 : 读取后缀表达式,第一个遇到的是 a 执行入栈操作,此时栈中的元素为 [ a ]
Step 2 : 继续读取,解下来遇到的是 b ,执行入栈操作,此时栈中的元素为 [ a | b ]
Step 3 : 继续读取,解下来遇到的是 c ,执行入栈操作,此时栈中的元素为 [ a | b | c ]
Step 4 : 继续读取,解下来遇到的是 * ,出栈两个元素,计算 b * c ,然后在执行入栈, 此时栈中的元素为 [ a | b * c ]
Step 5 : 继续读取,解下来遇到的是 + ,出栈两个元素,计算 a + b * c,然后执行入栈操作,此时栈中的元素为 [ a + b * c ]
Step 6 : 继续读取,解下来遇到的是 d ,执行入栈操作,此时栈中的元素为 [ a + b * c | d ]
Step 7 : 继续读取,解下来遇到的是 e ,执行入栈操作,此时栈中的元素为 [ a + b * c | d | e ]
Step 8 : 继续读取,解下来遇到的是 * ,出栈两个元素,计算 d * e ,然后执行入栈操作,此时栈中的元素为 [ a + b * c | d * e ]
Step 9 : 继续读取,解下来遇到的是 f ,执行入栈操作,此时栈中的元素为 [ a + b * c | d * e | f ]
Step 10 : 继续读取,解下来遇到的是 + ,出栈两个元素,计算 d * e + f ,然后执行入栈操作,此时栈中的元素为 [ a + b * c | d * e + f ]
Step 11 : 继续读取,解下来遇到的是 g ,执行入栈操作,此时栈中的元素为 [ a + b * c | d * e + f | g ]
Step 12 : 继续读取,解下来遇到的是 * ,出栈两个元素,计算 ( d * e + f ) * g ,然后执行入栈操作,此时栈中的元素为 [ a + b * c | ( d * e + f ) * g ]
Step 13 : 继续读取,解下来遇到的是 + ,出栈两个元素,计算 a + b * c + ( d * e + f ) * g ,然后执行入栈操作,此时栈中的元素为 [ a + b * c + ( d * e + f ) * g ]
Step 14 : 继续读取,到达了末端,执行出栈操作,出栈的结果就是计算的结果 a + b * c + ( d * e + f ) * g

实现代码

class Program
{
        static List<Priority> priority = new List<Priority>()
        {
        new Priority() { level = 0 , symbal ="+" },
        new Priority() { level = 0 , symbal ="-" },
        new Priority() { level = 1 , symbal ="*" },
        new Priority() { level = 1 , symbal ="/" },
        new Priority() { level = 2 , symbal ="%" },
        new Priority() { level = int.MaxValue , symbal ="(" },
        new Priority() { level = int.MaxValue , symbal =")" }
        };
        static void Main(string[] args)
        {
                //string expression = "a + b * c + ( d * e + f ) * g";
                //string expression ="10 + 1 * 10 + ( 2 * 3 + 4 ) * 10"; // 120 
                //string expression ="1 + 2 + 3 ";
                string expression ="3 * ( ( 2 - 4 ) / ( 2 - 1 ) ) ";
                GenerateExpression(expression);
                Console.WriteLine(OutputStr);
                Console.WriteLine(CalculateValue());
        }
        ///生成后缀表达式的栈
        static StackForArray<Priority> symbalStack = new StackForArray<Priority>();
        /// 输出字符串
        static string OutputStr=string.Empty;
        /// 生成后缀表达式
        static void GenerateExpression(string expression)
        {
                string[] symbals = expression.Split(' ');
                foreach(string symbal in symbals)
                {
                        RecursionExpression(symbal);
                }
                while(true)
                {
                        try
                        {
                            var popElement = symbalStack.Pop();
                            OutputStr += popElement.symbal +" ";
                        }
                        catch(Exception ex)
                        {
                            break;
                        }
                }
        }
        // 计算表达式的值
        static int CalculateValue()
        {
                StackForArray<int> valueStack = new StackForArray<int>();
                string[] symbals = OutputStr.Split(new char[]{' '}
                        ,StringSplitOptions.RemoveEmptyEntries);
                foreach(var symbal in symbals)
                {
                        var temp = priority.Where(x=>x.symbal ==symbal).FirstOrDefault();
                        if(temp!=null)
                        {
                            var t = 0;
                            var second = valueStack.Pop();
                            var first = valueStack.Pop();
                            switch (symbal)
                            {
                                    case "*":
                                        t = first * second;
                                        break;
                                    case "/":
                                        t = first / second;
                                        break;
                                    case "+":
                                        t = first + second;
                                        break;
                                    case "-":
                                        t = first - second;
                                        break;
                                    default:
                                     throw new Exception();
                            }
                            valueStack.Push(t);
                        }
                        else
                        {
                            valueStack.Push(int.Parse(symbal));
                        }
                }
                return valueStack.Pop();
        }
        /// 递归表达式
        static void RecursionExpression(string symbal)
        {
                var temp = priority.Where(x=>x.symbal == symbal).FirstOrDefault();
            if(temp==null) 
                {
                        OutputStr+= symbal + " ";
                        return;
                }
                var stackCount = symbalStack.count;
                if(stackCount==0 || temp.symbal =="(")
                {
                        symbalStack.Push(temp);
                        return;
                }
                if(temp.symbal ==")")
                {
                        while(true)
                        {
                            var popElement = symbalStack.Pop();
                            OutputStr += popElement.symbal +" ";
                            if(popElement.symbal=="(")
                            {
                                    OutputStr=OutputStr.Substring(0,OutputStr.Length -2);
                                    break;
                            }
                        }
                        return;
                }
                var topElement = symbalStack.GetTop();
                if(temp.level > topElement.level || topElement.symbal=="(")
                {
                        symbalStack.Push(temp);
                        return;
                }
                if(temp.level <= topElement.level && topElement.symbal != "(")
                {
                        var popElement= symbalStack.Pop();
                        OutputStr += popElement.symbal +" ";
                        RecursionExpression(temp.symbal);
                        return;
                }
            } 
    }
    public class Priority
    {
        public string symbal { get; set; }

        public int level { get; set; }
    }
}

PS:测试的代码比较简单,主要看思路吧

爱编程-编程爱好者经验分享平台

文章评论

  

版权所有 爱编程 © Copyright 2012. w2bc.com. All Rights Reserved.
闽ICP备12017094号-3