[자료구조(Data Structure)] - 5. Circular Queue with Array

[자료구조(Data Structure)] - 5. Circular Queue with Array

 

먼저 환형 큐 with 배열을 소개하면, 여러분들 원으로 된 시계 잘 아신가요??

 

1. 잔머리 굴려보기

 

 

실제로는 원이 아닙니다. 배열 index가 마치 회전하는 듯한 연상이 이해하는 데 도움이 되기 때문에 그려 놓은 겁니다.

예를 들어 저기 원이 Size가 4개인데, 회전하는 데 있어서 회전을 균일하게 잡아줄 공간이 필요합니다.

 

저 원이 예를 들어 Size가 4라고 하면, 실제로 사용가능한 공간은 Size 3입니다.

 

잉여공간 1개를 부여하지 않으면, rear index가 기존에 있는 데이터를 하나 잡아 먹게 됩니다.

(이 부분은 여러분들이 한번 아래의 코드를 수정해서 생각해보시기 바랍니다.)

(또는 종이로 한번 그려보시기 바랍니다.)

 

갑자기 설명하는데, 잔 테크닉 먼저 이야기해서 난해하셨을 것 같습니다.

다시 기본 원리에 대해 소개 해드리겠습니다.

 

2. 기본 원리는?

 

먼저 동작 원리를 구현한 결과입니다. (파워포인트로 그리기엔 솔직히 귀찮고 힘든 일입니다.)

대신 코드 동작으로 똑같이 표현해드리겠습니다.

 

먼저 Queue 자료 구조의 ADT형을 이해하기에 앞서 용어를 이해하기 쉽게 설명해드리고 ADT를 설명해드리겠습니다.

push (어떤 책에선 enqueue( datatype x ) ), pop (어떤 책에선 dequeue ( ) )라고 표기합니다.

 

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

Queue의 ADT

 

큐(Singly Queue), 환형 큐(Circular Queue)나, 연결 큐(Linked Queue) 등 기본 ADT는 이걸로 사용합니다.

이건 Stack 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

Push(삽입) 원리

 

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

 

Pop(인출) 원리

 

front = ( front + 1 ) % n  Object data = itemArray ( front );

 

 

3. 코드로 한번 실험해보세요.

 

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