数据结构之队列and栈总结分析

一、前言：

　　数据结构中队列和栈也是常见的两个数据结构，队列和栈在实际使用场景上也是相辅相成的，下面简单总结一下，如有不对之处，多多指点交流，谢谢。

二、队列简介

　　队列顾名思义就是排队的意思，根据我们的实际生活不难理解，排队就是有先后顺序，先到先得，其实在程序数据结构中的队列其效果也是一样，及先进先出。

　　   队列大概有如下一些特性：

　　　　　1、操作灵活，在初始化时不需要指定其长度，其长度自动增加（默认长度为32）

　　　　　　　　注：在实际使用中，如果事先能够预估其长度，那么在初始化时指定长度，可以提高效率

　　    　　2、泛型的引入，队列在定义时可以指定数据类型避免装箱拆箱操作

　　　　　3、存储数据满足先进先出原则

　　     

　　　c#中有关队列的几个常用方法：

• • count：count属性返回队列中元素个数。
  • enqueue：enqueue()方法在队列一端添加一个元素。
  • dequeue：dequeue()方法在队列的头部读取和删除元素。如果在调用dequeue()方法时，队列中不再有元素，就抛出一个invalidoperationexception类型的异常。
  • peek：peek()方法从队列的头部读取一个元素，但不删除它。
  • trimexcess：trimexcess()方法重新设置队列的容量。dequeue()方法从队列中删除元素，但它不会重新设置队列的容量。要从队列的头部去除空元素，应使用trimexcess()方法。
  • clear：clear()方法从队列中移除所有的元素。
  • toarray：toarray()复制队列到一个新的数组中。

　　下面通过队列来实例模拟消息队列的实现流程：

 

using system;
using system.collections;
using system.collections.generic;

namespace datastructurequeuetest
{
    class program
    {
        static void main(string[] args)
        {
            console.writeline("通过queue来模拟消息队列的实现");
            queuetest queuetest = new queuetest();

            while (true)
            {
                console.writeline("请输入你操作的类型：1:代表生成一条消息，2：代表消费一条消息");
                string type = console.readline();
                if (type == "1")
                {
                    console.writeline("请输入具体消息：");
                    string inforvalue = console.readline();
                    queuetest.informationproducer(inforvalue);
                }
                else if (type == "2")
                {
                    //// 在消费消息的时候，模拟一下，消费成功与消费失败下次继续消费的场景

                    object inforvalue = queuetest.informationconsumerget();
                    if (inforvalue == null)
                    {
                        console.writeline("当前无可消息可消费");
                    }
                    else
                    {
                        console.writeline("获取到的消息为：" + inforvalue);

                        console.writeline("请输入消息消费结果：1:成功消费消息，2：消息消费失败");
                        string consumerstate = console.readline();

                        ///// 备注：该操作方式线程不安全，在多线程不要直接使用
                        if (consumerstate == "1")
                        {
                            queuetest.informationconsumerdel();
                        }
                    }
                }
                else
                {
                    console.writeline("操作有误，请重新选择");
                }
            }
        }
    }

    /// <summary>
    /// 队列练习
    /// </summary>
    public class queuetest
    {
        /// <summary>
        /// 定义一个队列
        /// </summary>
        public queue<string> queue = new queue<string>();

        /// <summary>
        /// 生成消息--入队列
        /// </summary>
        /// <param name="inforvalue"></param>
        public void informationproducer(string inforvalue)
        {
            queue.enqueue(inforvalue);
        }

        /// <summary>
        /// 消费消息---出队列--只获取数据，不删除数据
        /// </summary>
        /// <returns></returns>
        public object informationconsumerget()
        {
            if (queue.count > 0)
            {
                return queue.peek();
            }

            return null;
        }

        /// <summary>
        /// 消费消息---出队列---获取数据的同时删除数据
        /// </summary>
        /// <returns></returns>
        public string informationconsumerdel()
        {
            if (queue.count > 0)
            {
                return queue.dequeue();
            }

            return null;
        }
    }
}

 

 

三、栈简介

　　栈和队列在使用上很相似，只是栈的数据存储满足先进后出原则，栈有如下一些特性：

　　　　　1、操作灵活，在初始化时不需要指定其长度，其长度自动增加（默认长度为10）

　　　　　　　　注：在实际使用中，如果事先能够预估其长度，那么在初始化时指定长度，可以提高效率

　　    　　2、泛型的引入，栈在定义时可以指定数据类型避免装箱拆箱操作

　　　　　3、存储数据满足先进后出原则

　　　　c#中有关栈的几个常用方法：

• count：count属性返回栈中的元素个数。
• push：push()方法在栈顶添加一个元素。
• pop：pop()方法从栈顶删除一个元素，并返回该元素。如果栈是空的，就抛出一个invalidoperationexception类型的异常。
• peek：peek()方法返回栈顶的元素，但不删除它。
• contains：contains()方法确定某个元素是否在栈中，如果是，就返回true。

 　　　　下面通过一个栈来模拟浏览器的回退前进操作的实现

 

using system;
using system.collections.generic;

namespace datastructurestacktest
{
    class program
    {
        static void main(string[] args)
        {
            //// 通过栈来模拟浏览器回退前进操作
            ////   1、定义两个栈，分别记录回退的地址集合，和前进地址集合
            ////   2、在操作具体的回退或者前进操作时
            ////      如果和前一次操作相同，那么就取出对应队列的一条数据存储到另外一个队列
            console.writeline("本练习模拟浏览器的回退前进操作：");

            /// 假设浏览器已浏览了20个网站记录
            stacktest stacktestback = new stacktest(20);
            stacktest stacktestgo = new stacktest(20);
            for (int i = 0; i < 20; i++)
            {
                stacktestback.pushstack("网站" + (i + 1).tostring());
            }

            //// 记录上一次操作
            string beforopert = "";
            while (true)
            {
                console.writeline("");
                console.writeline("请输入你操作的类型：1:回退，2：前进");
                string type = console.readline();

                if (type == "1")
                {
                    //// 出栈
                    if (beforopert == type)
                    {
                        stacktestgo.pushstack(stacktestback.getanddelstack());
                    }
                    string wbesit = stacktestback.getstack();
                    console.writeline("回退到页面：" + wbesit);
                    beforopert = type;
                }
                else if (type == "2")
                {
                    //// 出栈
                    if (beforopert == type)
                    {
                        stacktestback.pushstack(stacktestgo.getanddelstack());
                    }
                    string wbesit = stacktestgo.getstack();

                    console.writeline("回退到页面：" + wbesit);
                    beforopert = type;
                }
                else
                {
                    console.writeline("请输入正确的操作方式！！");
                }
            }
        }
    }

    /// <summary>
    /// 队列练习
    /// </summary>
    public class stacktest
    {
        /// <summary>
        /// 定义一个栈
        /// </summary>
        public stack<string> stack;

        /// <summary>
        ///无参数构造函数，栈初始化为默认长度
        /// </summary>
        public stacktest()
        {
            stack = new stack<string>();
        }

        /// <summary>
        ///有参数构造函数，栈初始化为指定长度
        ///如果在定义队列时，如果知道需要存储的数据长度，那么最好预估一个长度，并初始化指定的长度
        /// </summary>
        public stacktest(int stacklen)
        {
            stack = stacklen > 0 ? new stack<string>(stacklen) : new stack<string>();
        }

        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="inforvalue"></param>
        public void pushstack(string inforvalue)
        {
            stack.push(inforvalue);
        }

        /// <summary>
        /// 出栈（但不删除）
        /// </summary>
        /// <returns></returns>
        public string getstack()
        {
            if (stack.count > 0)
            {
                return stack.peek();
            }

            return null;
        }

        /// <summary>
        /// 出栈（并删除）
        /// </summary>
        /// <returns></returns>
        public string getanddelstack()
        {
            if (stack.count > 0)
            {
                return stack.pop();
            }

            return null;
        }
    }
}

 

四、使用场景总结

　　根据队列和栈的特点，下面简单总结一下队列和栈的一些实际使用场景

　　　队列：

　　　　1、异步记录日志，此处会涉及到单例模式的使用

　　　　2、消息队列

　　　　3、业务排队，比如12306车票购买排队等候

　　　　4、其他符合先进先出原则的业务操作

　　　栈：

　　　　1、可回退的操作记录，比如：浏览器的回退操作

　　　　2、计算表达式匹配，比如：计算器表达式计算

　　　　3、其他符合先进后出原则的业务操作

 

附件：

关于这一些练习的代码，上传到github，有兴趣的可以看一下：

https://github.com/xuyuanhong0902/datastructuretest.git