FilesExpand file tree

 master

/

RandomizedQueue.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

102 lines (98 loc) · 2.97 KB

 master

/

RandomizedQueue.java

Copy path

Top

File metadata and controls

• Code
• Blame

102 lines (98 loc) · 2.97 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

import java.util.Iterator;

import edu.princeton.cs.algs4.StdRandom;

import edu.princeton.cs.algs4.StdOut;

public class RandomizedQueue<Item> implements Iterable<Item> {

private int N;

private int capacity;

private Item[] queue;

public RandomizedQueue() {

// construct an empty randomized queue

N = 0;

capacity = 1;

queue = (Item[]) new Object[capacity];

}

public boolean isEmpty() {

// is the queue empty?

return N == 0;

}

public int size() {

// return the number of items on the queue

return N;

}

public void enqueue(Item item) {

// add the item

if (item == null) throw new java.lang.NullPointerException();

if (N + 1 > capacity) {

resizePlus();

}

queue[N++] = item;

}

private void resizePlus() {

capacity *= 2;

Item[] newQueue = (Item[]) new Object[capacity];

int index = 0;

for (Item i : queue) {

newQueue[index++] = i;

}

queue = newQueue;

}

private void resizeMinus() {

capacity /= 2;

Item[] newQueue = (Item[]) new Object[capacity];

int index = 0;

for (int i = 0; i < capacity; i++) {

newQueue[index++] = queue[i];

}

queue = newQueue;

}

public Item dequeue() {

// delete and return a random item

if (isEmpty()) throw new java.util.NoSuchElementException();

int i = StdRandom.uniform(N);

Item ret = queue[i];

queue[i] = queue[--N];

queue[N] = null;

if (capacity / 4 > N) {

resizeMinus();

}

return ret;

}

public Item sample() {

// return (but do not delete) a random item

if (isEmpty()) throw new java.util.NoSuchElementException();

return queue[StdRandom.uniform(N)];

}

public Iterator<Item> iterator() {

// return an iterator over items in order from front to end

return new ListIterator();

}

private class ListIterator implements Iterator<Item> {

private int current = 0;

private int[] shuffledIndexes = new int[N];

public boolean hasNext() {

if (current == 0) {

for (int i = 0; i < N; i++)

shuffledIndexes[i] = i;

StdRandom.shuffle(shuffledIndexes);

}

return current < N;

}

public Item next() {

if (current == 0) {

for (int i = 0; i < N; i++)

shuffledIndexes[i] = i;

StdRandom.shuffle(shuffledIndexes);

}

if (current >= N || size() == 0) throw new java.util.NoSuchElementException();

return queue[shuffledIndexes[current++]];

}

public void remove() {

throw new java.lang.UnsupportedOperationException();

}

}

public static void main(String[] args){

RandomizedQueue<Double> rq = new RandomizedQueue<Double>();

rq.enqueue(0.6);

StdOut.println(rq.size());

}

}