基本信息
- 项目名称：
- 栈和队列的深入研究及应用
- 来源：
- 第十二届“挑战杯”作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 在栈和队列的研究中通常只讨论单栈、共享栈、多链栈、链队列和顺序循环队列等内容。基于对存储空间以及存储结构自适应性的考虑，本项目在已有结构的基础上提出了动态栈、动态双端栈、动态多栈、动态循环队列、循环多队列以及动态循环多队列等新的存储结构，并对这些结构进行了深入研究。该项目解决了一些实际问题，也指明了今后的研究方向。项目自启动以来，已在省级以上学术期刊发表论文7篇，其中国家权威期刊发表论文4篇。
- 详细介绍：
- 栈和队列是两种重要的数据类型。栈和队列在各种类型的系统中应用广泛。在传统的数据结构的研究中，关于栈的研究通常只讨论单顺序栈、单链栈、共享栈、链式多栈等内容，这些存储结构大多事先开辟好定量存储空间，导致了在具体应用中存储空间不同程度的浪费，以往文献并未就此问题做深入探究以求解决。本文在这些基础上实现了单顺序栈存储空间的动态利用和共享栈的动态存储结构，同时对文献中涉及较少的顺序多栈存储结构给出了具体实现方法，并做到了动态开辟与回收存储空间。最后用上述结构解决了一些实际问题。 在传统的数据结构的研究中，关于队列的研究通常只讨论链队列和顺序循环队列，而顺序循环队列的应用更为广泛，于是在此实现了顺序循环队列的动态化存储，避免了存储空间的大量浪费。基于实际应用的需要，对文献中未曾涉及到的循环多队列的顺序存储结构和循环多队列的动态存储也均予以实现，并将他们用于实际问题中。
作品专业信息
撰写目的和基本思路
- 栈和队列在各类系统中应用广泛。堆栈技术被广泛应用于编译软件和程序设计，操作系统、事务管理中广泛应用了队列技术。讨论堆栈与队列的结构特征与实现特点，有重要意义。在实际课堂教学中常讨论单栈、单队列、共享栈和循环队列等传统的栈和队列。但在实际应用中常会遇到多栈或多队列结构，在数据结构与算法中未研究该内容，此项目研究并实现了多栈和多队列的逻辑结构及其存储结构，并用这些数据结构解决了一些实际问题。
科学性、先进性及独特之处
- 该作品中实现了单顺序栈存储空间的动态利用和共享栈的动态存储结构，同时对文献中涉及较少的顺序多栈存储结构给出了具体实现方法，并做到了动态开辟与回收存储空间；文中也实现了顺序循环队列的动态化存储，避免了存储空间的大量浪费。基于实际应用的需要，对相关文献中未涉及到过的循环多队列的顺序存储结构和循环多队列的动态存储也均予以实现，并将他们用于实际问题中。
应用价值和现实意义
- 在实际应用中经常会遇到多栈或多队列的一些存储结构，但是在数据结构与算法中未研究该内容，此项目研究并实现了多栈和多队列的逻辑结构和存储结构，并用这些数据结构解决了一些实际生活中的问题。在大型事务管理及编译软件中，内存空间的合理使用显得极为重要，为此，在此项目中也实现了单栈、单队列、双端栈、多栈、多队列存储空间的动态扩充和动态回收，可节约大量的内存空间，降低程序的时间复杂度和空间复杂度。
学术论文摘要
- 在传统的数据结构的研究中，关于栈的研究通常只讨论单顺序栈、单链栈、共享栈、链式多栈等内容，这些存储结构大多事先开辟好定量存储空间，导致了在具体应用中存储空间不同程度的浪费，以往文献未就此问题做深入探究以求解决。本文在这些基础上实现了单顺序栈存储空间的动态利用和共享栈的动态存储结构，同时对文献中涉及较少的顺序多栈存储结构给出了具体实现方法，并做到了动态开辟与回收存储空间。最后用上述结构解决了一些实际问题。在传统的数据结构的研究中，关于队列的研究通常只讨论链队列和顺序循环队列，而顺序循环队列的应用更为广泛，于是在此实现了顺序循环队列的动态化存储，避免了存储空间的大量浪费。基于实际应用的需要，对文献中未曾涉及到的循环多队列的顺序存储结构和循环多队列的动态存储也均予以实现，并将他们用于实际问题。
获奖情况
- 项目自启动以来，已在省级以上学术期刊发表论文7篇，其中国家权威期刊发表论文4篇。具体如下： 1、《多栈的顺序存储及实现技术》发表于《自动化与仪器仪表》2010. 9(5期)； 2、《循环队列存储空间的动态回收方法》发表于《自动化与仪器仪表》2010. 11(6期)； 3、《动态双端栈技术》发表于《自动化与仪器仪表》2011. 5(3期)； 4、《动态多栈技术》发表于《自动化与仪器仪表》2011. 7(4期)（已采稿）； 5、《循环多队列的顺序存储和算法实现》发表于《甘肃联合大学学报》2010. 7(4期)； 6、《线性表存储空间的动态回收》发表于《甘肃科技纵横》2010. 11(5期)； 7、《线性表中数据元素循环移动的一种高效算法》发表于《甘肃高师学报》2011. 4(2期)。
鉴定结果
- 作品取材真实，内容严谨，在已有文献的基础上提出了创新，并取得了突破，所研究的内容具有一定的实用价值，有广泛的应用前景。
参考文献
- 参考文献： [1] 严蔚敏，吴伟民. 数据结构（C语言版）.北京:清华大学出版社,1997 [2] Robert L.Kruse,Alexander J.Ryba.Data Structures and Program Design in C++[M].Pearson Education,USA,2001.5 [3] 王晓东.计算机算法设计与分析(第二版)[M]. 北京:电子工业出版社,2005. [4] 李国东等. 通过单向队列自动机对适应性移动计算系统中组合事件的分析(英文)[J].软件学报,2002,13(8):1402-1411 [5] 薛华成.管理信息系统.北京:清华大学出版社,1993. [6] 李春葆. 数据结构教程（第二版）[M]. 北京:清华大学出版社,2007 [7] (美)Adam Drozdek.数据结构与算法——C++版[M].北京:清华大学出版社,2006 [8] 王琪玮等.循环队列在实时数据系统处理中的应用[J]华北科技学院学报.2003,6(1):52-53 [9] 龚舒群,任煜等.循环队列中的头尾指针设计[J].现代计算机,2007,253(2):17-20 [10] 梁西陈.关于《数据结构》课程中顺序栈的结构图示的思考.宿州教育学院学报,2006,9(1):100-101
同类课题研究水平概述
- 目前，国内外关于数据结构中栈和队列这两种限定性线性表的研究都只局限于传统的单栈、单循环队列、双端栈、链栈等存储结构，在实际的课堂教学中也只涉及到这些内容，这些存储结构大多事先开辟好定量存储空间，导致了在具体应用中存储空间不同程度的浪费，以往文献未就此问题做深入探究以求解决。故而，此项目中所提出的栈和队列的的动态存储结构以及多栈、多循环队列的新的存储结构的定义在国内外的同类研究中尚处于探索阶段。
