本次美国代写是C++数据结构和算法相关的的一个assignment

Introduction

Forourfourthprojectwe’llbeimplementingtheDeque(double-endedqueue)ADT.ADequeisageneralization

ofaqueuethatallowsforenqueueing/dequeueingfromboththefrontandbackofthequeue(Figure1).

Acoupleofpointstonote:

1. YoumustimplementtheADTdequebyusingadynamicarraytocontaintheitemsinthedeque;average

complexitymustbe O(1) withworstcase O(n).

2. The array implementation will feature dynamic memory. The default constructor will create a deque

capableofstoring64items.Oncethecapacityisexceededyoumustimplementanarraygrowingstrategy

thatdoublesthesizeofthearray.

3. Youmustfollowtheruleofthree.

Asalways,youneedtowriteunittestsforyourclass.

1 The Deque Class

Thefile abstract_deque.hpp inthestatercodedefinesthetemplatedinterface,AbstractDeque. Youshould

defineatemplateDequethatpubliclyinheritsfromtheinterfaceintheheaderfile Deque.hpp.Thistemplate

shouldoverridethefollowingmethodsfromtheinterface(see abstract_deque.hpp fordetails)

• isEmpty

• pushFront

• popFront

• front

• pushBack

• popBack

• back

YouwillneedtodefinethemethodsandimplementallmethodsintheDeque.hpp/.txxfile.Youshouldadd

appropriatecommentblockstoeachmethod,aswell.Youwillneedtowritetestsinthe student_tests.cpp

usingtheCatchtestingframework,asdescribedinclass.TheincludedCMakeLists.txtfilesetsupeverything

foryou.Justgenerateyourbuilddirectoryforyourdevelopmentenvironmentasdescribedinthecoursework-

flowtutorial.

2 Grader

Wewillbeusinganautomaticgradertohelpyoudetermineyourassignment’scompletenessandcorrectness.

Aportionofeachassignmentgradewillbedeterminedbythenumberofpassingtestsasdeterminedbythe

autograder,withourevaluationfillingintherest.Thismeansyouknowbeforeyouturninyoursubmissionthat

alliswell.Youcansubmittotheautograderasmanytimesasyoulike,butitisratelimited(fivesubmissions

everyhour)tokeepyoufromusingitasyourcompiler.Seethiscanvasforasummaryofhowtousethegrader

(NoteisisnotWebCAT,whichmanyofyoumaybefamiliarwith).

For this assignment you should upload a zip file containing only the files: Deque.hpp, Deque.txx and

student_tests.cpp.Thereisabuildtargetcalled“submission”configuredbydefaulttocreatethisfilewith

thecorrectcontentsinyourbuilddirectory.

3 Submission

Onceyouaresatisfiedwithyourcode,uploadazipfilecontaining(only)Deque.hpp,Deque.txxandstudent_tests.cpp

throughCanvasattheassignmentlink. Youshouldnotsubmittheotherfilesfromthestartercode,noryour

build directory. There is a build target called “submission” configured by default to create this file with the

correctcontentsinyourbuilddirectory.

4 Grading

Thereare40pointsallocatedtothisassignment.

• Correctlysubmittingtherequiredfiles:2points

• Yourtestscompile:3points

• Yourtestspass:10points(proportional)

• Instructortestscompilewithyourcode:3points

• Instructortestspass:15points(proportional)

• Notestsleakmemory:2points

• Designrequirementsmet(e.g.,codeandtestquality,comments):5points

Asperthesyllabus,goodfaitheffortsmustbemadetowritecomprehensivetests.Sincethereisnowayto

testforthisatcompileorruntime(atthispoint),shouldthegrader(person)deemyourteststobewoefully

lackingyouwilllosenotonlydesignpointsbutalsothepointsgivenbytheautograder. Eachmethodshould

betested.