//********************************************************************//
//***************Queues - January 24rd, 2017 ************************//
//******************************************************************//

-*REALITY CHECK! Implement a "Stack Class" based on the given interface (on website)!*

public class Stack<T> implements StackADT<T> { //almost forgot the <T>'s
    private final int INITIAL_CAPACITY = 100;
    private T[] backing; //had to look up how to declare a generic array
    private int size;

    public Stack() {
        backing = (T[]) new Object[INITIAL_CAPACITY];
    }

    public void push(T item) { //adding/removing from the back is most efficient
        if (size == backing.length) {
            throw new RuntimeException("Stack backing structure is full");
        }
        backing[size] = item; //could've used "size++" here to avoid the 2nd line
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new java.util.EmptyStackException("No objects in stack to return");
        }
        temp = backing[size];
        size--;
        return temp;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

-...well, that's a bit of a long intro.
    -On the bright side, my implementation was correct!
        *almost; I declared the generic array wrong at first (it's fixed here)

-"This is more or less how test questions will be phrased" - HB
-Speaking of which, 1st test will be IN TWO WEEKS!!!
    -A practice exam will be given, but answer keys will NOT be provided; you'll have to look up the answer for yourself
    -Exam is designed to be finished in 50 minutes (*stunned shock*)
------------------------------------------------------------

-A QUEUE is a FIFO ("first-in, first-out") data structure- the OPPOSITE of a stack
    -Just like a normal "queue", or waiting in line: the 1st person to wait in line should be the first to get out!
    -Insertions are at the BACK of the queue, removals are from the FRONT
        -You shouldn't be accessing ANY other part of the Queue
    -Like "Stacks", Queues are considered ADTs, and are fundamentally linear

-MAIN OPERATIONS:
    -"enqueue(object)" inserts an element at the end of the queue
    -"object dequeue" removes and returns the element from the start of the queue
        -Usually also has a "first()" method to look at the front without removing it, as well as a pretty size() / isEmpty() method

-Using an Array as a backing structure:
    -Use an array of size "n", and WRAP AROUND in a circular way
        -When the queue has fewer than "n" elements, "back = (front + size) % n" is the first empty slot past the rear of the queue
            -Elements are ONLY shifted when "enqueueing"; when you remove front elements, you instead change WHERE THE FRONT INDEX is, NOT shifting things
                -This is why you need the "back = (front+size) % n" operation; when you have open space in the front of the queue, you instead add elements to the front of the array and just start the traversal from the "new" front of the array
                    -e.g. the word "AWESOME" becomes "SOMEAWE", but we start reading from "A" and then wrap around to read; ta-da!
                -This is great, since in return for this "confusion", we avoid having to resize the array for additions! It's therefore MUCH more efficient!
    -2 variables: "front" keeps track of the front/first element, "size" keeps track of the size of the queue

-PSEUDOCODE:
    void enqueue(o)
        back = (front+size) % n
        item[back] = 0
        size++

    object dequeue()
        item = arr[front]
        front = (front + 1) % n
        size--
        return item

        -Now, what would you do if the queue is empty? Throw an error? Return null? It all depends on what you need...

-Linked List Implementation
    -NEEDS a tail variable now to have any sort of efficiency

-PERFORMANCE:
    -Space used is O(n)
    -Time for enqueueing/dequeuing is O(1)

    -Limitations:
        -For array-based implementations, We must either know the initial size OR have to deal with resizing the array (which is O(n), although enqueueing is still considered O(1))
        -Linked List implementations do NOT have this limitation

-Applications:
    -DIRECT-
        -Waiting lists (literally)
        -Printer queues, shared resources, etc.
        -Multithreading

    -INDIRECT- (on the slides)