Tutorial: Stack & Queue Algorithm Analysis

HelloWorld · #1 (**permalink**) 07-21-2007, 09:27 AM

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);
      }
    }
}

HelloWorld · #2 (**permalink**) 07-21-2007, 09:28 AM

TestMain.java - MAIN METHOD (Get all of the Time)

PHP Code:

  import java.util.Random;


public class TestMain {
    public static void main(String[] args) {
        
        int n = 10;
        
        Queue q = new Queue();
        Stack s = new Stack();
        VectorQueue vq = new VectorQueue();
        VectorStack vs = new VectorStack();
        
        double t1 = 0, t2 = 0, r = 0;
        boolean passed = false;
        
        // ENQUEUE & PUSH
        
        for (int i = 0; i < n; i++) {
            if (!passed) {
                t1 = System.nanoTime();
            }
                q.queue(i);
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("ARRAY QUEUE - ENQUEUE: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            s.push(i);
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("ARRAY STACK - PUSH: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vq.enqueue(i);
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR QUEUE - ENQUEUE: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vs.push(i);
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR STACK - PUSH: " + r);
                passed = true;
            }
        }
        
        System.out.println();
        passed = false;
        // PEEK
        
        for (int i = 0; i < n; i++) {
            if (!passed) {
                t1 = System.nanoTime();
            }
            s.peek();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("ARRAY STACK - PEEK: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vs.peek();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR STACK - PEEK: " + r);
                passed = true;
            }
        }
        
        System.out.println();
        passed = false;
        // DEQUEUE & POP
        
        for (int i = 0; i < n; i++) {
            if (!passed) {
                t1 = System.nanoTime();
            }
                q.dequeue();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("ARRAY QUEUE - DEQUEUE: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            s.pop();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("ARRAY STACK - POP: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vq.dequeue();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR QUEUE - DEQUEUE: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vs.pop();
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR STACK - POP: " + r);
                passed = true;
            }
        }
        
        System.out.println();
        passed = false;
        // SORTED STACK
        Random random = new Random();
        int range = 100;
        VectorSortedStack vss = new VectorSortedStack();
        VectorSortedQueue vsq = new VectorSortedQueue();
        for (int i = 0; i < n; i++) {
            if (!passed) {
                t1 = System.nanoTime();
            }
            vss.push(random.nextInt(range));
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR SORTED STACK: " + r);
            }
            if (!passed) {
                t1 = System.nanoTime();
            }
            vsq.enqueue(random.nextInt(range));
            if (!passed) {
                t2 = System.nanoTime();
                r = t2 - t1;
                System.out.println("VECTOR SORTED QUEUE: " + r);
                passed = true;
            }
        }
    }
}

My Result: (Will be various)

Code:

ARRAY QUEUE - ENQUEUE: 594577.0
ARRAY STACK - PUSH: 5483.0
VECTOR QUEUE - ENQUEUE: 10013.0
VECTOR STACK - PUSH: 6660.0

ARRAY STACK - PEEK: 2396.0
VECTOR STACK - PEEK: 6818.0

ARRAY QUEUE - DEQUEUE: 9540.0
ARRAY STACK - POP: 3202.0
VECTOR QUEUE - DEQUEUE: 9063.0
VECTOR STACK - POP: 5902.0

VECTOR SORTED STACK: 32148.0
VECTOR SORTED QUEUE: 29111.0

IMPORTANT:
To my class mates: Don't just copy and paste!!!
Don't blame and sue me if you get an F, getting fired, or whatever problem that you may have by using my codes. Use it at your own risk

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode