[DataStructures] 큐(Queue) - 동적 큐(DynamicQueue)

큐(Queue) - 동적 큐(DynamicQueue)

- 큐의 수용량이 초과 되면 자동으로 배열의 크기를 늘린다

1. 구현

1) 초기화

?

1 2 3 4 5 6 7 8 9

int rear = -1; int front = 0; int currentSize = 0; private int[] queueArr; private int capacity = 2;   public DynamicQueue(){     this.queueArr = new int[capacity]; }

- 동적으로 늘어날 것을 감안하여 사이즈 지정

2) enQueue(), isQueueFull()

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public void enqueue(int element){     if(isQueueFull()){         System.out.println("Queue is full");         increaseCapacity();     }     rear++;     if(rear == capacity){         rear = 0;     }     currentSize++;     this.queueArr[rear] = element;     System.out.println("adding:"+element);           System.out.println("rear:"+rear); }   public boolean isQueueFull(){     return(currentSize == capacity); }

 

3) deQueue(), isQueueEmpty()

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public void dequeue(){     if(isQueueEmpty()){         System.out.println("Queue is empty");     }else{         front++;         if(front > queueArr.length-1){             System.out.println("dequeue:"+this.queueArr[front-1]);             front = 0;         }else{             System.out.println("dequeue:"+this.queueArr[front-1]);         }         currentSize--;               System.out.println("front:"+front);     } }   public boolean isQueueEmpty(){     return(currentSize == 0); }

 

4) increaseCapacity()

?

1 2 3 4 5 6 7 8 9 10 11 12 13

public void increaseCapacity(){               this.capacity = capacity * 2;     int[] newArry = new int[capacity];           for(int i = 0; i<currentSize; i++){         newArry[i] = queueArr[i];     }     this.queueArr = newArry;           System.out.println("increase Size: "+this.queueArr.length);     this.rear = currentSize-1; }

 

5) main()

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public static void main(String[]args){               DynamicQueue qq = new DynamicQueue();         qq.enqueue(1);         qq.enqueue(2);         qq.enqueue(3);         qq.dequeue();         qq.dequeue();         qq.dequeue();         qq.enqueue(4);         qq.dequeue();             qq.enqueue(5);         qq.enqueue(6);           }