Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Queue<T> {
- private Array<T> _arr; //backing array
- private int queueStart = 0; //start of queue; first to be enqueued, first to be dequeued
- private int queueEnd = 0; //end of queue; most recent enqueue, last to be dequeued
- private int arraySize = 255; //size of array, only powers of 2
- private int numOfElements = 0; //counts elements in array
- Queue() {
- _arr = new Array<T>(256); //default, makes backing array of 255 T objects
- }
- Queue(int sz) {
- arraySize = MathUtils.nextPowerOfTwo(sz) - 1; //makes size next power of two after specified size - 1
- _arr = new Array<T>(arraySize);
- }
- Queue(Array<T> array) {
- arraySize = MathUtils.nextPowerOfTwo(array.size) - 1; //makes that can hold provided one with size of next power of two - 1
- _arr = new Array<T>(arraySize);
- Array.ArrayIterator<T> iter = new Array.ArrayIterator<T>(array);
- while (iter.hasNext()) {
- enqueue(iter.next()); //fill queue with array's objects
- }
- }
- public void enqueue(T o) {
- if (numOfElements == arraySize - 1) { // reallocates and refills array if full
- arraySize = MathUtils.nextPowerOfTwo(arraySize + 2);
- Array<T> tempArray = new Array<T>(--arraySize);
- queueStart = 0;
- queueEnd = 0;
- while (!isEmpty()) {
- tempArray.set(queueEnd++, dequeue());
- }
- _arr = tempArray;
- }
- _arr.set(queueEnd++, o);
- ++numOfElements;
- }
- public T dequeue() {
- T value = null;
- if (!isEmpty()) {
- --numOfElements;
- value = _arr.get(queueStart++);
- if (queueStart == arraySize) {
- queueStart = 0;
- }
- }
- return value;
- }
- public int size() {
- return numOfElements;
- }
- public boolean isEmpty() {
- return numOfElements == 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement