Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.Iterator;
- import java.util.NoSuchElementException;
- import java.util.Random;
- public class RandomizedQueue<Item> implements Iterable<Item> {
- private Item[] data;
- private int size;
- public RandomizedQueue() {
- data = (Item[]) new Object[10];
- }
- public void enque(Item item) {
- if (size == data.length) {
- ensureCapacity(size * 2);
- }
- data[size++] = item;
- }
- public Item deque() {
- Random random = new Random();
- int index = random.nextInt(size);
- Item item = data[index];
- data[index] = data[size - 1];
- data[size - 1] = null;
- --size;
- if (size <= data.length / 4) {
- ensureCapacity(data.length / 2);
- }
- return item;
- }
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public Iterator<Item> iterator() {
- return new Iterator<Item>() {
- Item[] localData = Arrays.copyOf(data, RandomizedQueue.this.size);
- int size = localData.length;
- @Override
- public boolean hasNext() {
- return size > 0;
- }
- @Override
- public Item next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
- Random random = new Random();
- int index = random.nextInt(size);
- Item item = localData[index];
- localData[index] = localData[size - 1];
- localData[size - 1] = null;
- --size;
- return item;
- }
- @Override
- public void remove() {
- }
- };
- }
- private void ensureCapacity(int length) {
- Item[] items = Arrays.copyOf(data, length);
- data = items;
- }
- public static void main(String[] args) {
- RandomizedQueue<Integer> rQueue = new RandomizedQueue<Integer>();
- System.out.println("length = " + ((Object[]) rQueue.data).length);
- for (int i = 0; i < 11; i++) {
- rQueue.enque(i);
- }
- System.out.println("length = " + ((Object[]) rQueue.data).length);
- while (!rQueue.isEmpty()) {
- System.out.print(" " + rQueue.deque());
- }
- System.out.println();
- System.out.println("length = " + ((Object[]) rQueue.data).length);
- RandomizedQueue<String> stringRandomizedQueue = new RandomizedQueue<String>();
- for (int i = 65; i < 91; i++) {
- stringRandomizedQueue.enque(String.valueOf((char) i));
- }
- for(String str : stringRandomizedQueue) {
- System.out.print(" " + str);
- }
- System.out.println();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement