NOIP基础数据结构_栈、队、堆

《NOIP基础数据结构_栈、队、堆》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOIP基础数据结构江涛队列、栈、堆概念与应用目录栈队列堆3数组124目录数组的特性数组数组(array)的元素(element)或项(item)的类型是相同的数组的大小是固定的、静态的、连续的数组对某元素的存取是O(1)时间数组的插入、删除操作是O(n)时间“订制”数组数组由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用。栈(s

2、tack)的图示栈栈的特性栈信息学中的栈一般就是用数组实现栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间栈有一个计数器counter或栈顶指针栈的实现样例Pascal代码栈constmaxn=1000;varstack:array[1..maxn]ofinteger;counter:integer;Procedurepush(x:integer);begin//入栈inc(counter);stack[counter]:=x;e

3、nd;functionpop():integer;begin//出栈pop:=stack[counter];dec(counter);end;栈的实现样例C++代码栈constintmaxn=1000;intstack[maxn],counter=0;voidpush(intx)//入栈{stack[++counter]=x;}intpop()//出栈{returnstack[counter--];}栈的常见应用举例栈括号匹配---判断字符串({[]}(){({{[()]}})}是否括号匹配运算表达式---计算表达式3*(5-(2-3)*(6+5))+8*5回溯的非递

4、归写法凸包的graham扫描算法队列(queue)的图示队列队列的特性队列信息学中的队列一般也用数组实现队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间队列有队头front和队尾back两个指针，一般也有个计数器counterconstmaxn=1000;varqueue:array[1..maxn]ofinteger;front,back,counter:integer;procedurepush(x:integer);

5、begininc(counter);inc(back);//这样的话front,back初始化为1,0queue[back]:=x;end;functionpop():integer;beginpop:=queue[front];inc(front);dec(counter);end;队列的实现样例Pascal代码队列constintmaxn=1000;intqueue[maxn],counter=0,front=0,back=-1;voidpush(intx){queue[++back]=x;++counter;}intpop(){--counter;returnq

6、ueue[front++];}队列的实现样例C++代码队列由于front和back一直向后移动，有可能counter不大，但back却超过maxn，而引起数组越界。数组实现队列的可能缺点队列………frontback在保证countermaxnthenfront:=1;同样的，每次back:=back+1;后加上ifback>maxnthenback:=1;队列的”循环数组”方案队列队列的常见应用举例队列1、宽度优先搜索（BFS）。2、单调队列

7、：a)有n(n<1000000)个数排成一行，找出一段长度为L(1