About Stack, a Computer Abstract Data Type (ADT).

Stack is one of computer abstract data type, that usually will be learn by programmer during data structures class. Stack is a very simple data structure. Stack is really a ‘stack’ in a real world. Imagine a stack of book, you put the book a, book b, and then book c. The most top in the stack is book c (which is the last inserted), and the most at the bottom is book a (which is the least inserted, the most-senior).

Operations that usually have to be there for stack are:

  • push() insert new data into the stack
  • pop() remove and return the newest inserted data in the stack
  • peek() return the newest inserted data in the stack
  • remove() delete the newest inserted data in the stack

Usually, pop() is combination of peek() and remove().

Why using stack?

  • We can use it for (reversed) polish notation aka postfix.
  • We can use it for determining whether there is error in a syntax of a source code.

Okay, now let’s have our hand dirty. Here is a Stack class source code.

static class Stack
    {
    ArrayList<Integer> arr;
    int nElems;

    public Stack()
    {
        arr = new ArrayList<Integer>();
        nElems = 0;
    }

    public void push(int n)
    {
        arr.add(nElems++, n);
    }

    public int pop()
    {
        int num = arr.get(nElems - 1);
        arr.remove(nElems-1);
        nElems--;
        return num;
    }

    }

See the stack above, we are not implementing peek() and remove(). I left this for you to modify the program so that it has the capability to peek() data without removing, or remove() data without returning the item in the stack.

Now, let’s try the class.

public static void main (String[] args)
    {
    Stack s = new Stack();
    s.push(4);
    s.push(6);
    s.push(9);
    s.push(19);

    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    }

If you run the program, the output will be:

run:
19
9
6
4
BUILD SUCCESSFUL (total time: 0 seconds)

Which means, the recent-inserted item will be the first to be returned in the stack. Just like how we would like to get Book A (in the picture above) from the Stack, we must remove Book C first.

That’s it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s