https://github.com/hym105289/Deques-and-Randomized-Queues
1.双端队列
操作要求：实现一个双端队列，可以在队头插入，也可以在队尾插入，可以在队头删除，也可以在队尾删除。
时间要求：每次插入或删除的时间复杂度为常量。
内存要求：一个包含n个对象的队列最多使用48n+192字节的内存。
思路：要实现常量时间内的插入和删除，可以采用双向链表实现
①队列的变量：长度，first头结点，last尾结点；
②Node：Item和pre、next双向结点；
③注意要实现Iterable<Item>接口中的hasNext、next、remove函数；
④插入要考虑当第一个元素插入的情况:队头插入则记得修改队尾队尾插入则记得修改队头；删除也要考虑到只有一个元素的情况，队头删除记得修改队尾，队尾删除记得修改队头；
⑤因为是双向链表，所以要记得更改与插入和删除元素相连接的结点，尤其要考虑到只有一个结点时的特殊情况；
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.In;
public class Deque<Item> implements Iterable<Item> {
private int n;
private Node first;
private Node last;
private class Node {
private Item item;
private Node pre;
private Node next;
}
public Deque() {
n = 0;
first = null;
last = null;
}
public boolean isEmpty() {
if (first == null)
return true;
else
return false;
}
public int size() {
return n;
}
public void addFirst(Item item) {
if (item == null) {
throw new IllegalArgumentException();
}
Node temp = new Node();
temp.item = item;
temp.next = first;
temp.pre = null;
if (first != null) {
first.pre = temp;
}
first = temp;
n++;
if (n == 1) {
last = first;
}
}
public void addLast(Item item) {
if (item == null) {
throw new IllegalArgumentException();
}
Node temp = new Node();
temp.item = item;
temp.pre = last;
temp.next = null;
if (last != null) {
last.next = temp;
}
last = temp;
n++;
if (n == 1) {
first = last;
}
}
public Item removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Item item = first.item;
first = first.next;
if (first != null)
first.pre = null;
n--;
if (n == 0) {
last = null;
}
return item;
}
public Item removeLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Item item = last.item;
last = last.pre;
if (last != null)
last.next = null;
n--;
if (n == 0) {
first = null;
}
return item;
}
@Override
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
String[] test = new In(args[0]).readAllStrings();
for (String s : test) {
System.out.println(s);
}
System.out.println();
Deque<String> deque = new Deque<String>();
for (int i = 0; i < test.length; i++) {
deque.addLast(test[i]);
}
for (String w : deque) {
System.out.println(w);
}
for (int i = 0; i < test.length; i++) {
test[i] = deque.removeLast();
System.out.println(test[i]);
}
}
}
2.随机队列
操作要求：按顺序的进行插入元素，但是随机地删除队列中的一个元素，迭代器也要求随机地访问所有元素；
性能要求：删除队列中的一个元素，均摊为常量时间；
内存要求：n个元素的队列，48n+192字节内存空间；
思路：采用动态数组来实现随机队列，随机队列可以随机地删除一个元素，首先产生一个均匀分布的在[0, N)之间的随机数，并与N-1交换，然后弹出items[N-1]；其迭代器也要求随机遍历元素，实现方式是取出数组下标构成一个index[]数组，同样用StdRandom对index[]进行随机洗牌，然后按照产生的随机数组下标遍历容器中的元素。
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
public class RandomizedQueue<Item> implements Iterable<Item> {
private int N;
private Item[] items;
public RandomizedQueue() {
N = 0;
items = (Item[]) new Object[1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void enqueue(Item item) {
if (N == items.length) {
resize(2 * items.length);
}
if (item == null) {
throw new IllegalArgumentException();
}
items[N++] = item;
}
private void resize(int length) {
Item[] temp = (Item[]) new Object[length];
for (int i = 0; i < N; i++) {
temp[i] = items[i];
}
items = temp;
}
private void randomSwap() {
if (N <= 1)
return;
int random = StdRandom.uniform(N);
Item temp = items[random];
items[random] = items[N - 1];
items[N - 1] = temp;
}
public Item dequeue() {
if (isEmpty()) {
throw new NoSuchElementException();
}
randomSwap();
Item item = items[N - 1];
items[N - 1] = null;
N--;
if (N > 0 && N == items.length / 4)
resize(items.length / 2);
return item;
}
public Item sample() {
if (isEmpty()) {
throw new NoSuchElementException();
}
randomSwap();
return items[N - 1];
}
public Iterator<Item> iterator() {
return new RandomQueueIterator();
}
private class RandomQueueIterator implements Iterator<Item> {
private final int[] index;
private int current;
public RandomQueueIterator() {
index = new int[N];
for (int i = 0; i < N; i++) {
index[i] = i;
}
for (int i = N - 1; i >= 0; i--) {
int random = StdRandom.uniform(i + 1);
int temp = index[random];
index[random] = index[i];
index[i] = temp;
}
current = N - 1;
}
public boolean hasNext() {
return current >= 0;
}
public Item next() {
if (current < 0) {
throw new NoSuchElementException();
}
return items[index[current--]];
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
RandomizedQueue<String> rq = new RandomizedQueue<String>();
String[] test = new In(args[0]).readAllStrings();
for (int i = 0; i < test.length; i++) {
rq.enqueue(test[i]);
}
for (String s : rq) {
StdOut.println(s);
}
StdOut.println();
String t = rq.dequeue();
StdOut.println(t);
}
}
要注意两点：
① items = (Item[]) new Object[1];会报警告（是因为[Java]不允许创建泛型数组（某些历史和技术原因），所以泛型数组只能通过强制类型转换(Item[]) new Object[cap]）实现。因此出现的警告不可避免，忽略即可。
②插入元素前判断是否需要扩容，删除元素后判断是否需要缩减容量；
③尤其注意迭代器的实现，利用了一个额外的index数组，来实现随机排列；
3.Permutation
操作要求：输入一组元素，插入到队列中，从命令行读取个数k，从中输出k个随机的元素。
要求：不能利用额外的String数组来保存输入的String对象
import edu.princeton.cs.algs4.StdIn;
public class Permutation {
public static void main(String[] args) {
int k = Integer.parseInt(args[0]);
RandomizedQueue<String> rq = new RandomizedQueue<String>();
while (!StdIn.isEmpty()) {
rq.enqueue(StdIn.readString());
}
for (int i = 0; i < k; i++) {
String temp = rq.dequeue();
System.out.println(temp);
}
}
}
