도도의 초록누리

 abstract interface Queue{

       abstract void Push( Object x );

       abstract Object pop();

       abstract boolean isEmpty();

 }

 Queue Interface ADT

 
class LinkedNode{
        private Object data;
        private LinkedNode next;
 
        public void setData(Object x)
        {
             this.data = x;
        }

       public void setNext(LinkedNode node)
       {
             this.next = node;
       }

       public Object getData()
       {
            return this.data;
       }

       public LinkedNode getNext()
       {
            return this.next;
       }
}

LinkedNode ADT

 abstract interface Queue{

       abstract void Push( Object x );

       abstract Object pop();

       abstract boolean isEmpty();

 }

 class LinkedNode{
        private Object data;
        private LinkedNode next;
 
        public void setData(Object x)
        {
             this.data = x;
        }

       public void setNext(LinkedNode node)
       {
             this.next = node;
       }

       public Object getData()
       {
            return this.data;
       }

       public LinkedNode getNext()
       {
            return this.next;
       }
}

 class LinkedQueue implements Queue{

          private LinkedNode front;
          private LinkedNode rear;
 
          public LinkedQueue(){
                 this.front = null;
                 this.rear = null;
          }
 
          public void push(Object x){
  
                 LinkedNode newNode = new LinkedNode();

                 newNode.setData( x );
                 newNode.setNext( null );

                 if( isEmpty() )
                 {
                       this.front = newNode;
                       this.rear = newNode;  
                 }
                 else{
                       this.rear.setNext ( newNode );
                       this.rear = newNode;
                 }

          }

          public Object pop(){
   
                 if ( isEmpty() )
                       return null;
  
                 Object data = front.getData();
   
                 LinkedNode prevnode = front;
                 front = front.getNext();
 
                 prevnode = null;
                 return data;
         }

         public Object peak(){
  
                if ( isEmpty() )
                        return null;
                else
                        return front;

         }

         public boolean isEmpty(){
  
                if(front == null)
                        return true;
                else
                        return false;  

          }
 
          public void viewOfAll()
          {
                LinkedNode current = this.front;
  
                System.out.println("출력 ---------");
 
                while ( current != null )
                {
                         System.out.println( current.getData() );
                         current = current.getNext();
                 }

           }

 }

 
public class LinkedQueueProgram{
 
         public static void main(String args[])
         {
                 LinkedQueue queue = new LinkedQueue();
                 queue.push("1번");
                 queue.push("2번");
                 queue.push("3번");
                 queue.viewOfAll();

                 queue.pop(); 
                 queue.viewOfAll();
 
                 queue.push("1번");
                 queue.viewOfAll();

         }
}

 LinkedQueueProgram.java

 abstract interface Queue{

      abstract void push ( Object x ) ;

      abstract Object pop ( ) ;

      abstract boolean isEmpty ( );

      abstract Object peak ( ) ;

 }

 Queue의 ADT

 public class ArrayQueue implements Queue{

      private int front;

      private int rear;

      private int count;

      private int queuesize;

      private Object[] itemArray;

      public ArrayQueue()

      {

               this.front = 0;

               this.rear = 0;

               this.count = 0;

               this.queueSize = 10;

               this.itemArray = new Object [ this.queueSize ];

      }

 } 

 배열 큐 - Circular Queue 구현 - 기본 Instance Variable, Constructor

 rear = ( rear + 1 ) % n

 itemArray[rear] = x ;

 front = ( front + 1 ) % n

 Object data = itemArray ( front );

 
abstract interface Queue{
 
        abstract boolean isEmpty();
        abstract void push(Object x);
        abstract Object pop();
        abstract Object peak(); 
}

class ArrayQueue implements Queue{

         private int front;
         private int rear;
         private int count;
         private int queueSize;
         private int increment;
         private Object[] itemArray;
 
         public ArrayQueue( )
         {
                 this.front = 0;
                 this.rear = 0;
                 this.count = 0;
                 this.increment = 5;
                 this.queueSize = 5;

                 itemArray = new Object[queueSize];
          }

          private void queueFull()
          {
  
                 int prevQueueSize = queueSize;
                 queueSize += increment ;
  
                 Object[] prevItemArr = itemArray.clone();
                 itemArray = new Object[queueSize];
  
                 int i = 0;

                 while( i < prevQueueSize )
                 {
                         itemArray[i] = prevItemArr[front];
                         front = (front + 1) % prevQueueSize;
   
                         i++;
                 }

                 front = 0;
                 rear = count;
        }
 
        public boolean isEmpty(){
                 return (count == 0) ? true : false ;
        }

        public void push(Object x){
  
                 if ( ( count + 1 ) ==  queueSize )
                        queueFull();

                 rear = ( rear + 1 ) % queueSize;
                 itemArray[ rear ] = x;
  
                 count++;

        }

        public Object pop(){

                if( isEmpty() )
                       return null;
  
                front = (front + 1) % queueSize;
                Object item = itemArray[front];
                itemArray[front] = null;
  
                count--;

                return item;
         }
 
          public Object peak(){
  
               if( isEmpty() )
                       return null;
               else
                       return itemArray[front];

          }

           public void viewOfAll( String label )
           {
                   System.out.println ( "\n\n[" + label + "]/-----실험결과" );
    
                   for ( Object x : itemArray )
                  {
                            System.out.println ( x );   

                   }

            }

