《栈和队列的操作及应1》由会员分享，可在线阅读，更多相关《栈和队列的操作及应1（4页珍藏版）》请在金锄头文库上搜索。
1、1栈和队列的操作及应用栈和队列的操作及应用耿超（盐城工学院 优集学院 224001）摘摘 要：要：计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以计算机学习中仅仅学习计算机语言是不够的。还必须掌握数据的组织、处理和运算的一种方法。这也是数据结构这门课的重要性，同时也是学习计算机的重要基础。所以说，数据结构作为计算机教学中的一门重要课程，很多领域都涉及到其中的知识，其中就涉及到栈和队列，下面我们就来初步了解栈与队列的一些基本操作和应用。关键词关键词: 计算机；操作运算；数据结构；栈；队列。 Operation and Application Stack and QueueGeng
2、 Chao(UGS College, Yancheng Institute of Technology, Yancheng, Jiangsu 224001)Abstract: The object of the processing of computer programming in the data, the data has a certain organizational structure; computer learning is not enough to merely learning the computer language. You must also master a
3、method of data organization, processing and computing. Which is the important foundation of the data structure of the importance of this course, learn computer. Therefore, the data structure as an important course in computer teaching, many areas related to knowledge, which relates to the stacks and
4、 queues, we talk about application development stack and queue to a preliminary understanding.Keywords: Computer; Operation op; Data structure; Stack; Queue.引言引言数据结构是计算机学习中的必要基础，栈和队列则又是数据结构学习中的两种重要的抽象数据类型，广泛应用在操作系统、编译程序等各种系统软件中。所以，深入理解栈和队列的基本知识、操作及生活中的一些应用是十分有必要的。数据结构内容丰富、学习量大、实践性强。尤其是栈和队列，他们在在很多领域都
5、有着广泛的使用。因此，在数据结构的研究中，学习并理解栈和队列不仅能更深入了解计算机编程语言，还能够使用栈和队列解决生活中的一些问题。所以，在这里就主要介绍对栈和队列的基本认识、研究及相关的生活应用。1 1 栈和队列的定义及特点栈和队列的定义及特点1.11.1 栈的定义及特点栈的定义及特点栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底 。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈是按
6、照“先作者简介：耿超（1992 年） ，男，在读本科生， 18262381297。2进后出“的原则组织数据的。栈的基本运算有三种：入栈、退栈与读栈顶元素1。（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即 top加 1） ，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢“错误。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即 top 减 1） 。当栈顶指针为 0时，说明栈空，不可进行退
7、栈操作。这种情况称为栈的“下溢“错误。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为 0 时，说明栈空，读不到栈顶元素。1.21.2 队列的定义及特点队列的定义及特点队列 Queue 是只能在一端进行插入，而在另一端进行删除的线性表。能进行插入的一端称为队尾，用 rear 表示队尾指针,允许执行删除操作的一端为队头，用 front 表示队头指针。队列的插入操作称为入队 Enqueue，队列的删除操作称为出队 DeQueue。用线性表的表示 不含元素的空表称为空队列，此时 front 与 rear
8、值相同2。一个队列的队头和队尾都是可以移动的。在队尾插入一个元素(即入队操作)时队尾指针加 1(rear 加 1)在队头删除一个元素(即出队操作)时队头指针加 1(front 加 1)。由于只能在队尾插入和在队头删除所以又称队列为先进先出的线性表。栈是按照“先进先出“的原则组织数据的。队列则具有先进先出的特点3。队列空的条件： front = rear。队列满的条件： rear = MAXSIZE。2 栈和队列之间的联系和区别栈和队列之间的联系和区别1.队列先进先出，栈先进后出。2.对插入和删除操作的“限定“。 栈是限定只能在表的一端进行插入和删除操作的线性表。队列是限定只能在表的一端进行插入
9、和在另一端进行删除操作的线性表。 从“数据结构“的角度看，它们都是线性结构，即数据元素之间的关系相同4。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定“。 栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出“的规则进行操作，而队列必须按“先进先出“的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。3.遍历数据速度不同。栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性
10、队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开3辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表5。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。从“数据结构“的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了他们各自的操作集不同外，主要区别是对插入和删除操作的“限定”。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出“的规则进行操作，而队列必须按“先进先出“的规
11、则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。3.栈和队列在生活中的广泛应用栈和队列在生活中的广泛应用3.1 栈在生活中的一些应用现象栈在生活中的一些应用现象1.某餐厅有一个放盘子的容器，当服务员洗净一个盘子后就将其放在容器中一摞盘子的最上面。当使用盘子时就从这摞盘子的最上面取下一个。如果将容器看成是一个栈，容器中的盘子看成栈中的数据元素。那么，放盘子就是近栈操作拿盘子就是出栈操作6。2.如果我们将冲锋枪的子弹匣看成是一个栈，则其中的子弹实战中的数据元素。那么，向弹匣中压入子弹的操作就是近栈操作，而射击子弹时的操作就是出栈操作。生活中还有很多，只
12、要你仔细的观察就会发现生活中普遍存在着它的影子。3.2 队列在生活中的一些应用现象队列在生活中的一些应用现象1.在日常生活中，到车站去购买车票的人们就要排成一个队列。售票站遵循着先来者先购票先出对的原则，后来者必须排到对尾的入队处等候，不许在中间插队。2.在多任务的批处理操作系统中，用户提交的作业需要排成队列。系统采用先来先服务的原则按序处理队列中的每个作业。同样，在多道作业的系统中等待打印输出的多个用户的任务也要排成一个队列，系统按序输出对列中的每个任务。3.铁路调度中用到栈，民航机票预订中用到队列。4.停车场治理系统，进来一辆车在登记后进入车场，如果车场已满则在车场便道处等候，一旦有车开走
13、则可从便道进入车场。4 结束语结束语计算机技术与应用的蓬勃发展，开始了信息时代的序幕，也就意味着计算机在人们的生活中起着越来越不可替代的作用。而计算机编程中加工处理的对象是数据，数据具有一定的组织结构，所以计算机学习中仅仅学习计算机语言是不够的。所以说，在当今这个时代，精通于计算机语言已经开始成为一种必要的技能，尤其是我们这样学习计算机的在校大学生。而作为计算机学习学习中有着广泛应用的栈和队列，我们不仅要精通栈和队列的各种知识、操作，还要学会深入探索它们在学习、生活中的应用，这样才能在学习上取得更好的收获。参考文献参考文献: :1戴坚锋,邵雷兵.一种新型的可扩展分布式数据结构J.计算机应用研究,2005;22(8):170-171.42 李先国,梁超.一种高效的适用于字词检索的数据结构J.栈和队列与计算机,2006;23(12):157-160.3王波. 数据结构栈和队列的联系D.曲阜：曲阜师范大学计算机科学学院.2003 年.4蓝雯飞. 数据结构的面向对象描述方法研究J.计算机工程与应用，2006;42(26)：79-80.5刘毅.关于栈和队列问题的研究J.计算机应用与软件,2005;22(8):36-38.6胡泽明,岳瑞生,王志刚.嵌入式 GIS 线要素无缝拼接的数据结及实现算法测绘科学,2006;31(5):102-103.
