Integer Stack
Updated on June 26th, 2021 at 1:04 am
What is it?
This was a program that I made for my advanced Java course in my junior college. I thought it was interesting because it creates the concept of a virtual stack in memory without implementing or extending actual Java Stack classes. Instead, I create my own.
The StackInt class that I created was essentially a reverse-engineered representation of the IntStack package offered by Sun Microsystem’s Apache-Utility library. This is why if you look at the VirtualMachine.java file, you will notice that the import for IntStack package as well as its instantiation are commented out (since it is replaced with my own “StackInt” class).
What does it do?
A stack is a data structure that works under the Last-In-First-Out (LIFO) principle. Data can be added to the end of a stack and/or removed from the beginning of the stack. This type of data structure is commonly used in system-level programming when you are dealing with fixed-sized data storage in memory. Java (being a high-level language) does not require you to work with actual memory, but the Stack data structure can still be used in Java for other purposes.
The concept of the program is to essentially create a fixed-sized array that works like a stack. Inside the array are numbers that correlate to a variety of instructions that can be performed on integers. In a more useful application, these numbers could be specified outside the application source code, but in this example, the array is created in the main function. Each instruction may use methods from the StackInt class to manipulate the stack. These methods may look familiar if you have worked with stacks before (methods like push, pop, and peek).
As I’ve mentioned before, the numbers that you specify in the array correlate to a variety of integer operations. This means that there is a fixed set of numbers that you can use in the array and any numbers outside of that set will result in an invalid instruction. The numbers are as follows:
- 0: Halt – End the program.
- 8: Constant – An integer that will be used as an input to one or more instructions. If this is used, the following number will represent an actual constant (meaning it will not be parsed as an instruction). Once specified, the number cannot be changed.
- 9: Load – Retrieve a constant from a specific address. If this is used, the following number will represent the index of the memory address (meaning it will not be parsed as an instruction). The address is not a real memory location, so any integer will do.
- 10: Store – Store a constant in a specific address. If this is used, the following number will represent the index of a memory address (meaning it will not be parsed as an instruction). The address is not a real memory location, so any integer will do.
- 11: Add – Add the last two specified constants together.
- 12: Subtract – Subtract the second-to-last constant from the last specified constant.
- 13: Multiply – Multiply the last two specified constants together.
- 14: Divide – Divide the second-to-last constant by the last constant.
- 15: Equality – Determine if the last two constants are equal and if so, return the number 1. If not, return 0.
- 16: Less – Determine if the second-to-last constant is less than the last constant and if so, return 1. If not, return 0.
- 17: More – Determine if the second-to-last constant is more than the last constant and if so, return 1. If not, return 0.
- 18: Jump – Change the program counter to a different number. This is useful if you want to skip instructions.
- 19: False Jump – Change the program counter to a different number only if the stack is empty.
- 21: Write – Print the last integer in the stack. This could be the result of an operation if one was specified.
In the VirtualMachine.java file, I created a memory array in the main method with 20 specific numbers in it. See below:
int[] memory = {
8,5, //const 5
8,2, //const 2
11, //add
10,16, //store at address 16
9,16, //load from address 16
21, //write
0, //halt
0,0,0,0,0,0,0,0,0,0,0,0
};The numbers are 8, 5, 8, 2, 11, 10, 16, 9, 16, 21 and 13 0s. If you match the number to each instruction, you’ll see that I created 2 constants (5 and 2), added them together, stored the result at address 16, loaded the value from address 16, printed the value, and then stopped the program.
The result is shown below:
7 Program halted by halt instruction
How does it work?
VirtualMachine.java
The class is named VirutalMachine because it is supposed to act as a very simple operating system for a very small block of memory. Inside the Virtual Machine, a new stack is created from a fixed-sized block of memory. The VM is assigned a program counter that will increment up after every instruction. The class also includes the method FetchDecodeExecute which interprets all of the integers in the memory array as either instructions or constants, and executes the appropriate stack operations accordingly.
Lastly, the class includes the main method which specifies the actual values of the memory array and calls the VM’s FetchDecodeExecute method to actually run the program.
//import com.sun.org.apache.xml.internal.utils.IntStack;
public class VirtualMachine {
//private IntStack stack = new IntStack(20);
private StackInt stack = new StackInt(20);
private int pc;
private int ir;
private int[] memory;
public VirtualMachine(int[] memoryArray) {
pc = 0;
this.memory = memoryArray;
}
public void FetchDecodeExecute() {
int d, x, y;
do {
ir = memory[pc]; //fetch
pc++; //increment the program counter
switch(ir){
case 0: //Halt
System.out.println("Program halted by halt instruction");
System.exit(0);
break;
case 8: //Constant
d = memory[pc]; //get constant from memory
pc++; //increment the program counter
stack.push(d); //store the constant on stack
break;
case 9: //Load
stack.push(memory[memory[pc]]);
pc++;
break;
case 10: //Store
memory[memory[pc]] = stack.pop();
pc++;
break;
case 11: //Add
y = stack.pop();
x = stack.pop();
d = x + y;
stack.push(d);
break;
case 12: //Subtract
y = stack.pop();
x = stack.pop();
d = x - y;
stack.push(d);
break;
case 13: //Multiply
y = stack.pop();
x = stack.pop();
d = x * y;
stack.push(d);
break;
case 14: //Divide
y = stack.pop();
x = stack.pop();
d = x / y;
stack.push(d);
break;
case 15: //Equality
y = stack.pop();
x = stack.pop();
if (x == y) stack.push(1);
else stack.push(0);
break;
case 16: //Less
y = stack.pop();
x = stack.pop();
if (x < y) stack.push(1);
else stack.push(0);
break;
case 17: //More
y = stack.pop();
x = stack.pop();
if (x > y) stack.push(1);
else stack.push(0);
break;
case 18: //Jump
pc = memory[pc];
break;
case 19: //False Jump
if (stack.pop() == 0) pc = memory[pc];
break;
case 21: //Write
System.out.println(stack.pop());
break;
default:
System.out.println("Invalid Instruction");
System.exit(0);
break;
}
} while(true);
}
public static void main( String [] args ) {
int[] memory = {
8,5, //const 5
8,2, //const 2
11, //add
10,16, //store at address 16
9,16, //load from address 16
21, //write
0, //halt
0,0,0,0,0,0,0,0,0,0,0,0
};
VirtualMachine vm = new VirtualMachine(memory);
vm.FetchDecodeExecute();
}
}StackIntOperations.java
This is not a class, but actually an interface. It lays out the methods that need to be written in order for a stack to be usable. The reason it is an interface is so that when I write the StackInt.java file, I’ll implement the StackIntOperations interface, thus forcing me to address those methods listed. It is a clean way to demonstrate the methods that make up a stack.
public interface StackIntOperations
{
public void push(int e);
public int pop();
public int peek();
public boolean isEmpty();
public boolean isFull();
public int size();
}StackInt.java
This file is the meat and bones of what makes a stack work. My assignment in this Java course was to replicate the IntStack package offered by the Sun Microsystem’s Apache Utility library. Though the source code may have been readily available, my job was to figure the code out myself. The stack operations file layed out the methods that I needed to write. I just had to figure out what they meant and how to build them.
push()takes an integer and adds it to the top of the stack.pop()removes the integer at the top of the stack.peek()inspects the integer at the top of the stack.isEmpty()determines if the stack is empty.isFull()determines if the stack has at least one value in it.size()returns the exact size of the stack (i.e: how many values are in it).toString()converts all of the data to a single string that can be printed.
public class StackInt implements StackIntOperations {
private int[] stack;
private int sp;
public StackInt() {
stack = new int[10];
sp = -1;
}
public StackInt( int s ) {
stack = new int[s];
sp = -1;
}
public void push(int e) {
if ( !isFull() ) { // check for stack space
sp++; // advance stack pointer
stack[sp] = e; // put element on stack
} else { // stack is full
System.out.println("Attempt to push to a full stack");
System.exit(0);
}
}
public int pop() {
int rv = 0; // return value
if ( !isEmpty() ) {// check for data on stack
rv = stack[sp]; // copy data out of stack
sp--; // reduce stack pointer
} else { // stack is empty
System.out.println("Attempt to pop an empty stack");
System.exit(0);
}
return rv;
}
public int peek() {
int rv = 0; // return value
if ( !isEmpty() ) {// check for data on stack
rv = stack[sp]; // copy data out of stack
} else {
System.out.println("Attempt to peek an empty stack");
System.exit(0);
}
return rv;
}
public boolean isEmpty() {
return sp == -1;
}
public boolean isFull() {
return sp == stack.length - 1;
}
//returns the number of active elements on the stack
public int size() {
return sp+1;
}
public String toString() {
String rv = "sp->";
// top item -> bottom item
for(int i = sp; i >= 0; i--) {
rv = rv + stack[i] + " ";
}
return rv;
}
}