《浅谈栈和队列》由会员分享，可在线阅读，更多相关《浅谈栈和队列（7页珍藏版）》请在金锄头文库上搜索。
1、浅谈栈和队列摘要：栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必 须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插 入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。关键词:栈和队列；数据结构；线性表；抽象数据类型Stack and QueueAbstract: Stack as a kind of data structure, it is a kind of can in the end of the insert and delete operation of the special lin
2、ear list. Queue is a special kind of linear list, it is allowed only in the front of the table (front) to delete operation, but in the table after end (rear) insertion operation. For insertion operation of the end called rear, to delete operation of the end called team head. The queue no element, ca
3、lled empty queue.Key words： Stack and queue ;Data structure ; Linear list; Abstract data type0引言栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。队列是一种特殊的线性表，它只允许 在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。在队列这种数据结构中，最先插 入的元素将是最先被删除的元素:反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出” (FIFO一first in first out.)的线性表。1栈1.1栈的逻辑结构栈的逻辑结构和我们先前
4、学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有 一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继)，但是栈的运算规则与线性 表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一 端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO 表(Last In First Out).1. 2栈的顺序存储结构及实现由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈TT顺序栈和链栈两种存储结构，这两种 存储结构的不同，则使得实现栈的基本运算的算法也有所不同。#
5、includestruct node int data;node *next;；class LinkStack public:LinkStack()top=NULL; 11构造函数置空链栈LinkStack();析构函数，释放链栈中个节点的存储空间void Push(int x); 将元素 x 进栈int Pop。; 将栈顶元素出栈int GettopO 获取栈顶元素(if(top! =NULL)retum top-data; 取栈顶元素(并不删除)bool cmptyO 判断链栈是否为空栈(if(top=NULL)return 1;elsereturn 0;private:node *top
6、; /栈顶指针即链栈的头指针；void LinkStack:Push(int x) 元素进栈(node *s=new node; 申请一个数据域为x的节点s s-data=x;s-next=top; /将节点s插在栈顶top=s;int LinkStack:Pop() 元素出栈(int x;if(top=NULL) throw下溢”；x=top-data; /暂存栈顶元素node *p=top; /将栈顶节点摘链 top=top-ncxt;delete p;return x;LinkStack:LinkStack() 析构函数将链栈中所有节点的存储空间释放while(top)(node *p=
7、top-next;delete top;top=p;void niain()(LinkStack link;int data;cout请输入进栈的10个元素:”;for(int i=0;i10;i+) /输入进栈的10个元素(cindata;link.Push(data);link.Pop(); /栈顶元素出栈cout现在栈顶的元素为:”vvlink.Gettop()vvendl; 输出栈顶元素while。link.empty。)cout现在出栈的是:”vvlink.Pop()vcndl; 所有元素一个一个出栈L3顺序栈和链栈的比较实现顺序栈和链栈的所有基本操作的算法都只能需要常数时间，因此唯
8、一可以比较的是空间性能。初始 时顺序必须确定一个固定的长度，所以rr存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只 有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指钊域，从而产生了结构性开销。所以当 栈的使用过程中元素个数变化较大时，用链栈适宜。反之，应该采用顺序栈。2队列2.1队列的逻辑结构队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear),允许插入 的一端称为队头(Front)，队列的操作原则是先进先出的，所以队列又称作FIF
9、O表(First In First Out)o2. 2队列的存储结构及实现队列的顺序存储结构：假设线性表有个n数据兀素，顺序表要求把表中的所TT元素都存储在数组的前n 个单元。假设队列有n个元素，顺序存储的队列也应该把队列的所有元素都存储在数组的前个单元。如果把 附着元素放在数组中下标为0的一端，则入队操作的时间开销公为0(1),此时的入队操作相当于追加，不 需要移动元素：但是出队操作的时间开销为0 3)。队列的链接存储结构：队列的链接存储结构称为链队列。链队列是在单链表的基础上做了简单的修改，为了 使空队列和非空队列的操作一致，链队列也加上头结点。根据队列的先进先出特性，为了操作上的方便，设
10、 置附着指针指向链队列的头结点，附属指针指向终端结点。循环队列的实现Const int QueueSize=100;TemplateClass CirQucuc(Public:cii*Queue() front=rear=QueueSize-1;cirQucuc() Void EnQueue(DataType x);DataType DeQueue();DataType GetQueue();Int Empty() front=rcar?rcturn I:return 0;Private:DataType dataQueueSize;Int front,rear;队列的链接存储结构的实现Tem
11、plate class DataTypOClass LinkQueue(Public:LinkQucucO;linkQueue。；Void EnQueue(DataType x);DataType DcQucuc();DataTypc GctQucuc();Int Empty() (front=rear?return 1: return 0;Private:Node*front,*rear;2.3循环队列和链队列的比较顺序队列一次性要分配大量保证够用的空间，效率较高，因为是基于数组的，长度也是固定的。可以实 现变长，但是-般代价较高。链表队列基于链表的，要动态创建和删除节点，效率较低，但是可以
12、动态增长。 3栈和队列的区别栈和队列都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用。不同的是，栈 就象一个很窄的桶先存进去的数据只能最后才能取出来，而且队列则不一样，即“先进后出”。队列有点象FI 常排队买东西的人的“队列”先牌队的人先买，后排队的人后买，即“先进先出二有时在数据结构中还有可 能出现按照大小排队或按照一定条件排队的数据队列，这时的队列属于特殊队列，就不一定按照“先进先出” 的原则读取数据了。4结论所谓的栈和队列，其实是一种技术，有时候需要特殊的存储方式，然后在必要的时候还原该元素，就会利 用到栈或者队列，例如在ARM操作的一些裸机代码中，需要保持状态寄存
13、器中的值，根据需要诃以利用栈或 者队列来存储，用起来很方便安全，所以在涉及到存储数据之类的操作时候，要想到这两个技术。栈和队列 是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制(不能随 机访问)：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算(访问)受限制 的线性表。所谓的栈和队列，其实是一种技术，有时候需要特殊的存储方式，然后在必要的时候还原该元素, 就会利用到栈或者队列，例如在ARM操作的一些裸机代码中，需要保持状态寄存器中的值，根据需要可以利 用栈或者队列来存储，用起来很方便安全，所以在涉及到存储数据之类的操作时候，要想到这两个技术。参考文献1王红梅.数据结构J,计算机信息科学,2005, 21 (0,1-4.吴长刚.栈和队列的应用D,西北工业大学博士学位论文,2006.3朱信宇.浅谈栈的应用J,清华大学出版社,2005, 3(1), 37-39.4李青云.栈和队列原理与算法M,华东大学出版社,2003.5杨代瑞.栈和队列的算法。，电子工业出版社,2007.
