[자료구조] Double-Ended Queue (Dequeue) and Randomized Queue

Double-Ended Queue (Dequeue) and Randomized Queue

더블엔디드큐

1. pop function call : 값 반환이 앞으로, 뒤로 가능함 ( removeFrist,removeLast )

2. push function call : 값 삽입이 앞으로, 뒤로 가능함 ( addFirst, addLast )

랜더마이즈 큐

1. dequeue function call 랜덤한 값을 반환하도록 한다.

2. enqueue function call 시에 할당된 Array 가 가득차있을경우 자동으로 늘려준다. MutableArray !

DOUBLE-Ended Queue ( Dequeue )

아래의 코드는 부여된 Interface 에서 함수를 작성한 것이다. 이게 답이라고는 얘기할 수 없다.

main function 은 작성 완료한 function 들을 테스트하는 공간이라고 생각하면 편하다.

/**
 * Homework Assignment #2-1: "Double-Ended Queue (Dequeue)"
 *
 *  - Double-Ended Queue implementation with a linked-list
 *
 * @ Student ID : A889056
 * @ Name       : GiPyeongLee
 * @ Date       : 2015.03.13
 **/

import java.util.Iterator;
import java.util.Scanner;

public class Deque<Item> implements Iterable<Item> {
    
    private int N;          // size of the Deque
    private Node first;		// first item
    private Node last;		// Create new variables last
    /*********************************
     * PUT YOUR CLASS VARIABLES HERE
     *********************************/
    
    // node class (for array or linked-list)
    private class Node {
        private Item item;
        private Node next;
        private Node before;
    }
    
    // construct an empty deque
    public Deque() {
        first = null;
        last = null;
        N=0;
    }
    
    // is the deque empty?
    public boolean isEmpty() {
        // There is no Items
        
        return N == 0;
    }
    
    // return the number of items on the deque
    public int size() {
        return N;
    }
    
    // insert the item at the front
    public void addFirst(Item item) {
        if (item == null)
            throw new java.lang.NullPointerException();
        
        if(first==null||last==null){
            // if first is null, than last is also null . cause it is first time;
            Node node = new Node();
            node.item = item;
            node.next= null;
            node.before=null;
            first = node;
            last = node;
        }else{
            // insert node front of first
            Node node = new Node();
            node.item = item;
            node.next = first;
            node.before = null;
            first.before = node;
            first = node;
        }
        N+=1; // Count up N
    }
    
    // insert the item at the end
    public void addLast(Item item) {
        if (item == null)
            throw new java.lang.NullPointerException();
        
        if(last==null||first==null){
            System.out.println("item : "+item);
            // if first is null, than last is also null . cause it is first time;
            Node node = new Node();
            node.item = item;
            node.next= null;
            node.before=null;
            first = node;
            last = node;
        }else{
            // insert node back of last
            Node node = new Node();
            node.item = item;
            node.next = null;
            node.before = last;
            last.next = node;
            last = node;
        }
        N+=1;
    }
    
    // delete and return the item at the front
    public Item removeFirst() {
        if (isEmpty())
            throw new java.util.NoSuchElementException("Deque underflow");
        
        Item item = first.item;
        first = first.next;
        N-=1;
        
        if(N==0){
            first=null;
            last=null;
        }
        
        return item;                   // return the saved item
    }
    
    // delete and return the item at the end
    public Item removeLast() {
        if (isEmpty())
            throw new java.util.NoSuchElementException("Deque underflow");
        
        Item item = last.item;
        last = last.before;
        if(last!=null)
            last.next = null;
        N-=1;
        
        if(N==0){
            first=null;
            last=null;
        }
        
        return item;                   // return the saved item
    }
    
