HW:

1. Implement MyArrayStack (constructor, push, pop, peek and isEmpty), MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedQueue (constructor, enqueue, dequeue, peek and isEmpty), and write the following two program to test them. (5 points)
2. For stack testing, write a program to check if a string has matching parenthesis such as (()), but not )(. (5 points)
3. For stack testing, use it to Evaluating Expressions using the algorithm given below. (5 points)
4. Animal Shelter: An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest"(based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintainthis system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the myLinkedlist data structure you created in previous homework.

The Algorithm for Step 3:

Phase 1: Scanning the expression

The program scans the expression from left to right to extract operands, operators, and the parentheses.

1.1. If the extracted item is an operand, push it to operandStack.

1.2. If the extracted item is a +or -operator, process all the operators at the top of operatorStackand push the extracted operator to operatorStack.

1.3. If the extracted item is a *or /operator, process the *or /operators at the top of operatorStackand push the extracted operator tooperatorStack.

1.4. If the extracted item is a (symbol, push it to operatorStack.

1.5. If the extracted item is a )symbol, repeatedly process the operators from the top of operatorStackuntil seeing the (symbol on the stack.

Phase 2: Clearing the stack

Repeatedly process the operators from the top of operatorStackuntil operatorStackis empty.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Here is my code:

-----------------------------------

MyArrayStack.java

import java.util.*;

public class MyArrayStack{

private ArrayList list = new ArrayList();

public int getSize(){

return list.size();

}

public E peek(){

return list.get(getSize() - 1);

}

public void push(E e){

list.add(e);

}

public E pop(){

E e = list.get(getSize() - 1);

list.remove(getSize() - 1);

return e;

}

public boolean isEmpty(){

return list.isEmpty();

}

public String toString(){

return "Stack: " + list.toString();

}

}

--------------------

MyLinkedStack.java

import java.util.NoSuchElementException;

public class MyLinkedStack {

private class Node {

public Node next;

public E item;

public Node(E item, Node next) {

this.item = item;

this.next = next;

}

public Node() {

}

public boolean isEnd() {

return next == null && item == null;

}

}

private Node top = new Node<>();//

public void push(E e) {

top = new Node<>(e, top);

}

public boolean isEmpty() {

return top.isEnd();

}

public E pop() {

if (isEmpty())

throw new NoSuchElementException("Stack is empty");

E result = top.item;

top = top.next;

return result;

}

public E peek(){

return top.item;

}

public static void main(String[] args) {

MyLinkedStack stack=new MyLinkedStack<>();

for(int i=0;i<20;i++)

stack.push(i);

while(!stack.isEmpty()){

System.out.print(stack.peek()+":");

System.out.println(stack.pop());

}

}

}

-------------------------

MyLinkedQueue.java

import java.util.NoSuchElementException;

@SuppressWarnings("unused")

public class MyLinkedQueue {

private int currentSize;

private Node front,rear;

private class Node{

public Node next;

public AnyType item;

public Node(AnyType item, Node next){

this.next=next;

this.item=item;

}

}

public MyLinkedQueue(){

front=rear=new Node<>(null,null);

}

public void enqueue(AnyType item){

rear.next=new Node<>(item,null);

rear=rear.next;

currentSize++;

}

public AnyType dequeue(){

if(isEmpty())

throw new NoSuchElementException("Queue is empty");

front=front.next;

return front.item;

}

public boolean isEmpty(){

return front==rear;

}

public static void main(String[] args) {

MyLinkedQueue que=new MyLinkedQueue<>();

for(int i=0;i<20;i++)

que.enqueue(i);

while(!que.isEmpty())

System.out.print(que.dequeue()+" ");

que.enqueue(1000);

System.out.println(que.dequeue());

System.out.println(que.dequeue());

}

}