Question

Write pseudocodes for the procedure StackFull;
Update the Push procedure to consider the exceptional situation where the stack is full;
Write pseudocodes for the procedures QueueFull and QueueEmpty; In particular, how would
you revise the queue-full condition \head[Q]==tail[Q]+1", when \head[Q]==1" thus you
need to wrap around the array index?
Update the Enqueue procedure to consider the exceptional situations where the queue is full;
Update the Dequeue procedure to consider the exceptional situations where the queue is empty;
Implement the pseudocodes in Java. That is,
{ Use an array S[1...n] and the attribute top[S] to implement a Stack of n Elements,
where top[S]==0 means the stack is empty.
{ Use an array Q[1...(n+1)] and the attributes head[Q] and tail[Q], for a Queue of
n Elements. Again, implementation of head[Q] and tail[Q] should strictly follow the
pseudocodes.

{ Add to the Java Starter two Java classes ArrayStack.java and
ArrayQueue.java. Speci cally, these two classes MUST implement respectively the in-
terfaces Stack.java and Queue.java.
{ You should NOT make any change to the three les: Element.java, Stack.java and
Queue.java.

public interface Stack {
   public void push(Element e);
   public Element pop();
   public boolean stackEmpty();
   public boolean stackFull();
   public int getTopValue();
}

public interface Queue {
   public void enQueue(Element e);
   public Element deQueue();
   public boolean queueEmpty();
   public boolean queueFull();
   public int getHeadValue();
   public int getTailValue();

}

public class Element {
   private int key;
   private String info;
  
   public Element(int key, String info) {
       this.key=key;
       this.info=info;
   }
  
   public int getKeyValue() {
       return this.key;
   }
  
   public String getStringValue() {
       return this.info;
   }
}

Answer 1

Summary:

Stack works in LIFO or FILO manner, i.e, that is last in first out/ first in last out mannger.

The element that is inserted first will be the last element that will go out of the stack.

Stack interface contain methods like push, pop, peek. Push is used to add elements to the stack,

Pop is used to remove element from the stack and peek tells the top most element in the stack.

In below code we implemented stack using an array to perform different stack operations.

Queue works in FIFO manner, that means the element which is inserted first will be the first one to go out. Queue has many operations like enqueu, dequeue, tail, head.

Enqueue operation is performed to add element to the end of the queue, whereas dequeue operation is used to remove element from front of the queue. Tail gives the last element present in the queue, wherease, head returns the first element present in the queue.

Below code implementation is very simple, I have included comments and print statement wherever possible to make program more readable and understable.

-----------------------------------------Element.java---------------------------------------

public class Element {
    private int key;
    private String info;

    public Element(int key, String info) {
        this.key = key;
        this.info = info;
    }

    public int getKeyValue(){
        return this.key;
    }

    public String getStringValue(){
        return this.info;
    }
}

----------------------------------------Stack.java-----------------------------------

public interface Stack {
    public void push(Element e);

    public Element pop();

    public boolean stackEmpty();

    public boolean stackFull();

    public int getTopValue();
}

---------------------------------------------Queue.java--------------------------------

public interface Queue {
    public void enQueue(Element e);

    public Element deQueue();

    public boolean queueEmpty();

    public boolean queueFull();

    public int getHeadValue();

    public int getTailValue();
}

------------------------------------------StackImpl.java----------------------------------

public class StackImpl implements Stack {

    private Element[] data; // Generic array used to implement the stack
    private int size; // The actual capacity of the stack array

    private static final int CAPACITY = 1000; // default array capacity

    private int top = -1; // index for the top of the stack

    public StackImpl() {
        this(CAPACITY); // default capacity
    }

    public StackImpl(int capacity) {
        size = capacity;
        data = (Element[]) new Element[size];
    }


    @Override
    public void push(Element e) {
        if (stackFull()) {
            System.out.println("Stack is full.");
            return;
        }
        data[++top] = e;
    }

    @Override
    public Element pop() {
        Element element;
        if (stackEmpty()) {
            System.out.println("Stack is empty.");
            return null;
        }
        element = data[top];
        data[top--] = null; // dereference S[top] for garbage collection.
        return element;
    }

    @Override
    public boolean stackEmpty() {
        return (top < 0);
    }

    @Override
    public boolean stackFull() {
        return (size() == size);
    }

    @Override
    public int getTopValue() {
        if (stackEmpty()) {
            System.out.println("Stack is empty.");
            return 0;
        }
        return data[top].getKeyValue();
    }

    public void displayElements(String op, Element element) {
        System.out.print("------> " + op);  // print this operation
        System.out.println(", returns : (" + element.getKeyValue() + ", " + element.getStringValue() + ")"); // what was returned
        System.out.print("result: size = " + size() + ", isEmpty = " + stackEmpty());
        System.out.print(", stack: " ) ; this.stackElements(); // contents of the stack
    }


    public int size() {
        return top + 1;
    }

    public void stackElements() {
        if (stackEmpty()) {
            System.out.println("[]");
        } else {
            System.out.print("[ ");
            for (int i=0; i<=top; i++) {
                System.out.print("(" + data[i].getKeyValue() + ", " + data[i].getStringValue() + "), ");
            }
            System.out.print(" ]");
        }
        System.out.println();
    }
}

----------------------------------------QueueImpl.java---------------------------------

public class QueueImpl implements Queue{
    private static int front, rear, capacity;
    private static Element queue[];


    QueueImpl(int c)
    {
        front = rear = 0;
        capacity = c;
        queue = new Element[capacity];
    }

    @Override
    public void enQueue(Element e) {
        // check queue is full or not
        if (queueFull()) {
            System.out.printf("\nQueue is full\n");
            return;
        }

        // insert element at the rear
        else {
            queue[rear] = e;
            rear++;
        }
        return;
    }

    @Override
    public Element deQueue() {
        // if queue is empty
        if (queueEmpty()) {
            System.out.printf("\nQueue is empty\n");
            return null;
        }

        // shift all the elements from index 2 till rear
        // to the right by one
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }

            // store 0 and null at rear indicating there's no element
            if (rear < capacity)
                queue[rear] = new Element(0,null);

            // decrement rear
            rear--;
        }
        return null;
    }

    @Override
    public boolean queueEmpty() {
        return (front == rear);
    }

    @Override
    public boolean queueFull() {
        return (capacity == rear);
    }

    @Override
    public int getHeadValue() {
        if (queueEmpty()) {
            System.out.printf("\nQueue is Empty\n");
            return 0;
        }
        System.out.printf("\nHead Element is: %d", queue[front].getKeyValue());
        System.out.println("\n");
        return queue[front].getKeyValue();
    }

    @Override
    public int getTailValue() {
        if (queueEmpty()) {
            System.out.printf("\nQueue is Empty\n");
            return 0;
        }
        System.out.printf("\nTail Element is: %d", queue[rear].getKeyValue());
        System.out.println("\n");
        return queue[rear].getKeyValue();
    }

    public void queueDisplay()
    {
        int i;
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }

        // traverse front to rear and print elements
        for (i = front; i < rear; i++) {
            System.out.printf(" (%d, %s) <-- ", queue[i].getKeyValue(),queue[i].getStringValue());
        }
        return;
    }
}

----------------------------------------Driver.java------------------------------

public class Driver {
    public static void main(String args[]){
        StackImpl  stack = new StackImpl();

        System.out.println("***************************");
        System.out.println("Stack Demo:");
        System.out.println("***************************\n");

        System.out.println(stack.stackEmpty());
        Element element1 = new Element(4,"Gurudas");
        stack.push(element1);

        stack.displayElements("stack.push(Element(4,\"Gurudas\"))", element1);

        Element element2 = new Element(3,"Bhaskar");
        stack.push(element2);
        stack.displayElements("A.push(Element(3,\"Bhaskar\"))", element2);


        Element element3 = new Element(2,"Garima");
        stack.push(element3);
        stack.displayElements("A.push(Element(2,\"Garima\"))", element3);


        Element popped =  stack.pop();
        stack.displayElements("A.pop()", popped);


        System.out.println("Get Top value : " + stack.getTopValue());

        System.out.println();
        System.out.println("***************************");
        System.out.println("Queue Demo:");
        System.out.println("***************************\n");

        QueueImpl queue = new QueueImpl(3);
        queue.queueDisplay();
        System.out.println();

        System.out.println("Inserting 3 elements");
        // inserting elements in the queue
        queue.enQueue(element1);
        queue.enQueue(element2);
        queue.enQueue(element3);

        queue.queueDisplay();
        System.out.println();

        queue.deQueue();
        System.out.println("After one dequeue");
        queue.queueDisplay();

        queue.getHeadValue();
        queue.getTailValue();
    }
}

Output:

Please run main method present in Driver class to see the output.

Hope you will like this answer. Enjoy!!!