001package hw5.problem1;
002
003
004/**
005 * IntQueue2 is our second implementation of a basic first-in, first-out queue
006 * for Integers.
007 * <p>
008 *
009 * An IntQueue can be described as [n1, n2, ..., n_k], where n1 is the
010 * least-recently-added item in the queue and is the next item to be
011 * removed.  n_k is the most-recently-added and will be the last of the
012 * current elements to be removed.
013 * <p>
014 *
015 * An IntQueue can also be described constructively, with the append operation,
016 * ':', such that [n1, n2, ..., n_k] : n_k+1 is the result of enqueing n_k+1
017 * at the end of the queue.
018 *
019 * @author Krysta Yousoufian
020 */
021public class IntQueue2 {
022    // This class represents a queue as a circular ring buffer. An array
023    // stores the values in the queue. Because the number of elements
024    // currently in the queue is usually less than the size of the
025    // array, we store the index of the first item in the queue and the
026    // total number of elements in the queue. For example, a queue with 4
027    // items might look like this:
028    //
029    // [__ __ n1 n2 n3 n4 __ __]
030    //        ^front   ^front+size-1
031    //
032    // As items are enqueued, front remains unchanged while size is
033    // incremented.  As items are dequeued, front is incremented and size
034    // is decremented.
035
036    // Normally, your abstraction function and representation invarant would go
037    // here. For ease of grading, please place them in hw5/answers/problem1.txt
038    // instead with your answers to the other written exercises.
039
040    // Starting size for the array
041    private static final int INITIAL_SIZE = 20;
042
043    int[] entries;
044    int front;
045    int size;
046
047    /**
048     * @effects constructs an empty queue
049     */
050    public IntQueue2() {
051        entries = new int[INITIAL_SIZE];
052        front = 0;
053        size = 0;
054        checkRep();
055    }
056
057    /**
058     * Enqueue an item
059     * @param entry item to be added to the queue
060     * @modifies this
061     * @effects places entry at the end of the queue
062     */
063    public void enqueue(Integer entry) {
064        // Enlarge queue if necessary
065        if (size == entries.length) {
066            int[] newEntries = new int[entries.length * 2];
067            for (int i = 0; i < size; i++) {
068                newEntries[i] = entries[(front+i)%entries.length];
069            }
070            entries = newEntries;
071            front = 0;
072        }
073
074        // Add item to the end of the queue, wrapping around to the front if necessary
075        entries[(front+size)%entries.length] = entry;
076        size++;
077
078        checkRep();
079    }
080
081    /**
082     * Dequeue an item
083     * @requires size() > 0
084     * @modifies this
085     * @effects removes the item at the front of the queue
086     * @return the item that was first in the queue
087     */
088    public Integer dequeue() {
089        Integer ret = entries[front];
090        size--;
091        front = (front+1) % entries.length;
092        return ret;
093    }
094
095    /**
096     * See the next item without removing it
097     * @requires size() > 0
098     * @return the item currently first in the queue
099     */
100    public Integer front() {
101        return entries[front];
102    }
103
104    /**
105     *
106     * @return number of elements in the queue
107     */
108    public int size() {
109        return size;
110    }
111
112    /**
113     *
114     * @return size() == 0
115     */
116    public boolean isEmpty() {
117        return size == 0;
118    }
119
120    public void checkRep() {
121        // If I gave this to you, you wouldn't have the fun of figuring out the
122        // rep invariant for yourself :)
123    }
124}