Data Structures
CSE 2221
Queues
The Queue is a data structure which is very common in computer science. It allows you to manipulate a series of entities in FIFO (First in first out) order.
There is also a Queue component in the OSU CSE Components library.
The best way to think of a Queue is people in a line (which is actually called a queue in British English). The first person in line, is the first person that gets to leave the line. The is exactly how queues where first element added is the first element to be taken off hence it being FIFO.
Queue Component
The queue component has a few different methods
QueueKernel<T> Methods
void enqueue(T t)- Adds an item to the queue.
T dequeue()- Removes the top item from the queue.
int length()- Returns the number of items in the queue.
Queue<T> Methods
T front()- returns the oldest entry in
this. T replaceFront()- replaces the front of
thisand returns the value of the old front void append(Queue<T> q)- appends another queue
qto the end ofthis, and clearsq. void flip()- flips the order of the elements in
this. void sort(Comparator<T> order)- Sorts
thisbased on the way defined inorder. void rotate(int distance)- Rotates
thisfordistanceelements.
A Queue<T> can be declared in the following way, where T represents the type of the elements in the queue:
Queue<Integer> = new Queue1L<Integer>();
Sets
A Set is most basically an unordered collection of unique elements. Because all the elements are unique, there can’t be any duplicate elements.
Sets are also unordered meaning that the ordering of the elements in a set dosen’t matter
Mathematical Set Notation
A set can be a collection of zero or more elements of some type \(T\). We call this a finite set of \(T\).
- A set cannot have any duplicates
- There is no order to the elements
An empty set with no elements is denoted by \({ }\). As elements are added, they become comma separated inside of the curly brackets i.e. \({ 1, 4, 3 }\).
Membership
Because a set has elements inside of it, we have notation for identifying which elements are inside of a set. If an element is in a set it is a member of that set.
Union
A union of two sets, is a combination of all the elements in each set.
- \(\{1, 2\} union \{2, 3\} \rightarrow \{1, 2, 3\}\)
Intersection
The intersection of two sets are the elements that only appear in both sets.
- \(\{1, 2\} \cap \{2, 3\} \rightarrow \{2\}\)
Difference
The difference of two sets are the elements that don’t appear in both.
Subsets
Sets can be subsets of another set if all the elements of one set appear in another set. They are a Proper subset if they don’t equal each other.
Set Component
There is a component of OSU CSE Components called Set<T> which represents this mathematical model, where T represents the type of the elements in the set.
Set<T> Methods
void add(T x)- Adds
xtothis. T remove(T x)- Removes
xfromthisand returnsx. Whenxis a reference, it is removed based on value not reference. T removeAny()- Removes and returns an arbitrary element from
this. However this is not a random value. boolean constains(T x)- returns
trueifxis inthis. int size()- Returns the size of
this void add(Set<T> s)- Adds to
thisall of the elements ofsthat are not already inthisand removes those elements froms. Set<T> remove(Set<T> s)- removes the elements of
sthat appear inthisand returns a set containing the removed elements. boolean isSubset(Set<T> s)- Checks whether
thisis a subset ofs.
Sequence
A sequence is similar to an array but it can have a ther
SequenceKernel<T> interface methods
void add(int pos, T x)- adds
xat positionposofthis. T remove(int pos)- removes the element at position
posofthisand returns it. int length()- returns how many elements are in
this.
Sequence<T> class methods
T entry(int pos)- returns the element of
thisat positionpos. T replaceEntry(int pos, T x)- replaces the entry at position
posofthiswithx, returns the previous element. void append(Sequence<T> s)- concatenates
sto the end ofthisand clearss.sandthismust be of the same typeT. void flip()- “flips” the order of
this. void insert(int pos, Sequence<T> s)- add the Sequence
sto the positionposofthisand clearss.sandthismust have the same typeT. void extract(int pos1, int pos2, Sequence<T> s)- sets
sto the sequence frompos1topos2and removes it fromthis.
Genome Reassembly from Fragments
Stacks
Stacks are a LIFO (last in first out) data structure.
StackKernel Methods
void push(T x)- adds
xto the top ofthis. T pop()- pops off the top element of
thisand returns it. int length()- returns the amount of elements in
this
Stack1L Methods
T top()- returns the top element of
thiswithout actually removing it fromthis. T replaceTop(T x)- returns the top element of
thisand replaces it withx. void flip()- flips/reverses
this.
Map
The Map data structure assigns a key to a value. Maps are one-to-one meaning that every key only has one value.
Component
MapKernel Methods
void add (K key, V value)- Adds the pair (
key,value) tothis. Map.Pair<K,V> remove(K key)- Removes the pair at
keyofthis. Map.Pair<K,V> removeAny()- Returns an arbitrary pair from
this, however it doesn’t do this randomly like Set. V value(K key)- Returns the value of the corresponding
keyinthis. boolean hasKey(K key)- Reports whether the
keyexists inthis. int size()- Returns the size of
this. V replaceValue(K key, V value)- Replaces the value at
keywithvalueand returns the old value.
Map1L Methods
K key(V value)- Returns a corresponding key of
value. boolean hasValue(V value)- Reports whether
valueexists inthis. void combineWith(Map<K, V> m)- Combines
mwiththis. boolean sharesKeyWith(Map<K,V> m)- Reports with
thisandmhave any keys in common.