             public int getCount()
             {
                     return this.count;
             }
 }

 public class QueueProgram{

             public static void main(String args[])
             { 

                     ArrayQueue queue = new ArrayQueue();
  
                     queue.push("1번");
                     queue.push("2번");
                     queue.push("3번");
                     queue.push("4번");
                     queue.viewOfAll("1번");

                     queue.pop();
                     queue.viewOfAll("2번");

                     queue.push("5번");
                     queue.viewOfAll("3번");

                     queue.push("6번");
                     queue.viewOfAll("4번");

                     queue.pop();
                     queue.viewOfAll("5번");

                     queue.pop();
                     queue.viewOfAll("6번");

                     queue.push("7번");
                     queue.viewOfAll("7번");

                     queue.push("8번");
                     queue.viewOfAll("8번");

                     queue.pop();
                     queue.viewOfAll("9번");

                     queue.pop();
                     queue.viewOfAll("11번");

                     queue.push("9번");
                     queue.viewOfAll("12번");

                     queue.push("10번");
                     queue.viewOfAll("13번");

                     queue.push("11번");
                     queue.viewOfAll("14번");

                     queue.push("12번");
                     queue.viewOfAll("15번");
 
         }

}

 QueueProgram.java

/*      
       Data Structure Circular Linked List - rootnode만 이용
       2015. 4. 25
       James
*/ 

class Node

{
        private Object data;
        private Node prev;
        private Node next;

        // Getter
        public Object getdata()
        {
             return this.data;
        }

        public Node getprev()
        {
             return this.prev;
        }

        public Node getnext()
        { 
             return this.next;
        }
 

        // Setter
        public void setdata(Object data)
       {
             this.data = data;
       }

       public void setprev(Node prev)
       {
             this.prev = prev;
       }

       public void setnext(Node next)
       {
             this.next = next;
       }
} 

class LinkedList{

       private Node headnode;
       private long length;
 
       public LinkedList(){
              this.headnode = null;
              this.length = 0;
       }

       public void insert(Object data)
       {
              Node createnode = new Node();  

              createnode.setdata(data);
              createnode.setprev( createnode );
              createnode.setnext( createnode );
  
              if ( this.headnode == null )
              {
                       this.headnode = createnode;
              }
              else
              { 
                      Node firstnode = this.headnode.getnext();   
   
                      // 현재 기억하고 있는 이전 노드 설정
                      createnode.setprev ( this.headnode );

                      // 맨 마지막 노드 처음 위치 지정
                      createnode.setnext ( firstnode );

                      // 현재 노드 -> node 삽입 (Next)
                      this.headnode.setnext( createnode );
   
                      // 현재 노드 -> 다음 노드로 이동
                      this.headnode = this.headnode.getnext();

                      // 맨 처음 노드 마지막 위치 지정
                      firstnode.setprev( this.headnode );
              }

              this.length++;
  
 }
 
 public void remove(Object data)
 {
             Node currentnode = this.headnode.getnext();
             boolean check = false;  

             long cnt = 0;  
  
             // 데이터 검색
             while ( cnt < length )
             {
                       if( currentnode.getdata() == data)
                       {    
                               check = true;
                               break;
                       }

                       currentnode = currentnode.getnext();
   
                       cnt++;
             }

              // 3가지 기준 (맨 처음 자료, 중간 자료, 맨 마지막 자료)
              if ( check == true )
              {
                      Node firstnode = this.headnode.getnext();
                      Node lastnode = this.headnode;
  
                      // 맨 처음 자료
                      if ( currentnode == firstnode )
                      { 
                                // 다음 주소가 firstnode와 일치시
                                if ( this.headnode.getnext ( ) == firstnode ){

                                        Node prevnode = firstnode.getprev();
                                        Node nextnode = firstnode.getnext();
     
                                        firstnode = nextnode;
                                        firstnode.setprev ( prevnode ) ;
                                        this.headnode.setnext ( firstnode ) ;
                               }
                               else
                                        this.headnode = this.headnode.getnext ( ) ; 
                      }

                     // 중간 자료 판별
                     if ( currentnode != firstnode && currentnode != lastnode )
                     {
                               Node prevnode = currentnode.getprev ( ) ;
                               Node nextnode = currentnode.getnext ( ) ;

                               currentnode = prevnode ;
                               currentnode.setnext ( nextnode ) ;
                               nextnode.setprev ( prevnode ); 
                     }

                      // 마지막 자료 판별
                      if ( currentnode == lastnode && this.headnode != null )
                      {
                               Node prevnode = currentnode.getprev ( ) ;

                        
                               prevnode.setnext ( firstnode ) ;
                               firstnode.setprev ( prevnode ) ;
     
                               currentnode = null ;

                               this.headnode = prevnode;
                      }
 
                      this.length--;

                }  

        }
  
        public void view()
        {
                  Node currentnode = this.headnode.getnext();
    
                  long cnt = 1;

                  while ( cnt <= length )
                  {
                           System.out.println( "번호:" + cnt + ", Data:" + currentnode.getdata() ) ;
   
                           currentnode = currentnode.getprev() ;
                           cnt++;
                  } 
         }
 
         public long getlength()
         {
                  return this.length;
         }

          public Node getnode()
          {
                  return this.headnode;
          }

}

public class Ds{

         public static void main(String args[])
        {
             LinkedList list = new LinkedList();

             list.insert("야호1"); 
             list.view();

             list.remove("야호1");
             System.out.println( list.getlength() ) ;
             list.view();
       }

} 

 Ds.java