'Algorithm&DataStructures/Queue'에 해당되는 글 5건

큐(queue) - 우선순위 큐(Priority queue)

- 큐에 들어있는 값 중 큰 순서대로 밖으로 나온다

1. PriorityQueue.class

1) 초기화

@SuppressWarnings("rawtypes") private Comparable[] pQueue; private int index = 0; public PriorityQueue(int size){ pQueue = new Comparable[size]; }

- SuppressWarning 이란 이클립스에게 해당 경고는 무시하라는 표시를 한다

- Comparable 인터페이스형 배열을 만든다

2) insertQueue(Comparable element)

public void insertQueue(Comparable element){ if(index == pQueue.length){ System.out.println("Queue is full"); return; } pQueue[index] = element; index++; }  

3) Comparable remove()

public Comparable remove(){ if(index == 0){ System.out.println("Queue is empty"); return null; } int maxIndex = 0; for(int i = 1; i<index; i++){ if(pQueue[i].compareTo(pQueue[maxIndex]) > 0){ maxIndex = i; } } Comparable result = pQueue[maxIndex]; System.out.println("removing:"+result); index--; pQueue[maxIndex] = pQueue[index]; pQueue[index] = null; return result; }  

- for문을 이용하여 각각의 요소들을 비교한다

- 가장큰 요소의 인덱스 번호를 max에 저장한 후 그 값을 리턴한다

4) toString(), main()

public String toString(){ String str = "["; for(int i=0; i < pQueue.length-1; i++){ str += pQueue[i]+","; } str += pQueue[pQueue.length-1] +"]"; return str; } public static void main(String[]args){ PriorityQueue pQueue = new PriorityQueue(5); pQueue.insertQueue(30); pQueue.insertQueue(5); pQueue.insertQueue(10); pQueue.insertQueue(1); pQueue.insertQueue(2); System.out.println(pQueue); pQueue.remove(); pQueue.remove(); pQueue.remove(); System.out.println(pQueue); }  

더블링크드리스트 데큐 - Deque using doubly linked list

- 데큐(deque)를 링크드 리스트로 구현한다

1. Node<T>.class

class Node<T>{ private T data; private Node<T> next; private Node<T> pre; public T getData() { return data; } public void setData(T data) { this.data = data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } public Node<T> getPre() { return pre; } public void setPre(Node<T> pre) { this.pre = pre; } }

- doubly linked list 이기 때문에 pre, next 가 선언 되었다

2. DoubleLinkedListDeque<T>.class

1) 초기화

Node<T> front; Node<T> rear; int size = 0;  

- 링크드 리스트로 구현하기 때문에 삽입과 삭제되는 부분을 컨트롤할 front, rear가 필요하다

- size를 지정함으로 유연하게 deque를 컨트롤 한다

2) addFirst(E element), addLast(E element)

 public void addFront(T element){ Node<T> newNode = new Node<>(); newNode.setData(element); newNode.setNext(front); if(front != null){ front.setPre(newNode); } if(front == null){ rear = newNode; } front = newNode; size++; } public void addLast(T element){ Node<T> newNode = new Node<>(); newNode.setPre(rear); newNode.setData(element); if(rear != null){ rear.setNext(newNode); } if(rear == null){ front = newNode; } rear = newNode; size++; }  

- deque 이기 때문에 삽입이 자유롭다

3) removeFront(), removeLast()

 public void removeLast()throws Exception{ if(isNullCheck()){ throw new Exception("List is null"); }else{ Node<T> temp = rear.getPre(); if(temp != null){ temp.setNext(null); } if(temp == null){ front = null; } rear = temp; temp = null; size--; } } public void removeFront()throws Exception{ if(isNullCheck()){ throw new Exception("List is null"); }{ Node<T> temp = front.getNext(); if(temp != null){ temp.setPre(null); } if(temp == null){ rear = null; } front = temp; temp = null; size--; } }  

4) isNullCheck(), toString()

 public boolean isNullCheck(){ return(size == 0); } public String toString(){ Node<T> temp = front; String str = "{"; if(temp != null){ for(int i = 0; i<size-1; i++){ str += temp.getData()+","; temp = temp.getNext(); } str += temp.getData(); } str += "}"; return str; }  

- 큐가 비었는지 체크와 현재 상태를 출력하는 함수 이다

5) main()

 public static void main(String[]args){ DoubleLinkedListDeque<Integer> list = new DoubleLinkedListDeque<>(); try{ list.addFront(1); list.addFront(2); list.addFront(3); list.addLast(4); list.addLast(5); list.removeFront(); list.removeLast(); list.removeLast(); list.removeLast(); list.removeLast(); System.out.println(list); }catch(Exception e){ System.out.println(e.getMessage()); } }  

큐(Queue) - 데큐 ArrayList(Double-ended queue (Decue using ArrayList))

- 일반 큐와 달리 데큐는 rear와 front에서 동시에 삽입 삭제가 이루어 질수 있다

- ArrayList를 사용하여 구현

1. ArrayList

1) 추가(add)

List<Integer> list = new ArrayList<>(); //자동으로 배열의 뒤로 추가 list.add(10); //특정 인덱스 위치에 추가 list.add(1,10);  

2) 삭제(remove)

//특정 인덱스 삭제 list.remove(0);  

3) 가져오기(get)

//특정 인덱스 값 가져오기 list.get(1);  

2. 구현 - ArrayList

1) 정의

List<Integer> decue = new ArrayList<>();

- ArrayList 특성상 사이즈가 동적으로 증가한다, 그렇기 때문에 사이즈를 처음에 명시 하지 않아도 된다

- ArrayList 만 생성

2) insertFront(), insertRear()

public void insertFront(int element){ System.out.println("inserting at front:"+element); decue.add(0,element); System.out.println(decue); } public void insertRear(int element){ System.out.println("inserting at rear:"+element); decue.add(element); System.out.println(decue); }  

3) removeFront(), removeRear()

public void removeFront(){ if(decue.isEmpty()){ System.out.println("queus is empty"); return; } System.out.println("removing at front:"+decue.remove(0)); System.out.println(decue); } public void removeRear(){ if(decue.isEmpty()){ System.out.println("decue is empty"); return; } System.out.println("removing at rear:"+decue.remove(decue.size()-1)); System.out.println(decue); }  

4) peekFront(), peekRear()

public int peekFront(){ int element = decue.get(0); System.out.println("Element is front" + element); return element; } public int peekRear(){ int element = decue.get(decue.size()-1); System.out.println("Element is front" + element); return element; }  

5) main()

public static void main(String[]args){ DoubleEndedQueue que = new DoubleEndedQueue(); que.insertFront(50); que.insertFront(30); que.insertRear(10); que.insertRear(60); que.removeFront(); que.removeRear(); que.removeFront(); que.removeRear(); que.removeFront(); }  

큐(Queue) - 동적 큐(DynamicQueue)

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

1. 구현

1) 초기화

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()

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()

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()

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()

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); }