Advanced Topics

Stack

Summary

  • Stack is a basic data structure that inserts and retrieves based on the LIFO (Last In First Out) model.
  • Two fundamental operations: push(insert) and pop(retrieve and remove).
  • Efficiency:
    • push: O(1)
    • pop: O(1)
    • enlarge stack: O(n)
  • Often used for keeping track of history (refer to the Practice section for more detail).

Theory

The stack is a fundamental data structure that is used more commonly than you might think. Before exploring the applications of a stack, lets take a look at how it works.

Stacks have 2 fundamental operations: push (insert) and pop (retrieve and remove). The unique attribute about the stack is that it follows the Last In First Out (LIFO) model. Imagine the stack as a narrow, tall cookie jar. Every time you fill it up, the first cookie you insert goes to the bottom of the jar and the last cookie inserted goes on the top of the jar. When you want a retrieve a cookie from the jar, you take the top one out. This is exactly how a stack works.

Let's take a look at an example: Suppose that I want to insert the numbers: 7, 3, 12, 8, 5 into the stack in this order, the stack will look like the following:

If we were to pop off all the numbers in this stack, we will get it back in this order: 5, 8, 12, 3, 7.

Check out the implementation section for more details on creating the stack and the examples section for some real world applications.

[Download-Stack.java]

  • public void push(Object obj);
  • public Object pop();
  • public boolean hasNext();
  • private void enlarge();

The Idea

To implement a stack, we will be using an Object Array as an underlying source to hold the data. To optimize efficiency, we will keep a counter to keep track of the top of stack for easy push and pop operations.

In the initial state, we have an empty object array and a counter starting at 0. To push an object into the stack, we insert the object at S[counter] and then increment counter. To pop an object off the stack, we decrement counter and return the object at S[counter].

Lets examine how it works with the current state of Stack S:

Push

The next item we want to push onto the stack is the number 12. For this to happen, we will insert it at the current spot in the array and then increment counter as follows:

There is a problem with this design. As you can see, the array can only hold 4 objects, so if it fills up we will get an "Out of Bounds Exception". To fix this, we need to check if the counter is the same as the size of the array. If it is, we will double the size of the array with the enlarge() function call. More on enlarge() later.


        public void push(Object obj)
        {
            if(counter==S.length)
            {
                enlarge();
            }
            S[counter]=obj;
            counter=counter+1;
        }
        

Pop

To pop an item off the stack is simple. We simply decrement counter and return S[counter]. However, if the stack is empty we will return null. The object is not actually deleted from the array, but it will be over written on next insert.


        public Object pop()
        {
           if(counter==0)
           {
                return null;
           }
           counter=counter-1;
           return S[counter];		
        }
        

Has Next

This is a simple function that checks if there are any items in the stack. Returns false if counter is not 0, true otherwise. This is very useful for a quick mechanism to go through the stack without the fear of hitting a null.


        private boolean hasNext()
        {
            if(counter==0)
            {
                return false;
            }
            return true;
        }
        

Enlarge

Since array size is static in most programming languages, we need to implement a way to increase the size of the stack array while keeping all the data. The idea is simple: create a new temporary object array with double the size of the current array, copy everything over, and point the current array to the new array.


        private void enlarge()
        {
            Object[] temp = new Object[S.length*2];
            for(int i=0;i<S.length;i++)
            {
                temp[i]=S[i];
            }
            S=temp;		
        } 
        

Example - Paranthesis Checking

Suppose that you want to write an application that checks a string for well formed proper brackets opening and closing.

The following is correct:

  • This ( is { a } sentence )
  • ( This { [ is ( ) a { } ] sentence } )
The following is NOT correct:
  • ( This } is ( a ) sentence {
  • ( This { is [ a } sentence ] )

The string can contain any number of opening brackets and closing brackets with different types of brackets in no particular order. This will make this problem extremely complex to solve by using lots of comparisons and multiple loops. Don't believe me? Try it!

It is simple to solve this using a stack:

  1. Loop through each character of the string.
  2. If it is an open bracket, pop it onto the stack.
  3. If it is a closing bracket, pop a bracket off the stack and check if it is the same type. If it is, return false.
  4. After the loop, check if the stack has anymore elements, if so, return false.


            public boolean checkParanthesis(String sentence)
            {
                Stack S;
                Char[] c = sentence.toCharArray();
                for(int i=0; i<c.length;i++)
                {
                    if(c[i]=='(' || c[i]=='{' || c[i]=='[')
                    {
                        S.push(c[i]);
                    }
                    else if(c[i]==')' || c[i]=='}' || c[i]==']')
                    {   
                        if(c[i] != S.pop())
                        {
                            return false;  //Check if it is the same type of bracket
                        }
                    }
                }
                if(S.hasNext())
                {
                    return false; //Check for any unclosed brackets
                }
                return true;
            }
            

[Download-Practice.zip]

[Download-Solution.zip]

Practice Problem - The Back Button

Like all internet browsers, there is a "Back" button and a "Forward" button that allows you to go back and forth between the websites you have recently visited. The user can visit a new page at any time and this will disable the "Forward" button.

There are 3 methods to be implemented:

  • public void back()
  • public void forward()
  • public void visit(string visit)

The goal of this practice is to familiarize yourself with the Stack and how to use it effectivly to solve future problems.

Run the program to test. If it works properly, it will print out "Test Successful". If you get a null error or "Test Failed" messages, then your implementation is not correct. Refer to the solution if stuck.

Hints

  • There are 2 Stacks: Back and Forward. Use it to keep track of what was visited.
  • Be sure to "juggle" the website strings back and forth between the stacks.
  • Empty the "Forward" stack whenever the user visits a new site.