승목

• 술목이의 LinkedList

구현

• 술목이의 구현!

LinkedList

package study;

public class LinkedList<T> implements Queue<T>{

    LinkedData start;    //시작.
    LinkedData end;    //끝.
    int size=0;

    public LinkedList(){
        this.start = new LinkedData();
        this.end = new LinkedData();
        start.pre = null;
        start.next = end;
        end.pre = start;
        end.next = null;
    }

    /**
    *    맨 뒤에 하나씩 추가한다.
    *    맨 뒤는 결국 end의 앞부분이다.
    *    end.pre에 있는 객체의 next에 연결하고,
    *    end의 pre에 넣어주면 된다.
    */
    public void add(T data){
        add(size,data);    //맨 마지막에 넣는다.
    }

    public void add(int index, T data){
        LinkedData idxData = getLinkedData(index);
        LinkedData<T> lData = new LinkedData<T>();
        lData.data = data;
        lData.pre = idxData.pre;
        lData.next = idxData;

        //end.pre
        idxData.pre.next = lData;
        idxData.pre = lData;

        //size
        size++;

        //print
        print();

    }

    public T get(int index){
        return (T) getLinkedData(index).data;
    }

    public int size(){
        return size;
    }

    private LinkedData getLinkedData(int idx){
        return getLinkedData(idx, start);
    }

    private LinkedData getLinkedData(int idx, LinkedData lData){
        if(idx > -1){
            return getLinkedData(idx-1, lData.next);
        }else {
            return lData;
        }
    }

    private void print(){
        System.out.print("\nList [ ");
        for(int i=0; i<size; i++){
            System.out.print(getLinkedData(i)+" ");
        }
        System.out.print("]");
    }

    //queue implement.

    //집어넣는다.
    public void offer(T data){
        add(0,data);
    }

    //꺼내고 지운다.
    public T poll(){
        T data = get(size-1);
        //test
        //System.out.println();
        end.pre = end.pre.pre;
        end.pre.next = end;
        size--;
        print();
        return data;
    }

    //있는지 확인한다.
    public T peek(){
        return get(size-1);
    }

    public static void main(String[] args){
        LinkedList<Data> list = new LinkedList<Data>();
        list.add(new Data(2));    // 2
        list.add(new Data(3));    // 2 3
        list.add(new Data(5));    // 2 3 5

        list.add(1, new Data(9));    // 2 9 3 5 expected

        Data d2 = list.get(2);    // 3.
        System.out.println("\n" + d2);

        System.out.println("\nend!");
    }
}

class LinkedData<T> {
    LinkedData pre;
    T data;
    LinkedData next;

    public String toString(){
        if(data == null){
            return "null!!";
        }else{
            return data.toString();
        }
    }

}

Stack

package study;

import java.lang.reflect.Array;
import study.StackOverflowException;
import study.StackUnderflowException;

/**
* 스택을 구현한 프로그램.
*/
public class Stack<T> {

    private final int size;
    private T[] datum;
    private int p = -1;

    public Stack(int initSize){
        size = initSize;
        datum = (T[]) new Object[initSize];
    }

    public void push(T data) throws StackOverflowException {
        if(p == size - 1 ) throw new StackOverflowException();
        datum[++p] = data;
        print("push");
    }

    public T pop() throws StackUnderflowException {
        if(p < 0) throw new StackUnderflowException();
        T data = datum[p];
        datum[p--] = null;
        print("pop");
        return data;
    }

    public int size(){
        return p;
    }

    private void print(String cmd){
        //verify data.
        System.out.print("\n "+cmd + " [");
        for(int i=0; i<=p; i++){
            System.out.print(datum[i] + " ");
        }
        System.out.print("]");
    }

    public static void main(String[] args){
        if(args.length < 3){
            System.err.println("enter init size and iteration count!! \n [1]size [2]push count [3]pop count");
            return;
        }

        //size, iter cnt.
        int size = 0;
        int pushCnt = 0;
        int popCnt = 0;
        try{
            size = Integer.parseInt(args[0]);
            pushCnt = Integer.parseInt(args[1]);
            popCnt = Integer.parseInt(args[2]);
        }catch(java.lang.NumberFormatException nfe){
            System.err.println("please input integer!!!");
        }



        try{
            Stack<Data> s = new Stack<Data>(size);

            //push
            System.out.print("\n push start.. ");
            for(int i=0; i<pushCnt; i++){
                int r = (int) (Math.random()*100);
                s.push(new Data(r));
            }

            //pop
            System.out.print("\n pop start.. ");
            for(int i=0; i<popCnt; i++){
                System.out.print(" >> "+s.pop());
            }

            System.out.println("\n end!");

        }catch(StackUnderflowException soe){
            System.out.println("stack underflow!!");
        }catch(StackOverflowException soe){
            System.out.println("stack overflow!!");
        }
    }
}

Stack

• 술목이의 Queue 정도는 인터페이스

package study;

public interface Queue<T> {

    //집어넣는다.
    public void offer(T data);

    //꺼내고 지운다.
    public T poll();

    //있는지 확인한다.
    public T peek();

}