New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

LAB Data Structures

by: Jordon Hermiston

LAB Data Structures CS 230

Jordon Hermiston

GPA 3.89


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 10 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 230 at Wellesley College taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/230947/cs-230-wellesley-college in ComputerScienence at Wellesley College.

Similar to CS 230 at

Popular in ComputerScienence


Reviews for LAB Data Structures


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
Priori ry Queues Se rs and Bags Wellesley College C8230 Lecture 12 Monday March 12 Handout 22 Exam 1 due Friday March 16 REA Overview of Today s Lec rure lt3 A T 1 More on PrioriTy Queues ordered queues in which maximal elemenT is dequeued 2 SeTs concepTually unordered collecTions of elemenTs wiThouT duplicaTes buT need order on elemenTs To implemenT efficienle 3 Bags concepTually unordered collecTions of elemenTs wiTh duplicaTes 99D PrioriTy Queues A prioriTy queue is a kind of queue in which deqfronT reTurn The highesTprioriTy elemenT where prioriTy is deTermined by a ComparaTor If comporoTor is null This indicaTes use of The noTural Comparable ordering PQueueltSTringgt pq new PQueueltTringgt Use null ComporoTor pqenq beeTlequot pqenq coTquot pqenq deerquot pqenq onTquot Dequeue highesT elemenT 0 am beelle cal deer l The greaTesT by ComparoTor While l PqiSEmpTyO SysTemouTprinTpqdeq SysTemouTprinTan deer coT beeTle onT 9 1 Specufying a PriorITy Queue ComparaTor The following meThod demonsTraTes how a pqueue depends on The ComparaTor public sTaTic void TesT PQueueltSTringgt pq PqenqquotbeeTequot pqenqquotcaTquot pqenqquotdeerquotpqenqquotanTquot while lpqisEmpTy SysTemouTprinTpqdeq quot quot SysTemouTprinTan A porTIculor pqueue ImplemenTaTIon ThaT we39ll sTudy loTer 1 PQueueTesTerTesTnew PQueueVecTorLHltSTringgt 2 PQueueTesTerTesTnew PQueueVecTorLHltSTringgtnew LengThComparaTor 3 PQueueTesTerTesT new PQueueVecTorLHltSTringgt new ComparaTor nverTerltSTringgt new ComparableComparaTorltSTringgt 4 PQueueTesTerTesT new PQueueVecTorLHltSTrinlggt new ComparaTor nverTerltSTringgt new LengT ComparaTor agUm Qg j WhaT are PriorITy Queues Good For 1 They model siTuaTions where cerTain Todoquot iTems have a higher prioriTy Than oThers Eg prinTer queue ThaT prinTs shorTer documenTs before longer ones emergency room docTor who performs Triage on paTienTs sTudenT who works on assignmenT based on due daTeimporTance 2 They can be use To sorT elemenTs public sTaTic ltTgt void pqsorT ComparaTorltTgt T elTs This is a ood idea only if an efficienT prioriTy queue implemenTaTion is use In parTicular heapsorT is an efficienT sorTin algoriThm using The heap imp lemenTaTion of a pqueue laTer T is semesTer 1275 9 1 635 A PriorITy Queue PQueue InTerface public inTerface PQueueltTgt exTends QueueltTgt public ComparaTorltTgt comparaTor ReTurns comparaTor used by This pqueue To deTermine prioriTy ReTurns null if The naTural Comparable ordering is being used public void enqT elT Add elT To This pqueue public T deq Remove and reTurn highesTprioriTy elemenT from This pqueue public T fronT ReTurn highesTprioriTy elemenT from This pqueue wiThouT removing iT public ITeraTorltTgt iTeraTor ReTurn an iTeraTor ThaT yields This pqueue39s elemenTs from highesT prioriTy To lowesT prioriTy public PQueueltTgt copy ReTurn a shallow copy of This pqueue public STring ToSTringO ReTurn sTring lisTing elemenTs of This pqueue from highesT prioriTy down InheriTs The following meThods wiTh Their usual behavior from QueueltTgt boolean isEmpTy inT size void clear A pqueue implemenTaTion should also provide Two consTrucTor meThods 1 A nullary consTrucTor meThod in which The ComparaTor is assumed null 2 A unary consTrucTor meThod explicile supplying The ComparaTor meThod agum 415 Implementing a PQueue as a Vec ror Suppose we imp lemen r a PQueue as a Vector 1 Should elemen rs be unsor red or sor red Why VecTorltSTringgt VeCTorltSTringgt O 1 2 3 0 1 2 3 Q Q Q Q bl quotdogquot ah cl 0an ball quotcalquot d 9quot 2 Should elemen rs be sorted lowTohigh or highTolow Why VecTorltSTringgt 2 VecTorltSTringgt 1 2 i r39 dog E0 3E j 0 0 LO 0 Q 039 Q O 3 Q Q l E FE an rquot b r39 c D D 99KB DATA PQueueVec rorLH Cons rruc ror Me rhods TRU Represen r a pqueue as a vec ror of elemen rs from low ro high priori ry public class PQueueVecTorLHltTgt implemen rs PQueueltTgt Ins rance Variables priva re Vec rorltTgt el rs S rores sor red elemen rs priva re Compara rorltTgt comp Remembers compara ror Consfrucfor Me39rhods public PQueueVec rorLHCompara rorltTgt comp Thisel rs new VecTorltTgt Thiscomp comp public PQueueVec rorLH Thisnull null means To use IIna ruralII Comparable ordering Ins rance Methods 90 here 99B 423 PQueueVecTor LH Easy InsTance MeThods One brand new insTance meThod39 public ComparaTorltTgt compar39aTor39O r39eTur39n comp MosT insTance meThods like Those in backTofr39onT queue public T deq if elTssize 0 Throw new RunTimeExcepTionquotATTempT To deq empTy pqueuequot else r39eTur39n elTsr39emoveelTssize1 public T from if elTssize 0 Throw new RunTimeExcepTionquotATTempT To Take fr39onT of empTy pqueuequot else r39eTur39n elTsgeTelTssize1 public boolean isEmpTy r39eTur39n elTssize 0 public inT size r39eTur39n elTssize public void clear39 elTs new VecTor39ltTgt copy iTer39aTor39 and ToSTr ingO are also like in backTofr39onT queue 3Wquot Tm PQueueVecTor LH Enqueumg public void enq T elT Her39e use near search for39 inser39Tion Could use binar39y sear39ch insTead buT inser39Tion will generally be linear39 anyway due To elemenT shifTing in vecTor39 inT i elTssize 1 while i gt 0 ampamp compareelT elTsgeTi lt 0 Loop invar39ianT39 all sloTs in elTs aT indices gt i hold values gr39eaTer39 Than elT Iquot Invar39ianT i in range 1elTssize 1 is lar39gesT i such ThaT all sloTs wiTh indices gr39eaTer39 Than i conTain values gr39eaTer39 Than elT elTsaddi1elT 12710 WTquot hm PQueueVecTorLH Comparing ElemenTs privaTe inT compareT x T y if com null Assume ThaT x is an insTance of Comparable reTurn Comparable xcompareToy A ClassCasTExcepTion will be Thrown if This assumpTion is violaTed NoTe The Java 15 compiler will issue an unchecked warning for The above line because iT cannoT prove ThaT The downcasT will succeed else reTurn compcomparexy fTurbakpuma queue javac PQueueVecTorLHjava NoTe PQueueVecTorLHjava uses unchecked or unsafe operaTions NoTe Recompile wiTh XlinT39unchecked for deTails fTurbakpuma queue javac XlinT39unchecked PQueueVecTorLHjava PQueueVecTorLHjava29 warning unchecked unchecked call To compareToT as a member of The raw Type javalangComparable reTurn Comparable xcompareToy M 1 lt6 TA Using InheriTance To Simplify ImplemenTaTion ImplemenTs QueueltTgt using vecTor of elemenTs arranged from back To fronT ImplemenTs PQueueltTgt using vecTor of elemenTs arranged from low To high prioriTy Can inheriT The The following from QueueVecTorBF public T deq public T fronT public boolean isEmpTyO public boolean size public boolean clear public ITeraTorltTgt iTeraTor PQueueVecTorLH musT sTill implemenT The following ConsTrucTor meThods public ComparaTorltTgt comp new To PQueueltTgt public void enq T elT inserTs in sorTed order public PQueueltTgt COPYO has differenT reTurn Type public STring ToSTring has differenT name QueueVecTorBF 12712 99 5 Can Even Inherl r ToS rrIngO public class QueueVecTorBFltTgt implemen rs QueueltTgt public S rring roS rring S rringBuffer buff new S rringBufferO buff appendname quotquot code for lis ring elemen rs from fron r ro back buff appendquotquot re rurn buff roS rring public S rring name can be overridden by PQueueVec iorLH re rurn quotQueueVec rorBFquot public class PQueueVecTorLHltTgt ex rends QueueVecTorBFltTgt implemen rs PQueueltTgt public S rring name overrides name in QueueVec rorBF re rurn quotPQueueVec rorLHquot o rher me rhods go here 1213 9K1 EMA ImplemenTing PrioriTy Queues as a MuTable LisT TRU We could instead implemen r a Priority Queue using a mu139able list How should elements be arranged What is The code for enq deq fron r 12714 99D DATA PrioriTy Queues ImplemenTaTion Summary TRU Using vecTors or lisTs all prioriTy queue operaTions can be implemenTed efficienle excepT for enq 0 ConsTrucTor meThods fronT deq size isEmp lYO Clear Take consTanT Time 0 copy ToSTring and iTeraTor Take Time linear in number of elemenTs iTeraTor can be changed To consTanT Time 0 enq Takes Time linear in number of elemenTs BAD 12715 9U llM MaThemaTical SeTs I Rd In maThemaTics a seT is an unordered collecTion of elemenTs wo duplicaTes A seT is wriTTen by enumeraTing iTs elemenTs beTween braces Eg The empTy seT wiTh no elemenTs is wriTTen InserTion inserTs an elemenT inTo a seT if iT39s noT already There inserT aquot D quotaquot inserT b quotaquot quotaquot bquot quotbquot quot0quot order is irrelevanT inSerI139lla l Haul Ilbll Haul Ilbll quotle Hall inSerI139llc l Ialllllbll Haul b IICH Haul CHI Ilbll quotle all IICH quotle C Hall IICHI all Ilbll IICHI b Hall DeleTion removes an elemenT if iT39s in The seT deleTe aquot D deleTe aquot Haul llbll II bu deleTellb l Halli llbll Hall deleTellc l Halli Ilbll Haul Ilbll Size CardinaliTy ISI is The number of elemenTs in S IClall uaul ubu uaul bu llcll 12716 9K1 More Sefs Membership x E S is True if x is in The set S and false o rherwise Ilaquot E Ilaquot E Haul Ilbll C E Haul Ilbll Subsef 1 2 is True if all elemenfs in 51 are also in 52 l g quotaquot bquot is True quot0quot g quotaquot bquot is True bquot g quotaquot bquot is True quotaquot bquot g quotaquot bquot is True quotaquot bquot g quotaquot is false quotaquot g l is false Union 51 U 52 all elemen rs in of leasf one of 1 and 2 quotaquot equot U quotbquot fquot quotaquot quotequot fquot Infersecfion 1 SZ all elements in a r bofh 1 and 2 quotaquot equot O quotbquot fquot quotbquot dquot Difference 51 52 or 5152 all elemen rs in 51 fhaf are no r in 52 quotaquot equot quotbquot fquot quotaquot equot 1217 9U gillA j Mafhemafical Bags MulTiSefs TRU In ma rhemafics a bag mulTisef is an unordered collecfion of elemenfs wi l39h duplicafes A bag is wriffen by enumerafing ifs elemen rs wifh duplicafes be rween braces Eg fhe emp ry bag wifh no elemen rs is wrif ren U The bag wifh one a is wri r ren quotaquot aquot The bag wifh fwo aquots is wrif ren quotaquot aquot Mosf sef nofions inserfion delefion membership subsef union in l39ersecfion difference cardinalify generalize 139o bags as long as duplica res are accounfed for Eg inser r aquot quotaquot bquot quotaquot bquot quotaquot aquot bquot aquot dele re aquot quotGquot quotaquot quotaquot b Cquot CHD quot0quot Cl quotbquot Cquot Cquot quotaquot bquot g quotaquot bquot True quotaquot bquot g quotaquot bquot false quotaquot dquot u quotaquot quotdquot equot quotaquot d d equot quotaquot cquot m quotaquot bquot quotaquot bquot quotaquot cquot quotaquot bquot quotaquot cquot Ilalll all all bu cu llcll 6 1218 95R RAl j New Bag OperaTions l2 MulTipliciTy39 we shall wriTe xB my nonsTandard noTaTion for The number of occurrences of elemenT x in bag B aka The mulTipliciTy of x in B Ilalll a l all b C IICHI aquot BI 3 bquot Bl 1 cquot Bl 2 dquot Bl O DeleTeAll deleTexB deleTes one occurrence of x from B SomeTimes we wanT To deleTe all occurrences of x from B For This we use deleTeAllxB deeella l Haul all all b C IICH Hall Illaquot b C IICH deleTeAlla l Haul all all b C IICH Hle CH IICH deleTeAlld l Haul all all b C IICH Haul all all b C IICH CounTDisTincT39 IBI counTs all elemenT occurrences in B including duplicaTes SomeTimes we wanT jusT The number of disTincT elemenTs For This we use counTDisTincTB Ilalll an an b quotCquot llcll 6 counTDisTincT aquot quotaquot quotaquot quotbquot quotcquot cquot 3 1219 9U EAM j Digression Ordered SeTs and Bags TRU SeTs and bags are unordered collecTions of elemenTs However we can also have ordered noTions of seTs and bags in which The order of elemenTs maTTers The order mighT be specified by a ComparaTor or The Comparable compareTo meThod in which case elemenTs would have a welldefined index For insTance in The ordered bag OBCIGHI all all b C IICH aquots are aT indices 0 1 2 quotbquot is aT index 3 and cquots are aT indices 4 amp 5 Since elemenTs have a welldefined index we could requesT The elemenT aT a given index or deleTe The elemenT aT an index from an ordered seTbag InserTing elemenTs inTo or deleTing elemenTs from an ordered seTbag can shifT The indices of oTher elemenTs similar To whaT happens in a vecTor We will noT consider implemenTaTions of ordered seTs or bags This semesTer 12720 10


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.