Using Stacks and Queues

Goals

• To implement simple Stack and Queue classes
• To use these new data structures to solve problems efficiently

Making the Structures

We'll begin by making our own Stack and Queues classes. Below, you are provided interfaces for your classes; please name your implementations MyStack, MyQueue (The interfaces are named so as to avoid conflict with the Java implementations of Stack and Queue.)

1. Using java.util.LinkedList build your own MyStack class (using the StackI interface).
2. Now, instead of using LinkedList to build MyQueue, use MyStack to build it. (Hint: you need two stacks to build a queue.) If you cannot visualize how to do this, ask your T for help (QueueI interface).

   public interface StackI <K> {
     //Pops an item from the top of the stack
     // and returns it.
     public K pop();
     //Pushes an item onto the top of the stack.
     public void push(K k);i
     // returns true iff stack is empty
     public boolean isEmpty();
   }
   
   public interface QueueI <K> {
     //Dequeues an item from the front of the
     // queue and returns it.
     public K dequeue();
     //Enqueues an item at the back of the queue
     public void enqueue(K k);
     // returns true iff queue is empty
     public boolean isEmpty();
   }
   
   
       

A) Application: Balanced Parenthesis

How can we easily and efficiently analyze an expression like this "{((([))])" to check whether the parenthesis/brackets are balanced? Using the stack data type, we can very easily. Please complete the method balancedParens()using the algorithm below:

For each character in the string:
1. For any character not in the set {<,>,[,],(,),{,}}, just discard.
2. For any left paren/bracket, push the character onto the stack.
3. For any right paren/bracket, pop the top of the stack. If it isn't the corresponding left paren/bracket, then return false. If stack is empty, likewise return false.

After you are done reading inputs, if the stack is empty return true.

B) Application: Postfix Notation

In computers, having a mathematical notation that avoids ambiguity is very important. Using Infix notation, 3-4+6 could be considered as (3-4)+6 or 3-(4+6). PostFix notation can avoid such an issue. We would write (3-4)+6 as 34-6+ and 3-(4+6) as 346+-

Write a method that takes a string in PostFix notation, evaluates it and returns an int. Your method needn't worry about bad inputs.

Use the Integer class, with its Integer(String) constructor and intValue() method to recover the integer values from the String.

C) Application: Recursively Listing Directories by Depth (Challenge Problem)

Write a program, using queues to recursively list all of the files in a directory. All of the files of similar depth from the original directory should be listed together.

~student/foo/b1
~student/foo/b2
~student/foo/b3
~student/foo/b4
~student/foo/b5
~student/foo/a/r1
~student/foo/a/r2
~student/foo/a/r3
~student/foo/a/r4
~student/foo/a/r5
~student/foo/c/f1
~student/foo/c/f2
~student/foo/a/g/j1
~student/foo/d/f/ff

D) Application: Turning Infix statements into Postfix (Challenge Problem)

Write a program to take an InFix statement of the form: (3+3)*4
Into a PostFix statement of the form: 33+4*
Use this link to the Shunting Yard Algorithm as a reference.

public class StackQueueProgs{
  public boolean balancedParens(String s){
    ...
  }
  public int postfix(String s){
    ...
  }
  public String[] listDirContents(String dir){
    ...
  }
  public String infixToPostfix(String){
    ...
  }

  //suggested
  private void listDirContentsRecursiveHelper(...){
    ...
  }
}