プログラミング割り当て2：両端キューとランダム化されたキュー

Programming Assignment 2

デキュー
双頭リスト
アイデア：各ノードには、addFirst、addLast、removeFirst、removeLastを実装するための次と前が含まれています。プルーニング操作を追加するたびに、first.beforeとlast.nextがnullであることを確認してください。

import java.util.Iterator import java.util.NoSuchElementException /* API: public Deque() // construct an empty deque public boolean isEmpty() // is the deque empty? public int size() // return the number of items on the deque public void addFirst(Item item) // add the item to the front public void addLast(Item item) // add the item to the end public Item removeFirst() // remove and return the item from the front public Item removeLast() // remove and return the item from the end public Iterator iterator() // return an iterator over items in order from front to end public static void main(String[] args) // unit testing (optional) */ public class Deque<Item> implements Iterable<Item> { private Node first private Node last private int num public Deque() { first = null last = null num = 0 } private class Node { Item item Node next Node before } public int size() { return num } public boolean isEmpty() { // when is empty , first or last will be null. return first == null } public void addFirst(Item item) { if (item == null) throw new IllegalArgumentException() // add the first one if (isEmpty()) { Node cur = new Node() cur.item = item first = cur last = cur } else { Node oldFirst = first first = new Node() first.item = item first.next = oldFirst oldFirst.before = first } num++ } public void addLast(Item item) { if (item == null) throw new IllegalArgumentException() // add the first one if (isEmpty()) { Node cur = new Node() cur.item = item first = cur last = cur } else { Node oldLast = last last = new Node() last.item = item last.before = oldLast oldLast.next = last } num++ } public Item removeFirst() { if (isEmpty()) throw new NoSuchElementException() Item item = first.item first = first.next // make sure that first.before always is null if (first != null) first.before = null else last = null num-- return item } public Item removeLast() { if (isEmpty()) throw new NoSuchElementException() Item item = last.item last = last.before // make sure that last.next always is null if (last != null) last.next = null else first = null num-- return item } @Override public Iterator<Item> iterator() { return new ListIterator() } private class ListIterator implements Iterator<Item> { private Node current = first @Override public boolean hasNext() { return current != null } @Override public void remove() { throw new UnsupportedOperationException() } @Override public Item next() { if (!hasNext()) throw new NoSuchElementException() Item item = current.item current = current.next return item } } public static void main(String[] args) { Deque<Integer> test = new Deque<Integer>() for (int i = 0 i < 100 i++) { if (i % 2 == 0) test.addFirst(i) else test.addLast(i) } System.out.println(test.isEmpty()) for (int i = 0 i < 100 i++) { if (i % 2 == 0) test.removeLast() else test.removeFirst() } System.out.println(test.isEmpty()) for (int i = 0 i < 1000 i++) { if (i % 2 == 0) test.addLast(i) else test.addFirst(i) } System.out.println(test.size()) for (int i = 0 i < 1000 i++) { test.removeLast() } System.out.println(test.isEmpty()) } }

ランダム化されたキュー
デキュー実装方法：ランダムインデックス[0、last-1]を生成します。このインデックスは削除されるインデックスであり、このインデックスの値と最後の値が交換されて、削除操作が示されます。

import java.util.Iterator import java.util.NoSuchElementException import edu.princeton.cs.algs4.StdRandom import java.util.Objects /* API: public RandomizedQueue() // construct an empty randomized queue public boolean isEmpty() // is the randomized queue empty? public int size() // return the number of items on the randomized queue public void enqueue(Item item) // add the item public Item dequeue() // remove and return a random item public Item sample() // return a random item (but do not remove it) public Iterator iterator() // return an independent iterator over items in random order public static void main(String[] args) // unit testing (optional) */ public class RandomizedQueue<Item> implements Iterable<Item> { private Item[] items private int last public RandomizedQueue() { items = (Item[]) new Object[1] last = 0 } private void resize(int newSize) { Item[] newItems = (Item[]) new Object[newSize] for (int i = 0 i < size() i++) { newItems[i] = items[i] } items = newItems } public int size() { return last } public boolean isEmpty() { return last == 0 } public void enqueue(Item item) { if (item == null) throw new IllegalArgumentException() // double the size of items if necessary if (size() == items.length) resize(items.length*2) items[last++] = item } public Item sample() { if (isEmpty()) throw new NoSuchElementException() return items[StdRandom.uniform(last)] } public Item dequeue() { if (isEmpty()) throw new NoSuchElementException() int ind = StdRandom.uniform(last) Item item = items[ind] items[ind] = items[last - 1] items[last - 1] = null // to avoid loitering last-- // shrink the size of items if necessary if (size() == items.length/4 && size() > 0) resize(items.length/2) return item } @Override public Iterator<Item> iterator() { return new ListIterator() } private class ListIterator implements Iterator<Item> { private final Item[] objects private int cur public ListIterator() { cur = last objects = (Item[])new Object[cur] //StdRandom.shuffle(obeject s) } @Override public boolean hasNext() { return cur != 0 } @Override public void remove() { throw new UnsupportedOperationException() } @Override public Item next() { if (cur == 0) throw new NoSuchElementException() int ind = StdRandom.uniform(cur) Item obj = objects[ind] objects[ind] = objects[--cur] //objects[cur] = obj return obj } } public static void main(String[] args) { RandomizedQueue<Integer> test = new RandomizedQueue<Integer>() for (int i = 0 i < 100 i++) { test.enqueue(i) } System.out.println(test.size()) Integer []num = new Integer[100] for (int i = 0 i < 100 i++) { Integer n = test.dequeue() for (int j = 0 j < i j++) { if (Objects.equals(num[j], n)) System.out.println('wrong') } num[i] = n } System.out.println(test.size()) for (int i = 0 i < 1000 i++) { test.enqueue(StdRandom.uniform(1000)) } for (int i = 0 i < 1000 i++) { System.out.println(test.dequeue()) } System.out.println(test.size()) } }

順列

import edu.princeton.cs.algs4.StdIn import edu.princeton.cs.algs4.StdOut public class Permutation { public static void main(String[] args) { int k = Integer.parseInt(args[0]) RandomizedQueue<String> test = new RandomizedQueue<String>() while (!StdIn.isEmpty()) test.enqueue(StdIn.readString()) while (k > 0) { StdOut.println(test.dequeue()) k-- } } }