《浅析队列、栈的应用.doc》由会员分享，可在线阅读，更多相关《浅析队列、栈的应用.doc（6页珍藏版）》请在金锄头文库上搜索。
1、 学期论文2专 业： 计算机科学与技术_ 班 级： U计算机111_ 学 号： 1111503111_ _ 姓 名： 于秀芳_ _ 指导教师： 孟敏 _ _ 完成日期： 2012年11月29日_ _ 5浅析队列、栈的应用于秀芳(盐城工学院 优集学院 江苏盐城 224051)摘要：栈和队列是两种常用的数据结构，广泛应用在操作系统、编译程序等各种软件系统中。从数据结构角度看，栈和队列是操作受限的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；从抽象数据类型角度看，栈和队列又是两种重要的抽象数据类型。关键词：栈和队列；数据结构；编译程序Analysis Of The Queue, Stac
2、k Of ApplicationsYuXiuFang(UGS College, Yancheng Institute of Technology, Yancheng, Jiangsu 224051)Abstract: Stacks and queues are two common data structure widely used operating systems, compilers and other software systems .From the perspective of data structure, stack and queue operation is const
3、rained linear list, stack and queue data elements having a single precursor and successor linear relationship;From the perspective of abstract data types, stacks and queues are two kinds of important abstract data type. Key words: Stack and queue ;Data structure; Compiler program0引言：目前我们所学的数据结构包括上学期
4、学过的C+都运用到了栈，队列。1 栈的逻辑结构1.1栈的定义栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈中元素除了具有线性关系外，还具有后进先出的特性。1.2栈的顺序存储结构及实现1.2.1栈的顺序存储结构栈的顺序存储结构称为顺序栈。顺序栈本质上是顺序表的简化，唯一需要确定的是用数组的那一端表示栈底。通常把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在元组中的位置。设存储栈元素的数组长度为StackSize，则栈空时栈顶指针top=-1；栈满时栈顶指top=StackSize-1。入栈时，栈顶指针to
5、p加1；出栈时，栈顶指针top减1。1.2.2顺序栈的实现（1）栈的初始化初始化一个空栈只需将栈顶指针top置为1。（2）入栈操作TemplateVoid SeqStack:Push(DataType x) If(top=StackSize-1)throw”上溢”; data+top=x;(3)出栈操作TemplateVoid SeqStack:Pop() If(top=-1)throw”上溢”; x=datatop-; return x;1.2.3两栈共享空间在一个程序中如果需要同时使用具有相同数据类型的两个栈时，最直接的方法是为每一个栈开辟一个数组空间，同时另一个栈的空间仍有大量剩余而没有
6、得到利用的情况，从而造成存储空间的浪费。一种可取的方法是充分利用顺序栈单向延伸的特性，使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸。1.3栈的链接存储结构及实现1.3.1栈的链接存储结构栈的链接存储结构称为链栈。通常链栈用单链表表示，因此其节点结构与单链表的节点结构相同。因为只能在栈顶执行插入和删除操作，显然以单链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。1.3.2链栈的实现链栈的结点结构可以复用单链表的结点结构Templateclass LinkStackPublic: LinkStac
7、k()top=NULL; LinkStack(); Void push(DataType x); DataType pop(); DataType GetTop()if(top!=NULL)return top-data; Int Empty()top=NULL?return 1:return 0;Private: Node*top;（1）构造函数 构造函数的作用是初始化一个空链栈，由于链栈不带头结点，因此只需将栈顶指针top置为空。（2） 入栈操作 链栈的插入操作只需处理栈顶即第一个位置的情况，而无需考虑其他位置的情况。(3) 出栈操作 链栈的删除操作只需处理栈顶即第一个位置的情况，而无需考
8、虑其他位置的情况。 (4)取栈顶元素 取栈顶元素只需返回栈顶指针top所指结点的数据域。 (5)判空操作 链栈的判空操作只需判断top=NULL是否成立。如果成立则栈为空，返回1；如果栈不为空，则栈非空，返回0. (6)析构函数 链栈的析构函数需要将栈中所有结点的存储空间释放。1.4顺序栈和链栈的比较实现顺序栈和链栈的所有基本操作的算法都只需要常数时间，因此唯一可以比较的是空间性能。初始化时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。所以当栈的使用过程中元素
9、个数变化较大时，用链栈是适宜的；反之，应该采用顺序栈。2 队列2.1队列的定义队列是指允许在一端进行插入操作，在另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为对头。队列是一种只允许在表的一端进行插入操作, 而在另一端进行删除操作的线性表。由于新来的队列元素总是加入到队尾, 而离开队列的总是队头的元素, 因此, 队列也称为先进先出表( First In First Out, 简称FIFO表)。2.2队列的顺序存储结构及实现2.2.1队列的顺序存储结构队列是特殊的线性表，从这个出发点来考虑队列的顺序存储问题。初始存储类似于线性表，但由于只能从一边进入另一边出，所以数据会随着
10、数据操作而不断“前进”，使队列像一条“蠕虫”一样慢慢“爬过”队列定义的全部空间，而且“爬过”的空间就无法再次得到运用。“蠕虫”爬到数组尽头之后则无法前进，而此时很可能数组前端还有大量的数据未得到使用。因此我们将一个数组看作是“相连”的，即将整个数组看做一个环形，而队列“蠕虫”则会在这个环形轨道中持续“爬动”，直到数据装满整个数据空间。2.2.2循环队列的实现 (1)构造函数构造函数的作用是初始化一个空的循环队列，只需将对头指针和队尾指针同时指向数组的某一个位置，一般是数组的高端，即rear=front=QueueSize-1。 (2)入队操作循环队列的入队操作只需将队尾指针rear在循环意义下
11、加1，然后将待插元素x插入队尾位置。 (3)出对操作循环队列的出队操作只需将队头指针front在循环意义下加1，然后读取并返回队头元素(4)读取对头元素 读取队头元素与出队操作一样，唯一区别是不改变对头指针2.3队列的链接存储结构及实现2.3.1队列的链接存储结构队列的链接存储结构称为链队列。链队列是在单链表的基础上做了简单的修改，为了使空队列和非空队列的操作一致，链队列也加上头结点。根据队列的先进先出特性，为了操作上的方便，设置对头指针指向链队列的头结点，队尾指针指向终端节点。2.3.2链队列的实现（1）构造函数构造函数的作用是初始化一个空的链队列，只需申请一个头结点，然后让对头指针和队尾指
12、针均指向头结点。（2）入队操作Templatevoid LinkQueue:EnQueue(DataType x)s=new Node;s-data=x;s-next=NULL; rear-next=s; rear=s;(3)出对操作Templatevoid LinkQueue:EnQueue(DataType x) if(rear=front) throw”下溢”; p=front-next;x=p-data;front-next=p-next; if(p-next=NULL)rear=front; delete p; return x;2.4循环队列和链队列的比较实现循环队列和链队列的基本
13、操作的算法都需要常数时间O(1)。循环队列的链队列的空间性能的比较与顺序栈和链栈的空间性能的比较类似，只是循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队列。3 队列和栈的运用举例3.1队列的应用以列车重排进行分析，一列货运列车共有n 节车厢，每节车厢将停放在不同的车站。假定n 个车站的编号分别为1n，即货运列车按照第n 站至第1 站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。假定重排n 个车厢，可使用k 个缓冲轨，将每个缓冲轨看成是一个队列，用nowOu
14、t 表示下一个输出至出轨的车厢编号。火车车厢重排的算法用伪代码描述如下：分别对k 个队列初始化；初始化下一个有爱输出的车厢编号nowOut=1；依次取入轨中的每一个车厢编号。如果入轨中的车厢编号等于nowOut，则输出该车厢：nowOut+。否则，考虑每一个缓冲轨队列：for（j=1;j=k;j+），取队列j 的对头元素c。如果c=nowOut，则将队列j 的对头元素出队并输出：nowOut+。如果入轨和缓冲轨的对头元素没有编号为nowOut 的车厢，则求小雨入轨中第一个车厢编号的最大队尾元素所在队列编号j。如果j 存在，则把入轨中的第一个车厢移至缓冲轨j；如果j 不存在，但有多余一个空缓冲轨，则把入轨第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束3.2栈的应用首先是背包问题，假设有一个能容纳总体积为T 的背包，另有n 个体积分别是w1，w2wn 个物品，现
