IB Computer Science/Abstract Data Structures and Algorithms
Return to IB Computer Science
Abstract Data Structures and Algorithms
editFundamentals
editStatic data structures
editYou 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() {
// valid Java or JETS statements may be placed here...
output("The answer is: " + d);
}
You may want to change the Class name, in which case, remember that:
the file name must be the same as the class name with the extension .java the constructor name must be the same as the class name. you ought to change the comments to reflect what your program does.
Stack in an array
An array is going to be used to hold a sequence of characters:
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[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:
Allocate the item to stack[size] then move size up one in the array Allocate the item to stack[0] and increment size by 1
It should be apparent that the second option involves shuffling up elements whereas the first only requires the stack pointer to be moved.
Given:
private static final int SIZE = 12; // a constant for the stack size private char[] stack = new char[SIZE]; // the array to hold the stack private int size = 0; // the number of items in the stack
A possible push operation is:
// method to push an item onto the stack
public void push(char item)
{
stack[size] = item;
size = size + 1;
}
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 {
private static final int SIZE = 12; // a constant for the stack size private char[] stack = new char[SIZE]; // the array to hold the stack private int size = 0; // the number of items in the stack
// Constructor
public Stack()
{
size = 0;
char c;
do
{
c = inputChar("Input a character ('/' to end)");
push(c);
display();
} while (c != '/');
}
// method to push an item onto the stack
public void push(char item)
{
if (size < SIZE)
{
stack[size] = item;
size = size + 1;
}
else
{
output("Stack full");
}
}
public void display()
{
output("stack");
output("=====");
for(int p = (size - 1); p >= 0; p--)
{
output(p + ":> " + stack[p]);
}
output("=====");
}
// Main method for class stack
public static void main(String[] args)
{
new Stack();
}
//============================================================
// Below are the IBIO simple input and output methods
// to be included in the Class.
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:
String s = input("Please input a String");
for (int p = 0; p < s.length(); p++)
{
char c = s.getChar(p);
// process c
To concatenate characters into a String try something like:
String s; char c; s = s + c; // string s with char c added at the end (concatenated)
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 ).
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[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 {
private static final int SIZE = 12; // a constant for the queue size private char[] queue = new char[SIZE]; // the array to hold the queue private int front = 0; // the first item in the queue private int rear = 0; // the last item in the queue
// Constructor
public Queue()
{
front = 0;
rear = 0;
char c;
do
{
c = inputChar("Input a character ('/' to end)");
enqueue(c);
display();
} while (c != '/');
}
public void enqueue(char item)
{
if (rear < SIZE)
{
queue[rear] = item;
rear = rear + 1;
}
else
{
output("Queue full - cannot add item");
}
}
public void display()
{
output("front");
output("=====");
for(int p = front; p < rear; p++)
{
output(p + ":> " + queue[p]);
}
output("=====");
}
// Main method for class queue
public static void main(String[] args)
{
new 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:
c = inputChar("Input a character ('/' to end, '#' to dequeue)");
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
s
s
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 {
private static final int SIZE = 12; // a constant for the queue size
private char[] queue = new char[SIZE]; // the array to hold the queue
private int front = 0; // the first item in the queue
private int rear = 0; // the last item in the queue
private boolean qFull = false; // flag
private boolean qEmpty = true; // nothing in the queue initially
// Constructor
public Queue()
{
front = 0;
rear = 0;
qFull = false;
qEmpty = true;
char c;
do
{
c = inputChar("Input a character ('/' to end, '#' to dequeue)");
if ( (c != '/') && (c !='#'))
{
enqueue(c);
}
else if (c == '#')
{
dequeue();
}
display();
} while (c != '/');
}
public void enqueue(char item)
{
if (qFull)
{
output("Queue full - cannot add item");
}
else
{
queue[rear] = item;
rear = (rear + 1) % SIZE;
qFull = (rear == front);
qEmpty = false;
}
}
public void dequeue()
{
if (qEmpty)
{
output("Empty queue");
}
else
{
char c = queue[front];
front = (front + 1) % SIZE;
output("dequeued: " + c);
qFull = false;
qEmpty = (front == rear);
}
}
public void display()
{
output("front");
output("=====");
for(int p = front; p != rear; p = (p + 1) % SIZE)
{
output(p + ":> " + queue[p]);
}
output("=====");
}
// Main method for class queue
public static void main(String[] args)
{
new 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.
Dynamic data structures
editObjects in problem solutions
editRecursion
editExample (Java):
public static int factorial(int num) {
int ans;
if(num !== 1) {
ans = factorial(num-1) * num;
}
return ans;
}
This is a simple code to represent the value of factorial.
Algorithm Evaluation
editEfficiency of Algorithms
editTo 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 , 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( ). 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 is very large and is increased. For instance, if a certain algorithm takes milliseconds for each item of data, it will still have a Big O notation of O( ). 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( ) for bubble and selection sort and O( ) for binary search. Note that binary search’s Big O notation is instead of , because logarithms of different bases increase in approximately the same way when is large.
