cLOGONOIP基础数据结构江涛队列、栈、堆概念与应用yourfamilysiteyoursitehereLOGO目录栈栈队列队列堆堆3数组数组124目录yourfamilysiteyoursitehereLOGO数组的特性数组的特性数组•数组(array)的元素(element)或项(item)的类型是相同的•数组的大小是固定的、静态的、连续的•数组对某元素的存取是O(1)时间•数组的插入、删除操作是O(n)时间yourfamilysiteyoursitehereLOGO“订制”数组“订制”数组数组•由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。•常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。•注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用。yourfamilysiteyoursitehereLOGO栈(stack)的图示栈(stack)的图示栈yourfamilysiteyoursitehereLOGO栈的特性栈的特性栈•信息学中的栈一般就是用数组实现•栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的•栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间•栈有一个计数器counter或栈顶指针yourfamilysiteyoursitehereLOGO栈的实现样例Pascal代码栈的实现样例Pascal代码栈constmaxn=1000;varstack:array[1..maxn]ofinteger;counter:integer;Procedurepush(x:integer);begin//入栈inc(counter);stack[counter]:=x;end;functionpop():integer;begin//出栈pop:=stack[counter];dec(counter);end;yourfamilysiteyoursitehereLOGO栈的实现样例C++代码栈的实现样例C++代码栈constintmaxn=1000;intstack[maxn],counter=0;voidpush(intx)//入栈{stack[++counter]=x;}intpop()//出栈{returnstack[counter--];}yourfamilysiteyoursitehereLOGO栈的常见应用举例栈的常见应用举例栈•括号匹配---判断字符串({[]}(){({{[()]}})}是否括号匹配•运算表达式---计算表达式3*(5-(2-3)*(6+5))+8*5•回溯的非递归写法•凸包的graham扫描算法yourfamilysiteyoursitehereLOGO队列(queue)的图示队列(queue)的图示队列yourfamilysiteyoursitehereLOGO队列的特性队列的特性队列•信息学中的队列一般也用数组实现•队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的•队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间•队列有队头front和队尾back两个指针，一般也有个计数器counteryourfamilysiteyoursitehereLOGOconstmaxn=1000;varqueue:array[1..maxn]ofinteger;front,back,counter:integer;procedurepush(x:integer);begininc(counter);inc(back);//这样的话front,back初始化为1,0queue[back]:=x;end;functionpop():integer;beginpop:=queue[front];inc(front);dec(counter);end;队列的实现样例Pascal代码队列的实现样例Pascal代码队列yourfamilysiteyoursitehereLOGOconstintmaxn=1000;intqueue[maxn],counter=0,front=0,back=-1;voidpush(intx){queue[++back]=x;++counter;}intpop(){--counter;returnqueue[front++];}队列的实现样例C++代码队列的实现样例C++代码队列yourfamilysiteyoursitehereLOGO由于front和back一直向后移动，有可能counter不大，但back却超过maxn，而引起数组越界。数组实现队列的可能缺点数组实现队列的可能缺点队列………frontbackyourfamilysiteyoursitehereLOGO在保证countermaxnthenfront:=1;同样的，每次back:=back+1;后加上ifback>maxnthenback:=1;队列的”循环数组”方案队列的”循环数组”方案队列yourfamilysiteyoursitehereLOGO队列的常见应用举例队列的常见应用举例队列1、宽度优先搜索（BFS）。2、单调队列：a)有n(n<1000000)个数排成一行，找出一段长度为L(1