    // return an iterator over items in order from front to end
    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() { /* not supported */
            throw new java.lang.UnsupportedOperationException();
        }
        public Item next() {
            if (current == null)
                throw new java.util.NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
    
    // test client(optional)
    public static void main(String[] args)   // unit testing
    {
        Deque<Integer> dq = new Deque<Integer>();
        
        for (int i = 0; i < 10; i++) {
            Integer item = new Integer(i);
            dq.addFirst(item);
            System.out.print("enqueue " + item);
            System.out.print("\t[ ");
            for (Integer s : dq)
                System.out.print(s + " ");
            System.out.println("]");
        }
        while (!dq.isEmpty()) {
            System.out.print("dequeue " + dq.removeLast());
            System.out.print("\t[ ");
            for (Integer s : dq)
                System.out.print(s + " ");
            System.out.println("]");
        }
        
    }
}

Randomized Queue

다음 알아볼 큐는 랜덤한 값을 출력해주는 큐이다.

추가로 MutableArray 를 구현하도록 한다.

/**
 * Programming Assignment 2-2: "RandomizedQueue"
 *
 *  - RandomizedQueue implementation with a resizing array.
 *
 * @ Student ID : A889056
 * @ Name       : GiPyengLee
 * @ Date       : 2015.03.15
 **/

import java.util.Scanner;
import java.util.Iterator;
import java.util.Random;

public class RandomizedQueue<Item> implements Iterable<Item>
{
    private Item[] a;       // array of items
    private int N;          // size of the RandomizedQueue
    private int head;       // pointer to head of RQ
    private int tail;       // pointer to tail of RQ
    
    private static Random random;    // pseudo-random number generator
    private static long seed;        // pseudo-random number generator seed
    
    // construct an empty randomized queue
    public RandomizedQueue() {
        a = (Item[]) new Object[2];
        N = 0;
        head = 0;
        tail = 0;
        seed = System.currentTimeMillis();
        random = new Random(seed);
    }
    
    // is the queue empty?
    public boolean isEmpty() {
        return N == 0;
    }
    
    // return the number of items on the queue
    public int size() {
        return N;
    }
    
    // resize the underlying array holding the elements
    private void resize(int capacity) {
        
        // resize array with capacity
        Item[] copy = (Item[])new Object[capacity];
        int idx = 0;
        
        for(int i=0;i<N;i++){
            copy[i] = a[i];
        }
        a = copy;
        
    }
    
    // add the item
    public void enqueue(Item item) {
        if (item == null)
            throw new java.lang.NullPointerException();
        
        if(N > 0 && N==a.length-1){
            // resize Array
            resize(2*a.length);
        }
        a[N]=item; // increase tail value
        N++;
        
    }
    
    // delete and return a random item
    public Item dequeue() {
        if (isEmpty())
            throw new java.util.NoSuchElementException("RandomizedQueue underflow");
        
        int dequeueIdx = random.nextInt(N);
        Item item = a[dequeueIdx];
        a[dequeueIdx]=null;
        
        if(N>0 && N == a.length/4-1){
            // resize array
            resize(a.length/2);
        }
        
        // remove null value of 'a' Array
        for(int i=dequeueIdx;i<N;i++){
            if(i+1!=N)
                a[i]=a[i+1];
        }
        
        N--;
        
        return item;
    }
    
    // return (but do not delete) a random item
    public Item sample() {
        if (isEmpty())
            throw new java.util.NoSuchElementException("RandomizedQueue underflow");
        
        int dequeueIdx = random.nextInt(N);
        Item item = a[dequeueIdx];
        
        return item;
    }
    
    // return an independent iterator over items in random order
    public Iterator<Item> iterator() {
        return new RandomizedQueueIterator();
    }
    private class RandomizedQueueIterator implements Iterator<Item> {
        private int left;
        Item[] temp;
        public RandomizedQueueIterator() {
            temp = (Item[]) new Object[N];
            Item swap;
            for (int i = 0; i < N; i++) {
                temp[i] = a[(tail + i) % a.length];
                int rand = random.nextInt(i + 1);
                swap = temp[i];
                temp[i] = temp[rand];
                temp[rand] = swap;
            }
            left = N;
        }
        public boolean hasNext() {
            return left > 0;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
        public Item next() {
            if (!hasNext())
                throw new java.util.NoSuchElementException("Iterator underflow");
            return temp[--left];
        }
    }
    
    // test client(optional)
    public static void main(String[] args)   // unit testing
    {
        RandomizedQueue<String> rQueue = new RandomizedQueue<String>();
    }
}