# IB Computer Science/Abstract Data Structures and Algorithms

Return to IB Computer Science

# Abstract Data Structures and Algorithms
## Static data structures

You should be able to compile these examples in any Java editor, such as BlueJ or JCreator. All of the examples assume that the IBIO methods exist in the file.
An example class using these methods is found here . Make sure you can compile and run this source code if you want to implement any of the examples given in these pages.
Any code you want to try out should be placed in the Constructor:
* Constructor for objects of class Adams
public Adams {
You may want to change the Class name, in which case, remember that:
Stack in an array
An array is going to be used to hold a sequence of characters:
[10]
[11] stack
Initially, a pointer, size , is set to 0, so stack[size] is the next available element. To push an item onto the stack we can work one of two ways:
It should be apparent that the second option involves shuffling up elements whereas the first only requires the stack pointer to be moved.
Given:
A possible push operation is:
Which works up to a point. Is there any check that needs to be done? Add it.
So far, the code might look like this:
* Class Stack
* Implements a stack of Characters
* Uses an array - is a static data structure
public class Stack {
Exercises
Write the method pop, to remove an item from the stack - being sure to watch out for underflow (when there are not any items on the stack).
Write the algorithm which reverses a character String in place (a discussion of this is found on the previous page). To take an input String and split it into characters, you might need something like:
To concatenate characters into a String try something like:
A useful method, top, returns the top element from the stack, if it exists, without popping it. Implement this.
Queue in an array
We have seen a possible way of implementing a queue using a linked list , but this section is concerned with static data structures. So let's see how we might go about using the same array as above, except that we will need two pointers into the array, front and rear.
Recall the items are added at the rear ( enqueued ) and removed from the front ( dequeued ).
[10]
[11] queue
It seems reasonable to have both front and rear point to element 0 initially. To enqueue an item, place it at rear then increment rear to point at the next free location.
Check to see if the end of the array has been reached:
* Class Queue
* Implements a stack of Characters
* Uses an array - is a static data structure
public class Queue {
//============================================================ // Below are the IBIO simple input and output methods
Exercise
Implement the dequeue method, be sure to test if there is anything in the queue to remove.
You might want to change the Constructor to allow the dequeue to be called:
You can either return a character from the dequeue method or output it within the method body.
Once you have got that working, there are a few problems here - try adding asnd removing enough items and we get to a point where the rear pointer has run up against the end of the array, yet there is still space at the front of the array:
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11] queue
f
a
d space which is unused/wasted
front
rear
So, what we need to do is wrap the front pointer around to the start again.
However, we have to be able to detect when the queue is full , when the rear pointer catches up with the front pointer.
There are several ways to deal with this problem, the simplest of which is probably to maintain a special flag qFull which we will set true when the front reaches the rear and unset whenever we dequeue an item.
It is also possible to use a qEmpty flag in a similar way.
* Class Queue
* Implements a stack of Characters
* Uses an array - is a static data structure
public class Queue {
//============================================================ // Below are the IBIO simple input and output methods
Exercises
Write self-contained Queue Class that can enque and dequeue Strings or other Objects of your own choosing.
The Class should implement Exception handling so that EmptyQueue, FullQueue and other custom exceptions can be thrown.
Additional methods mught be getFront, getRear to examine, but not remove these items. A method to return the current size of the queue would also be useful.

## Recursion

Example (Java):
This is a simple code to represent the value of factorial.

## Algorithm Evaluation
### Efficiency of Algorithms

To optimize algorithms, one must first know whether a certain algorithm is better or worse than another one. In this case, better can mean that the algorithm processes data faster or that less RAM is used. To measure data processing speed, one can use Big O notation.
Big O notation is always in the form of O(expression). The expression inside the parentheses is different for different efficiencies. It almost always contains $n$, the number of items of data to be processed. The Big O notation of a linear search on an array (of size n) is O($n$). This means that doubling the array size will, on average, double the time for the linear search to complete.
Big O notation does not, however, indicate exactly how efficient an algorithm is. It only indicates how much the time spent increases when $n$ is very large and is increased. For instance, if a certain algorithm takes $0.5n+2$ milliseconds for each item of data, it will still have a Big O notation of O($n$). This is because when n gets to, say, one trillion, the added 2 will have almost no effect, so it is discarded. In the same way, all coefficients of n are discarded.
Other examples of Big O notation include O($n^{2}$) for bubble and selection sort and O($\log n$) for binary search. Note that binary search’s Big O notation is $\log n$ instead of $\log _{2}n$, because logarithms of different bases increase in approximately the same way when $n$ is large.