浅谈栈和队列

浅谈栈和队列摘要:栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。关键词:栈和队列;数据结构;线性表;抽象数据类型StackandQueueAbstract:Stackasakindofdatastructure,itisakindofcanintheendoftheinsertanddeleteoperationofthespeciallinearlist.Queueisaspecialkindoflinearlist,itisallowedonlyinthefrontofthetable(front)todeleteoperation,butinthetableafterend(rear)insertionoperation.Forinsertionoperationoftheendcalledrear,todeleteoperationoftheendcalledteamhead.Thequeuenoelement,calledemptyqueue.Keywords:Stackandqueue;Datastructure;Linearlist;Abstractdatatype0引言栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—firstinfirstout）的线性表。1栈1.1栈的逻辑结构栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(LastInFirstOut).1.2栈的顺序存储结构及实现由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。#includeiostream.hstructnode{intdata;node*next;};classLinkStack{public:LinkStack(){top=NULL;}//构造函数置空链栈~LinkStack();//析构函数，释放链栈中个节点的存储空间voidPush(intx);//将元素x进栈intPop();//将栈顶元素出栈intGettop()//获取栈顶元素{if(top!=NULL)returntop-data;}//取栈顶元素（并不删除）boolempty()//判断链栈是否为空栈{if(top==NULL)return1;elsereturn0;}private:node*top;//栈顶指针即链栈的头指针};voidLinkStack::Push(intx)//元素进栈{node*s=newnode;//申请一个数据域为x的节点ss-data=x;s-next=top;//将节点s插在栈顶top=s;}intLinkStack::Pop()//元素出栈{intx;if(top==NULL)throw下溢;x=top-data;//暂存栈顶元素node*p=top;//将栈顶节点摘链top=top-next;deletep;returnx;}LinkStack::~LinkStack()//析构函数将链栈中所有节点的存储空间释放{while(top){node*p=top-next;deletetop;top=p;}}voidmain(){LinkStacklink;intdata;cout请输入进栈的10个元素:;for(inti=0;i10;i++)//输入进栈的10个元素{cindata;link.Push(data);}link.Pop();//栈顶元素出栈cout现在栈顶的元素为:link.Gettop()endl;//输出栈顶元素while(!link.empty())cout现在出栈的是：link.Pop()endl;//所有元素一个一个出栈}1.3顺序栈和链栈的比较实现顺序栈和链栈的所有基本操作的算法都只能需要常数时间，因此唯一可以比较的是空间性能。初始时顺序必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。所以当栈的使用过程中元素个数变化较大时，用链栈适宜。反之，应该采用顺序栈。2队列2.1队列的逻辑结构队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front),队列的操作原则是先进先出的，所以队列又称作FIFO表(FirstInFirstOut)。2.2队列的存储结构及实现队列的顺序存储结构：假设线性表有个n数据元素，顺序表要求把表中的所有元素都存储在数组的前n个单元。假设队列有n个元素，顺序存储的队列也应该把队列的所有元素都存储在数组的前个单元。如果把附着元素放在数组中下标为0的一端，则入队操作的时间开销公为O（1），此时的入队操作相当于追加，不需要移动元素；但是出队操作的时间开销为O（n）。队列的链接存储结构：队列的链接存储结构称为链队列。链队列是在单链表的基础上做了简单的修改，为了使空队列和非空队列的操作一致，链队列也加上头结点。根据队列的先进先出特性，为了操作上的方便，设置附着指针指向链队列的头结点，附属指针指向终端结点。//循环队列的实现ConstintQueueSize=100;TemplateclassDataTypeClassCirQueue{Public:cirQueue(){front=rear=QueueSize-1;}~cirQueue(){}VoidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();IntEmpty(){front==rear?return1:return0;}Private:DataTypedata[QueueSize];Intfront,rear;};//队列的链接存储结构的实现TemplateclassDataTypeClassLinkQueue{Public:LinkQueue();~linkQueue();VoidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();IntEmpty(){front==rear?return1:return0;}Private:NodeDataType*front,*rear;};2.3循环队列和链队列的比较顺序队列一次性要分配大量保证够用的空间，效率较高，因为是基于数组的，长度也是固定的。可以实现变长，但是一般代价较高。链表队列基于链表的，要动态创建和删除节点，效率较低，但是可以动态增长。3栈和队列的区别栈和队列都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用。不同的是，栈就象一个很窄的桶先存进去的数据只能最后才能取出来，而且队列则不一样，即“先进后出”。队列有点象日常排队买东西的人的“队列”先牌队的人先买，后排队的人后买，即“先进先出”。有时在数据结构中还有可能出现按照大小排队或按照一定条件排队的数据队列，这时的队列属于特殊队列，就不一定按照“先进先出”的原则读取数据了。4结论所谓的栈和队列，其实是一种技术，有时候需要特殊的存储方式，然后在必要的时候还原该元素，就会利用到栈或者队列，例如在ARM操作的一些裸机代码中，需要保持状态寄存器中的值，根据需要可以利用栈或者队列来存储，用起来很方便安全，所以在涉及到存储数据之类的操作时候，要想到这两个技术。栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制（不能随机访问）：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算（访问）受限制的线性表。所谓的栈和队列，其实是一种技术，有时候需要特殊的存储方式，然后在必要的时候还原该元素，就会利用到栈或者队列，例如在ARM操作的一些裸机代码中，需要保持状态寄存器中的值，根据需要可以利用栈或者队列来存储，用起来很方便安全，所以在涉及到存储数据之类的操作时候，要想到这两个技术。参考文献[1]王红梅.数据结构[J],计算机信息科学,2005,21(1),1-4.[2]吴长刚.栈和队列的应用[D],西北工业大学博士学位论文,2006.[3]朱信宇.浅谈栈的应用[J],清华大学出版社,2005,3(1),37-39.[4]李青云.栈和队列原理与算法[M],华东大学出版社,2003.[5]杨代瑞.栈和队列的算法[M],电子工业出版社,2007.