Hello everybody, back again to HelloWorld's tutorial on Java
In this tutorial, we basically going to analyze
Stack and
Queue's algorithms that's going to be implemented differently using both Vectors and Arrays. As we learned before in
Tutorial: Simple Algorithm Analysis
ArrayList and Vector are actually types of Data Structure that uses the fundamental Arrays. Then you probably may be able to guess what's the underline Data Structure for Stacks and Queues too!!! Guess what, Stack and Queues are actually use VECTOR as their underline data structure!!! Why Vector not ArrayList?? The answer is I don't know, and should probably ask Sun for that
In this tutorial, we're going to analyze different run-time when we implement our Stack and Queues using Vector, and Arrays. How long does it take time to
POP,
PEEK, and
PUSH? How long does it take to
ENQUEUE and
DEQUEUE? as well as the SORTED version too
P.S we're going to create our own version of
Stacks and
Queues. If you don't know about this, below is a little intro:
Stacks and Queues are actually just other type of Data Structures that we have in Java. Here are the difference between them:
Stacks
You're washing dishes and have 10 plates (doesn't have to be 10, whatever number you have for your plates) and you stack them together once you're done washing them. IF you are going to use the plate, then of course you're not going to bother to get it from the bottom, so you will get the plate that's on the top. So is the same with Stacks, and in Computer Science, we call Stacks as
LIFO (Last In First Out) Data Structure
Queues
You're about to watch movie, I hope that you don't cut the people in front of you because they will get mad!!! So, you have to wait in line (it's called queue in UK if I'm not wrong) if you get to be the first person in line, you will be the first one that gets the ticket and get out of the line. So, it is the same with Queues, and in Computer Science, we call Queues as
FIFO (First In First Out) Data Structure
Hopefully that little introduction gives you some little more background about Stacks and Queues. I see that those two stories work best for me to understand Stacks and Queues, so that's the best that I can come up with. However, feel free to add and ask questions.
Also, hope that my code below is self explanatory. It's really, straight forward. You can see the way I implement different things there using Arrays and Vector. I believe that programmers are reading codes better than bunch of paragraphs
Stack.java - ARRAYS IMPLEMENTATION PHP Code:
public class Stack {
private int size = 10;
private Object o[] = new Object[size];
private Object temp[] = new Object[size];
private int pos = 0;
public void push(Object in) {
if (pos == size-1) {
for (int i = 0; i < o.length; i++) {
temp[i] = o[i];
}
o = new Object[2*size];
size *= 2;
for (int i = 0; i < temp.length; i++) {
o[i] = temp[i];
}
}
o[pos] = in;
pos++;
}
public Object pop() {
return o[pos-- - 1];
}
public Object peek() {
return o[pos];
}
}
Queues.java - USING ARRAYS IMPLEMENTATION
PHP Code:
public class Queue {
private int size = 10;
private Object o[] = new Object[size];
private Object temp[] = new Object[size];
private int pos = 0;
private Object temp2[] = new Object[size];
public void queue(Object in) {
if (pos == size-1) {
for (int i = 0; i < o.length; i++) {
temp[i] = o[i];
}
o = new Object[2*size];
size *= 2;
for (int i = 0; i < temp.length; i++) {
o[i] = temp[i];
}
}
o[pos] = in;
pos++;
}
public Object dequeue() {
for (int i = 0; i < temp2.length; i++) {
temp2[i] = o[i];
}
o = new Object[size-1];
for (int i = 1; i < temp2.length; i++) {
o[i-1] = temp2[i];
}
return temp2[0];
}
}
VectorStack.java - USING VECTOR IMPLEMENTATION
PHP Code:
import java.util.Vector;
public class VectorStack {
private Vector<Object> v = new Vector<Object>();
public void push(Object i) {
v.add(i);
}
public Object pop() {
return v.remove(v.size() - 1);
}
public Object peek() {
return v.get(v.size() - 1);
}
}
VectorQueue.java - USING VECTOR IMPLEMENTATION
PHP Code:
import java.util.Vector;
public class VectorQueue {
private Vector<Object> v = new Vector<Object>();
public void enqueue(Object i) {
v.add(i);
// insert at beginning
// v.add(0, i);
}
public Object dequeue() {
return v.remove(0);
// remove from end
// return v.remove(v.size() - 1);
}
}
VectorSortedQueue.java - USING VECTOR IMPLEMENTATION
(Sorry, this is only for Integers)
PHP Code:
import java.util.Vector;
public class VectorSortedQueue {
private Vector<Integer> v = new Vector<Integer>();
public void enqueue(Integer i) {
v.add(i);
sort();
// insert at beginning
// v.add(0, i);
}
public Object dequeue() {
return v.remove(0);
// remove from end
// return v.remove(v.size() - 1);
}
public void sort() {
VectorSelectionSort(v);
}
// Selection Sort Vector
public void VectorSelectionSort(Vector<Integer> v)
{
int i, j;
int min, temp;
for (i = 0; i < v.size()-1; i++)
{
min = i;
for (j = i+1; j < v.size(); j++)
{
if (v.get(j) < v.get(min))
min = j;
}
temp = v.get(i);
v.set(i, v.get(min));
v.set(min, temp);
}
}
}
VectorSortedStack.java - USING VECTOR IMPLEMENTATION
(This one also only for Integers)
PHP Code:
import java.util.Vector;
public class VectorSortedStack {
private Vector<Integer> v = new Vector<Integer>();
public void push(Integer i) {
v.add(i);
sort();
}
public Object pop() {
return v.remove(v.size() - 1);
}
public Object peek() {
return v.get(v.size() - 1);
}
public void sort() {
VectorSelectionSort(v);
}
// Selection Sort Vector
public void VectorSelectionSort(Vector<Integer> v)
{
int i, j;
int min, temp;
for (i = 0; i < v.size()-1; i++)
{
min = i;
for (j = i+1; j < v.size(); j++)
{
if (v.get(j) < v.get(min))
min = j;
}
temp = v.get(i);
v.set(i, v.get(min));
v.set(min, temp);
}
}
}