課件章雙端隊(duì)列349de5c9

2011-3-13.53.43.33.22011-3-13.53.43.33.2ADT3.13.1?雙端隊(duì)列：deque(3.1?雙端隊(duì)列：deque(double-?與向量類與向量不同的?2011-3-2抽象數(shù)據(jù)類型雙端size()：抽象數(shù)據(jù)類型雙端size()：雙端隊(duì)列的長度empty()：測(cè)試雙端隊(duì)列是否為空capacity()：雙端隊(duì)列的容resize(n)：重置雙端隊(duì)列的容量（5）=：賦值運(yùn)算front()：雙端隊(duì)列首元素back()：雙端隊(duì)列尾元素 (x)：雙端隊(duì)列首插入元素ADT雙端隊(duì)???????????????（9）()：刪除雙端隊(duì)列首元素push_back(x)：雙端隊(duì)列尾插入元素pop_back()：刪除雙端隊(duì)列尾元素begin()：指向雙端隊(duì)列首的迭代器end()：指向雙端隊(duì)列尾的下一位置的迭代器（14）()：所有元素按位置的先后次序輸2011-3-3雙端隊(duì)列的實(shí)現(xiàn)方?雙端隊(duì)列的實(shí)現(xiàn)方?考慮使用數(shù)組實(shí)需要Ω(n)的時(shí)間（無法令人滿意??實(shí)現(xiàn)目在O(1)時(shí)間實(shí)現(xiàn)push_front考慮其他實(shí)現(xiàn)方法?2011-3-4用循環(huán)數(shù)組實(shí)現(xiàn)雙端用循環(huán)數(shù)組實(shí)現(xiàn)雙端?問題：如何實(shí)現(xiàn)循環(huán)數(shù)組使用%2011-3-5隊(duì)首與隊(duì)尾游隊(duì)首與隊(duì)尾游三種常用的first/last游標(biāo)2011-3-6隊(duì)列中已有3隊(duì)列中已有3個(gè)元素的三種表示方?2011-3-7AlgorithmsandDataAlgorithmsandData2011-3-8AlgorithmsandDataAlgorithmsandData空2011-3-9解決辦法解決辦法?(b√被約2011-3-福州大學(xué)數(shù)學(xué)與計(jì)算雙端隊(duì)列類???雙端隊(duì)列類?????????????????deque{deque(intsize=0,constT&value=T());/~deque(){if(start)delete[]start;}deque&operator=(constdeque<T>&rhs);//賦值運(yùn)算voidpush_back(constT&item);/雙端隊(duì)列尾插入元素voidpop_back();//刪除雙端隊(duì)列尾元素voidpush_front(constT&item);/voidpop_front();2011-3-T*start;/intfirst;//intlast;/intmaxsz;intsz;//雙端隊(duì)列首插入運(yùn)雙端隊(duì)列首插入運(yùn)template<classvoiddeque<T>::push_front(constT&??????{已滿時(shí)容量擴(kuò)大1elseif(sz==maxsz-1)reserve(2*maxsz,true);first=(first+maxsz-1)%maxsz;???}2011-3-刪除雙端隊(duì)列首元?jiǎng)h除雙端隊(duì)列首元template<classvoid???????{if(sz==0)throwout_bounds();first=(first+1)%maxsz;}2011-3-雙端隊(duì)列尾插入元雙端隊(duì)列尾插入元template<classvoiddeque<T>::push_back(constT&??????????{elseif(sz==maxsz-容量擴(kuò)大1}2011-3-刪除雙端隊(duì)列尾元template刪除雙端隊(duì)列尾元template<classvoid???????{last=(last+maxsz-1)%}2011-3-雙端隊(duì)列的迭代?雙端隊(duì)列的迭代????2011-3-內(nèi)部類????????iterator{內(nèi)部類????????iterator{iterator(intj=0,T*a=0,intsz=0):i(j),arr(a),maxsz(sz){}//構(gòu)造函T&operator*(){return*(arr+i);}//提領(lǐng)運(yùn)iterator&operator++(){i=(i+1)%maxsz;return*this;}//前置遞iteratoroperator++(int)//后置遞{iteratortmp=*this;i=(i+1)%maxsz;returniterator&operator--(){i=(maxsz+i-1)%maxsz;return前遞??????iteratoroperator--(int)//2011-3-intmaxsz,i;//迭代器位T*arr;//雙端隊(duì)列數(shù)???iterator???iteratorbegin(){returnconst_iteratorbegin()const{returniteratorend(){returnconst_iteratorend()const{return???2011-3-應(yīng)用?雙端隊(duì)列應(yīng)用?雙端隊(duì)列的簡單應(yīng)?簡單多邊形的凸2011-3-雙端隊(duì)列的簡單應(yīng)?????雙端隊(duì)列的簡單應(yīng)??????????????????#include<string>#include"deque.h"#include"algo.h"int{deque<string>str.push_back("string");str.push_back("string");str.push_back("string");str.push_back("laststring");str.push_front("firststr.pop_front();str.pop_back();for(inti=1;i<str.size();i++)str[i]="another"+str[i];str.resize(4,"resizedstring");}2011-3-#include<iostream>#include<string>#include<deque>#include<algorithm>#include<iterator>usingnamespace測(cè)試結(jié)果輸測(cè)試結(jié)果輸?????????laststringanotherstringanotherresized2011-3-簡單多邊形簡單多邊形的凸2011-3-Melkman??Melkman??q0,q1,,且 ??點(diǎn)2011-3-頂點(diǎn)在凸殼內(nèi)部的充頂點(diǎn)在凸殼內(nèi)部的充要條藍(lán)色點(diǎn)vector<point>left_front(q)&&??2011-3-新凸殼上的2新凸殼上的2個(gè)支撐2011-3-核心算法描convex_hull(vector<point>?????????核心算法描convex_hull(vector<point>???????????????{逆時(shí)針序逆時(shí)針序}}2011-3-for(itervit=p.begin()+3;it!=p.end();it++){//依次考察剩余pointif(left_front(q)&&left_back(q))continue;//q在凸殼內(nèi)部while(!left_front(q))dq.pop_front();//前端點(diǎn)在凸殼內(nèi)部dq.push_front(q);//在前端插入點(diǎn)qdq.push_back(q);//在后端插入點(diǎn)q平面上點(diǎn)point的實(shí)#include平面上點(diǎn)point的實(shí)#include#include"vector.h"#include書上未給???typedefdeque<point>::iteratoriter;deque<point>dq;2011-3-classpoint(doublexx=0,doublevoidprint_point(ostream& ★紅色部分代voidpoint::print_point(ostream&{out<<x<<"}ostream&operator<<(ostream&out,constpoint&{x.print_point(out);return判定P2與P0P1判定P2與P0P1的相對(duì)位inlinedoubleleft(pointp0,pointp1,point{return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-}inlineboolleft_front(point{iterit=dq.begin();returnleft(p0,p1,p)>0;}inlineboolleft_back(point{iterit=dq.end()-1;returnleft(