INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS201, SECTIONS 52  (002 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB  #08 Stacks, Queues & Lists

 

Instructor: Bashir M. Ghandi

 


Objectives:

 

1.         Abstract Data Types Animation Applets.

Click on each of the following links to visualize the various ADT’s in action:

 

2.         Array Implementation of Stack ADT

The implementation of Stack ADT using array of characters as discussed in the lectures can be found in the file,  StackArray.java.  This implementation uses StackOutOfBoundsException class defined in the file StackOutOfBoundsException.java.  Open both these files and study them closely to understand them.

 

Example 1:  The following example, StackArrayTest.java, makes use of the above class to implement a menu-driven program that allows the user to test the methods of the stack ADT.  Open it, study it, compile and test-run it.

import java.io.*;

 

public  class StackArrayTest {

 

   public static void main(String[] args) throws IOException {

      BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

      StackArray s = new StackArray(10);

  

      while (true) {

        System.out.println("\n1\tPush\n2\tPop\n3\tPeek\n4\tDisplay\n5\tQuit");

        System.out.print("Enter your choice:  ");

        char choice = stdin.readLine().charAt(0);

        try {

           switch (choice) {

               case '1': System.out.print("Enter Character Element: ");

                          char ele = stdin.readLine().charAt(0);

                          s.push(ele);

                          break;

               case '2': System.out.println("popped: "+s.peek());

                          s.pop();

                          break;

               case '3': System.out.println("top element is: "+s.peek());

                          break;

               case '4': s.print();

                        System.out.println();    

                          break;

               case '5': return;

               default: System.out.println("invalid command..");

           } // end switch

        } //end try

        catch(StackOutOfBoundsException e) {

           System.out.println(e);

        } // end catach        

      }

   }

}

 

 

3.         Array Implementation of Queue ADT

The implementation of Queue ADT using array of characters as discussed in the lectures can be found in the file,  QueueArray.java.  This implementation does not handle exceptions.  Thus, the user must check for possible errors when using this class.

 

Example 2:  The following example, QueueArrayTest.java, makes use of the above class to implement a menu-driven program that allows the user to test the methods of the Queue ADT.  Open it, study it, compile and test-run it.

import java.io.*;

 

public  class QueueArrayTest {

        

   public static void main(String[] arg) throws IOException {

      BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

      QueueArray q = new QueueArray(10);

  

      while (true) {

         System.out.println("1\tEnqueue\n2\tDequeue\n3\tFront\n4\tDisplay\n5\tSize\n6\tQuit");

         System.out.print("Enter your choice:  ");

         char choice = stdin.readLine().charAt(0);

         switch (choice) {

            case '1': System.out.print("Enter Character Element: ");

                    char ele = stdin.readLine().charAt(0);

                    if (!q.isFull())

                              q.enqueue(ele);

                    else

                        System.out.println("Sorry, Queue is Full");   

                    break;

            case '2': if (!q.isEmpty()) {

                       System.out.println("Dequed: "+q.front());

                       q.dequeue();

                    }  

                    else

                       System.out.println("Sorry, Queue is Empty");  

                    break;

            case '3': if (!q.isEmpty())

                         System.out.println("front element is: "+q.front());

                     else

                        System.out.println("Sorry, Queue is Empty");         

                    break;

            case '4': q.print();

                    break;

            case '5': System.out.println("Queue size="+q.size());

                    break;

            case '6': return;

            default: System.out.println("invalid command..");

         }

      }

   }

  

}

 

Notes:

Comparing Example 1 and Example 2 we can observe two major advantages of using Exception handling provided by Java.

1.        Security:  Because StackOutOfBoundsException is derived from Exception which is a checked exception, the compiler will not allow any applications that makes use of any of the methods push(), pop() and peek() to compile unless there is some specification on what to do if StackOutOfBoundsException occurs.  Thus, using exceptions as in Example 1 forces the programmer to write a more secure programs.

 

2.        Shorter Code: Using exception handling, we can use one try-catch statement to handle multiple calls of the methods that throw exceptions as seen in Example 1:  In example 2 we had to use an if statement for each call to any of the methods that throw exceptions. 

 

4.         Implementation of Linked List.

The file LinkedList.java implements the dynamic List ADT as discussed in the lectures.  It makes use of the files: Node.java and LinkedListIterator.java. Open each of these files and study them closely.  Notice the use of the standard Exception class IndexOutOfBoudsException.

 

Example 3:  The following example, LinkedListTest.java, shows how LinkedList may be used.

import java.io.*;

 

public class LinkedListTest {

   private BufferedReader stdin;

   private LinkedList list;

 

   public LinkedListTest() throws IOException {      

      stdin = new BufferedReader(new InputStreamReader(System.in));    

      list = new LinkedList();

      while (true) {

         System.out.println("1\tAdd\n2\tChange\n3\tDelete\n4\tFind Element\n5\tGet Element At\n6\tPrint\n7\tReset\n8\tQuit");

         System.out.print("Enter your Choice: ");

         int choice = Integer.parseInt(stdin.readLine());

         switch (choice) {

            case 1: add();

                    break;

            case 2: change();

                    break;

            case 3: delete();

                    break;

            case 4: findObject();

                      break;                         

            case 5: get();

                    break;

            case 6: list.print();

                    break;

            case 7: list.clear();

                    System.out.println("list cleared");

                    break;

            case 8: return;

            default: System.out.println("invalid command..");

         }

      }

   }

  

   private void add() throws IOException {

      try {

         System.out.print("Add at Position : ");

         int pos = Integer.parseInt(stdin.readLine());

         System.out.print("Enter Integer Element: ");

         int ele = Integer.parseInt(stdin.readLine());

         list.insert(pos,new Integer(ele));

      } catch (IndexOutOfBoundsException e) {

         System.out.println(e);

      }

   }

  

   private void change() throws IOException {

      try {

         System.out.print("Change at Position : ");

         int pos = Integer.parseInt(stdin.readLine());

         System.out.print("New Element: ");

         int ele = Integer.parseInt(stdin.readLine());

         list.update(pos,new Integer(ele));

      }

      catch (IndexOutOfBoundsException e) {

         System.out.println(e);

      }

   }

   private void delete() throws IOException {

      try {

         System.out.print("Delete At Position : ");

         int pos = Integer.parseInt(stdin.readLine());

         list.remove(pos);

      }

      catch (IndexOutOfBoundsException e) {

         System.out.println(e);

      }

   }

  

   private void get() throws IOException {

      try {

         System.out.print("Get at Position : ");

         int pos = Integer.parseInt(stdin.readLine());

         System.out.println(list.retrieve(pos));

      }

      catch (IndexOutOfBoundsException e) {

         System.out.println(e);

      }

   }

 

    private void findObject() throws IOException {

      System.out.print("Find element : ");

      int e = Integer.parseInt(stdin.readLine());

      LinkedListIterator iterator = find(new Integer(e),new LinkedListIterator(list));

      if (iterator.isPastEnd())

            System.out.println(e+" not found");

       else

          System.out.println(iterator.retrieve()+" found");

   }

 

   LinkedListIterator find(Object e, LinkedListIterator iterator) {

       if (iterator.isPastEnd() || e.equals(iterator.retrieve()))

         return iterator;

       else {

      iterator.next();

         return find(e, iterator);

       }

    }  

 

   public static void main(String[] arg) throws IOException {

      new LinkedListTest();

   } 

}

 

5.         Linked List Implementation of Stack.

The file StackList.java in the following example shows how Stack ADT can be implemented using LinkedList.  Notice that in this case, there is no need to have the isFull() method.

 

Example 4:     

public class StackList {

   private LinkedList list;

 

   public StackList() {

       list = new LinkedList();

   }

 

   public boolean isEmpty() {

      return list.isEmpty();

   }

   

   public void push(Object e) {

     list.insert(0,e);

   }

   

   public Object peek(){

      if (isEmpty())

          throw new StackOutOfBoundsException("Sorry!  Stack is Empty");

      else   

      return list.retrieve(0);

   }

   

   public void pop() {

     if (isEmpty())

          throw new StackOutOfBoundsException("Opps!  Stack is Empty");

       else   

      list.remove(0);

   }

  

  public String toString() {

   return list.toString();

  }

 

    public void print() {

       System.out.println(this);

    }

}

 

 

Example 5:  The following example, StackListTest.java, modifies example 1 to use StackList.

import java.io.*;

 

public  class StackListTest {

 

   public static void main(String[] args) throws IOException {

      BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

      StackList s = new StackList();

  

      while (true) {

        System.out.println("\n1\tPush\n2\tPop\n3\tPeek\n4\tDisplay\n5\tQuit");

        System.out.print("Enter your choice:  ");

        char choice = stdin.readLine().charAt(0);

        try {

           switch (choice) {

               case '1': System.out.print("Enter Character Element: ");

                          String ele = stdin.readLine();

                          s.push(ele);

                          break;

               case '2': System.out.println("popped: "+s.peek());

                          s.pop();

                          break;

               case '3': System.out.println("top element is: "+s.peek());

                          break;

               case '4': s.print();

                        System.out.println();     

                          break;

               case '5': return;

               default: System.out.println("invalid command..");

           } // end switch

        } //end try

        catch(StackOutOfBoundsException e) {

        System.out.println(e);

        } // end catach        

      }

   }

}

 

5.         Assignment:

1.        (a)   Write a class, QueueOutOfBoundsException, similar to StackOutOfBoundsException and use it to modify the Array implementation of Queue ADT so that the methods, enqueue(), dequeue() and front() thow this exception.

(b)      Modify Example 2, QueueArrayTest.java, so that it handle QueueOutOfBoundsException instead of using if statements.

 

2.        Complete the Program in the File, StackBracketTest.java, so that is checks whether the brackets, {}, [], and (), in a given string match or not.

 

3.        (a)   Write a class, QueueList that uses LinkedList to implement the Queue ADT.  You must use QueueOutOfBoundsException where appropriate.

(b)     Write an application, QueueListTest, similar to StackListTest to test your implementation.

 

 

 

 

5.         Home Work:

Provide an implementation of a FirstLastLinkedList. This is an extended version of a LinkedList class which not only maintains a reference to the first node in the list, but also a reference to the last node in the list. This can help the performance of inserting new nodes at the end of the list.

Use the existing LinkedList.java class and modify to provide a reference to the last list node and also amend any methods as necessary.