The Stack ADT

Stack is a last in first out datastructure. We can define the stack operations abstractly as an Interface as follows

public interface Stack<T> {

    int size();

    public boolean isEmpty();

    public T peek() throws StackEmptyException;

    public void push(T element);

    public T pop() throws StackEmptyException;

    public void print();

}

Now let us consider an application. We would like to reverse the elements of an array. How to use a Stack to achieve this? Let a be an array and let s be a Stack. Then, we can leverage the LIFO nature of s as follows:

	for (int i = 0; i < a.length; i++) {
	    s.push(a[i]);
	}

	for (int i = 0; i < a.length; i++) {
	    a[i] = s.pop();
	}

public class ArrayListStack<T> implements Stack<T> {
    protected List<T> stackData;
    protected int top = -1;

    public ArrayListStack() {
	this.stackData = new ArrayList<T>();
    }

    public int size() {

    }

    public boolean isEmpty() {
	
    }

    public T peek() throws StackEmptyException {

    }

    public void push(T element) {

    }

    public T pop() throws StackEmptyException {

    }

    public void print() {
	StringBuilder sb = new StringBuilder();
	sb.append("[");
	for (int i = top; i > -1; --i) {
	    sb.append((stackData.get(i)).toString());
	    if (i > 0) {
		sb.append(" : ");
	    }
	}
	sb.append("]");
	System.out.println("Printing the stack contents with top being leftmost");
	System.out.println(sb);
    }

    public static <T> void reverseArray(T[] a) throws StackEmptyException {

    }

HOMEWORK

You need to develop a NodeStack that implements the Stack interface. Using the same operations in the main method ensure that you have identical behaviour for both stacks.

Consider the class Node we created before:

public class Node<T> {
    private T val;
    private Node<T> next;

    // constructor

    public Node() {

    }

    public Node(T v) {
	val = v;
	next = null;
    }

    // getters and setters

    public void setNext(Node<T> n) {
	next = n;
    }

    public Node<T> getNext() {
	return next;
    }

    public T getValue() {
	return val;
    }
}

The Queue ADT

Queue is a first in first out (FIFO) data-structure with wide applicability.

public interface Queue<T> {

    public int size();

    public boolean isEmpty();

    public T front() throws QueueEmptyException;

    public void enqueue(T element) throws QueueFullException;

    public T dqueue() throws QueueEmptyException;

    public void print();

}

public class SimpleQueue<T> implements Queue<T> {
	protected int front;
	protected int rear;
	protected int count;
	protected int capacity;
	protected T[] queueData;

	public SimpleQueue(int capacity) {
		this.front = 0;
		this.rear = 0;
		this.count = 0;
		this.size = size;
		this.queueData = (T[]) new Object[capacity];

	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return count;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		
	}

	@Override
	public T front() throws QueueEmptyException {
		// TODO Auto-generated method stub
		
	}

	@Override
	public void enqueue(T element) throws QueueFullException {
		// TODO Auto-generated method stub
		
	}

	@Override
	public T dqueue() throws QueueEmptyException {
		// TODO Auto-generated method stub
	
	}

	@Override
	public void print() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for (int i = front; i < rear; ++i) {
			sb.append((queueData[i]).toString());
			if (i < rear - 1) {
				sb.append(" : ");
			}
		}
		sb.append("]");
		System.out.println("Printing the queue contents with front item being the left most");
		System.out.println(sb);
	}

Limitations of the SimpleQueue implementation

• While there is space available in the array i.e. the size of the Queue is 3. Yet, we are unable to reclaim the available space to enqueue.
• How can this be fixed? Can we wrap around F and R when they reach capacity?

A CircularQueue

• Here we can reclaim the available space
• Key idea is that when F or R reach the value of capacity-1 the next value upon increment makes them point again to the start of the queue i.e. 0. This is very simple to achieve using the mod operator.

public class CircularQueue<T> extends SimpleQueue<T> {

	public CircularQueue(int size) {
		super(size);
		// TODO Auto-generated constructor stub
	}

	@Override
	public void enqueue(T element) throws QueueFullException {
		// TODO Auto-generated method stub

	}

	@Override
	public T dqueue() throws QueueEmptyException {
		// TODO Auto-generated method stub
	}

	@Override
	public void print() {
		// TODO Auto-generated method stub
	}

TLDR

Concepts reused from previous lectures

• Polymorphism
• Interfaces
• Generics
• Inheritance

Recap of the Stack

• A Stack is a LIFO data-structure with wide applicability.
• The key operations are push, which adds an item to the top of the stack; pop, which removes an item from the top of the stack.
• You can use a stack to apply the B-Brackets, O-Orders (powers/indices or roots), D-Division, M-Multiplication, A-Addition, S-Subtraction (BODMAS) rule to solve an arithmetic expression. First thing you need to check if the expression is well-formed i.e. all the brackets are in the correct place and for every opening bracket there is a matching closing bracket.
• Consider: \(\{(a+b)*((c+d)/(e-f))\}\), which is well formed, while \(\{(a+b)*(c+d)/(e-f))\}\}\) is not well formed. ** HOMEWORK: Add a method to the ArrayListStack class to check if a given arithmetic expression is well formed.

Recap of the Queue

• A Queue is a FIFO data-structure, again with wide applicability.
• The key operations are enqueue that adds the next item to the end of the queue and dqueue that removes the next item at the front of the queue.

• A very good application of a Queue is when we want to perform scheduling. One typical scheduling is called round-robin, where the scheduler selects an entry from the front of the queue to provide service. This is, for example, how processes are scheduled by the operating system to allocate the CPU to a process for it’s timeslice.

• Examine how we explored a simple array-based queue, called a SimpleQueue, which has limitations.
• We then inherited from this SimpleQueue to create a CircularQueue