6 - Stack

A Stack is a collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO (see NIST-DADS' definition of stack). We may think a stack is a cramp storage area, where the first item going in, will certainly last to comes out.

Basic operation of stack are :

1. push
2. pop

The program bellow is an example of simple stack operation :

#include "iostream"
using namespace std;

#define n 10
int Stack[n]; //declaring a stack
int Top; //declaring the Top index of a stack
int i; //general counter

void initialize(void)
{
Top = -1;
}

int stillunfilledup(void)
{
if (Top < n-1) //stack is not full yet
{
return 1;
}
else
{
return 0;
}
}

void push(int X)
{
Top =Top +1;
Stack[Top] = X;
}

int notempty(void)
{
if (Top > -1)
{
return 1;
}
else
{
return 0;
}
}

int pop()
{
int X=Stack[Top];
Top = Top -1;
return X;
}


int main(void)
{
int X;
int i;

initialize();


cin >> X;
while (X != 9999) //loop for pushing. As long as the user do not input 999, the loop runs
{
if (stillunfilledup()) //stack is not full yet
{
push(X);
}
else //stack is full
{
cout << "Stack is full";
break;
}
cin >> X;
}

cout << endl << endl << endl;
for (i = 0; i < n; i++)//loop for popping
{
if (notempty())
{
X = pop();
cout << "Pops the " << Top+1 << " th member" << X << endl;
}
else
{
cout << "empty";
}
}
}

5 - Sorting Algorithm : Shell Sort

Another sorting algorithm is Shell Sort. It is based on insertion sort. This sorting method performs multiple passes through the array. Every time it passes the array it performs insertion sort. It divide the arry into several sets. A set grows every time the algorithm works on the array. Of course we need to understand that each members' location is not adjacent to each other (NOT CONTIGOUS). I will present two Shell sort alogoritms : one is for ascending sort and the other is for descending sort :

The first one is ascending sort :
#include "iostream"
using namespace std;

int main(void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;
int increment;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

increment = 3;
while (increment > 0)
{
for (i=0; i < 8; i++)
{
j = i;
temp = data[i];
while ((j >= increment) && (data[j-increment] > temp))
{
data[j] = data[j - increment];
j = j - increment;
}
data[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

And here is for descending sort :
#include "iostream"
using namespace std;

int main(void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;
int increment;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

increment = 3;
while (increment > 0)
{
for (i=0; i < 8; i++)
{
j = i;
temp = data[i];
while ((j >= increment) && (data[j-increment] < temp))
{
data[j] = data[j - increment];
j = j - increment;
}
data[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

4 - Sorting Algorithm : Insertion Sort

Another sorting algorithm that we can use is insertion sort. We can use it for doing ascending or descending sorting :

1. If we need to do ascending sort, then we need to compare two elements : if we find an element whose value is greater than temp place its value to right.
2. If we need to do descending sort, then we need to compare two elements : if we find an element whose value is less than temp place its value to right.

First we have a program Insertion Sort - Ascending :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] > temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we are presented with Insertion Sort - Descending :

#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 1; i < 8; i++)
{
temp = data[i];
j = i-1;
while ((j >= 0) && (data[j] < temp))
{
data[j+1] = data[j];
j = j-1;
}
data[j+1] = temp;
}
cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}
return 0;
}

Next we will discuss Shell Sort

3 - Sorting Algorithm : Selection Sort

The code below is an example of Selection Sort - ascending. It ascending sorts an array :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 0; i < 8; i++)
{
int k = i;
for (j = i + 1; j < 8; j++)
{
if (data[j] < data[k]) // Ascending Sort
{
k = j;
}
}
int t = data[i];
data[i] = data[k];
data[k] = t;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

Next we have descending sort :
#include "iostream"
using namespace std;

int main (void)
{
int data[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int k;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

for (i = 0; i < 8; i++)
{
int k = i;
for (j = i + 1; j < 8; j++)
{
if (data[j] > data[k]) //descending sort
{
k = j;
}
}
int t = data[i];
data[i] = data[k];
data[k] = t;
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << data[i];
}

return 0;
}

2 - Sorting Algorithm : Bubble Sort

One of the algorithm for sorting is Bubble Sort. It is called bubble sort because the way it sorts is like bubble in a glass of soda. The smallest integer will "bubble up" after the sorting. The program bellow is an example of such algorithm. It ascending sorts the array.

#include "iostream"
using namespace std;

int main (void)
{
int arrInt[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}

for (j=0; j<8;j++)
{
for (i = 0; i < 7; i++)
{
if (arrInt[i] > arrInt[i+1])
{
temp = arrInt[i];
arrInt[i] = arrInt[i+1];
arrInt[i+1] = temp;
}
}
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}
}


Next we have another example descending sort :

#include "iostream"
using namespace std;

int main (void)
{
int arrInt[8] = {5, 6, 3, 4, 8, 9, 2, 1};
int i;
int j;
int temp;

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}

for (j=0; j<8;j++)
{
for (i = 0; i < 7; i++)
{
if (arrInt[i] < arrInt[i+1])
{
temp = arrInt[i];
arrInt[i] = arrInt[i+1];
arrInt[i+1] = temp;
}
}
}

cout << endl;
for (i = 0; i < 8; i++)
{
cout << arrInt[i];
}
}

The bubble sort algorithm is arguably one of the easiest algorithm to memorize even though it is not particularly efficient. Therefore next we are going to explore another sorting algorithm : Selection Sort for sorting an array in ascending and descending manners.

5 - Import statements generated by netbeans inside "*View.java"

These are the list of import statements generated by netbeans when we build desktop database application. These statements are placed inside *View.java (which is a user interface class) :

1. import org.jdesktop.application.Action; Marks a method that will be used to define a Swing Action object's actionPerformed method. It also identifies the resources that will be used to initialize the Action's properties. Additional @Action parameters can be used to specify the name of the bound properties (from the same class) that indicate if the Action is to be enabled/selected, and if the GUI should be blocked while the Action's background Task is running.
2. import org.jdesktop.application.ResourceMap; A read-only encapsulation of one or more ResourceBundles that adds automatic string conversion, support for field and Swing component property injection, string resource variable substitution, and chaining.
3. import org.jdesktop.application.SingleFrameApplication;
4. import org.jdesktop.application.FrameView; A View encapsulates a top-level Application GUI component, like a JFrame or an Applet, and its main GUI elements: a menu bar, tool bar, component, and a status bar. All of the elements are optional (although a View without a main component would be unusual). Views have a JRootPane, which is the root component for all of the Swing Window types as well as JApplet. Setting a View property, like menuBar or toolBar, just adds a component to the rootPane in a way that's defined by the View subclass.
5. import org.jdesktop.application.TaskMonitor; This class is intended to serve as the model for GUI components, like status bars, that display the state of an application's background tasks. TaskMonitor provides an overview of all the ApplicationContext's Tasks, as well as the state of a single foreground Task.
6. import org.jdesktop.application.Task; A type of SwingWorker that represents an application background task. Tasks add descriptive properties that can be shown to the user, a new set of methods for customizing task completion, support for blocking input to the GUI while the Task is executing, and a TaskListener that enables one to monitor the three key SwingWorker methods: doInBackground, process and done.
7. import java.awt.event.ActionEvent; A semantic event which indicates that a component-defined action occurred. This high-level event is generated by a component (such as a Button) when the component-specific action occurs (such as being pressed). The event is passed to every every ActionListener object that registered to receive such events using the component's addActionListener method.
8. import java.awt.event.ActionListener; The listener interface for receiving action events. The class that is interested in processing an action event implements this interface, and the object created with that class is registered with a component, using the component's addActionListener method. When the action event occurs, that object's actionPerformed method is invoked.
9. import java.util.ArrayList;
10. import java.util.List;
11. import javax.persistence.RollbackException; Thrown by the persistence provider when the EntityTransaction.commit() fails.
12. import javax.swing.Timer;
13. import javax.swing.Icon;
14. import javax.swing.JDialog;
15. import javax.swing.JFrame;
16. import javax.swing.event.ListSelectionEvent;
17. import javax.swing.event.ListSelectionListener;
18. import org.jdesktop.beansbinding.AbstractBindingListener; An abstract subclass of BindingListener that simplifies writing BindingListeners by allowing you to extend this class and re-implement only the methods you care about.
19. import org.jdesktop.beansbinding.Binding; A factory class for creating instances of the concrete Binding implementations provided by this package.
20. import org.jdesktop.beansbinding.PropertyStateEvent; An event characterizing a change in a Property's state for a particular source object.
    

Recursion - Basic

Recursion
An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task. To be short it is a function that calls itself. NIST-DADS states that a recursive function consists of two major parts or cases, the second part having three components.
1.base case(s), in which the problem is simple enough to be solved directly, and
2.recursive case(s). A recursive case has three components:
1.divide the problem into one or more simpler or smaller parts of the problem,
2.call the function (recursively) on each part, and
3.combine the solutions of the parts into a solution for the problem.
Depending on the problem, any of these may be trivial or complex.
To make us understand what sort of algorithm this technique is, lets have a look at the code bellow :
#include
using namespace std;
void RecursiveIncrement(int i)
{
if (i ==10) //Base case : display value of i if i == 10
{
cout << i;
}
else //Recursive case : display value of i
{
cout << i << endl;
RecursiveIncrement(++i);
}
}

int main(void)
{
RecursiveIncrement(1);
return 0;
}
The program above display integer values from 1 to 10. The base case display the value of i if its value is 10. The recursive case display the values from 1 to 9.
We have another example of such algorithm. The program work just like the previous program except that it will display the value of 10 to 1. The source code is presented below :

#include
using namespace std;

void RecursiveDecrement(int i)
{
if (i == 1)
{
cout << i;
}
else
{
cout << i << endl;
RecursiveDecrement(--i);
}
}

int main(void)
{
RecursiveDecrement(10);
return 0;
}

Those two programs are fairly simple. We are going to explore the usage of recursion to navigate several type of data list.