Stacks

[chili5]

Stacks

A stack is a container class that allows retrieval of items by order of insertion. The order this class follows is a last-in, first-out order. This means that the last item added is the first item returned.


Stack object

In Java the stack object is located in the java.util package. So you must import java.util.Stack to use the class. The Stack inherits from java.util.Vector to get methods such as "add", "remove" and all the methods in the Vector class.

Constructors

Stack s = new Stack();

There is only one constructor for the Stack class. It creates an empty Stack.

Methods

Various methods exist to do things like:

1. Check if the stack is empty
2. Look at the top object of the stack
3. Return the last object at the top of the stack. Remove it from the stack.
4. Add an item to the top of the stack
5. Locate where an item is in the stack

These methods are: peek(), pop(), empty(), push(Object 0Item), search(Object OItem)

The empty method checks if the stack is empty.

For our example, we have a stack that contains three elements. Run this code:

Stack s = new Stack();
s.add(new Integer(5));
s.add("Hello");
s.add(new Integer(50));

This code is just to set up our example. The stack using the inherited add method, adds 3 items to the stack. An integer, a String and another integer.

Now for the example:

We have a stack of three items as defined above, we want an int method to return the top item of the stack * 2
if the top item is an integer, otherwise return -1. This is a rather simple problem. Take a peek() at the top
item and see what type it is. Then we can push() it off the stack, and return it. However if the stack is
empty we want to print "Stack Empty".

So first the peek method, it returns type Object. So you may need to use the wrapper classes. Also if the stack
is empty the method throws an EmptyStackException. So it seems like you would need an isInteger method for this.
I couldn't find the equivalent of is_int() in Java, so I made myself a little method. You need to copy this just outside of your main method.

public static boolean isInteger(Object o) {
        try {
            int nNum = (Integer)(o);
            return true;
        } catch (Exception e) {
            return false;
        }
    }

Don't need to be too concerned about this. But basically if Java cannot convert the object to an Integer an exception is thrown and we return false (not an integer), otherwise return true (an integer).

So for my comparison method:

public static int topItem(Stack s) {
        if (isInteger(s.peek())) {
            return 2 * (Integer)(s.pop());
        }
        return -1;
}

The stack is passed and if the last item is an integer we pop it off the stack using the pop() method and return
that value multiplied by 2. If it can't convert to an integer we return -1. Not a very difficult method. The important thing to note is that the pop method returns an Object type. So you have to convert it to something useful.

Now in main:

         if(!s.empty()) {
		int nTop;
        	nTop = topItem(s);
        	System.out.println(nTop);
	} else {
		System.out.println("Stack empty");
	}

Since the last item in the Stack is an integer "50" when represented as an Object on the stack can be converted to an integer, so the output is:

50

Now add this line:

s.add("I like Pancakes");

just under the line below in your code:

s.add(new Integer(50));

Then run the file again and you will notice that the output is -1. Why? This is because a String cannot be
converted to an Integer.

Now delete this section of code:

        s.add(new Integer(5));
        s.add("Hello");
        s.add(new Integer(50));
        s.add("I like Pancakes");

and run the file again. Now notice that since the stack is empty, we get a message: "Stack Empty" printed.

Adding elements

Now I have been using the add method to add elements to the stack. The add method is inherited from the Vector

class. However the push method can also be used to add an element to the top of the stack.

So right at the top of main add this:

s.push(new Integer(5));
s.push("Hello");
s.push(new Integer(50));

Now run the file again and you will notice the output is once again 100. Since the top item can be converted to
an Integer it is returned multiplied by 2.

Hope that this helps your understanding of a more advanced data structure in Java.

Enjoy,
James

Resources:
Stack (Java 2 Platform SE v1.4.2)
Stacks and Queues

[WingedPanther]

Nice job. +rep

[Brandon W]

Even though I don't know no Java. This is very clear.

Well done. +rep

[Turk4n]

Well done, stacks are a main important part while working with larger Arrays !
Instead of using the slower ArrayList you cand combine stacks and arrays which will and theoretically be faster then a normal array

Anyways well done !

[TALucas]

Kudos!!!! +Rep

[Egz0N]

nice .. +rep