数据结构之队列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
上一篇: 双鹿啤酒怎么样,答案这里看
下一篇: 崇祯明明可以逃走,为什么要选择自缢呢?