'Algorithm&DataStructures'에 해당되는 글 38건

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

큐(Queue) - 간단큐예제(SimpleQueue) 

1. 구현

- enqueue : 요소를 삽입한다

- dequeue : 요소 추출한다

- FIFO(First In First Out)

1) 변수 초기화

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

2) enqueue(), isQueueFull()

public void enQueue(int element){ if(isQueueFull()){ System.out.println("Queue is full"); }else{ rear++; //가득찬 후에 dequeue하고 다시 enqueue 할때를 위해 rear를 초기화 한다 if(rear == capacity){ rear = 0; } currentSize++; System.out.println("adding:"+element); this.queueArr[rear] = element; } } public boolean isQueueFull(){ return(currentSize == capacity ); }  

3) dequeue(), isQueueEmpty()

public void deQueue(){ if(isQueueEmpty()){ System.out.println("Queue is empty"); }else{ front++; //가든찬 queue를 다 제거하고 다시 처음부터 입력된 큐를 빼기위해 front 초기화 한다 // 초기화된 front 0 값으로 후에 영향을 주지 않기 위해 if else 처리 if(front == capacity){ System.out.println(this.queueArr[front-1]); front = 0; }else{ System.out.println(this.queueArr[front-1]); } currentSize--; } } public boolean isQueueEmpty(){ return(currentSize == 0); }  

스택(Stack) - 스택을 이용한 이진수변경(ConvertDecimalIntoBinary)

- 십 진수를 이진 수로 변경한다

1. DynamicStackImpl.class

class DynamicStackImp{ private int top; private int stackSize; private int[] stackArr; public DynamicStackImp(int size){ this.top = -1; this.stackSize = size; this.stackArr = new int[stackSize]; } public void push(int element){ if(this.isStackFull()){ System.out.println("Stack is full"); this.increaseCapacity(); } stackArr[++top] = element; } public int pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } return stackArr[top--]; } public boolean isStackEmpty(){ return(top == -1); } public boolean isStackFull(){ return(top == stackSize -1); } public void increaseCapacity(){ int[] newArry = new int[stackSize * 2]; for(int i = 0; i<stackSize; i++){ newArry[i] = stackArr[i]; } System.out.println("Stack size is extended"); this.stackArr = newArry; this.stackSize = stackSize *2; } }

2. ConvertDecimalIntoBinary.class

1) converter()

public String converter(int element) throws Exception{ DynamicStackImp stack = new DynamicStackImp(5); StringBuilder add = new StringBuilder(); int remainder = 0; int quotient = element; boolean flag = true; while(flag){ remainder = quotient%2; quotient = quotient/2; stack.push(remainder); if(quotient == 0 || quotient == 1){ stack.push(quotient); flag = false; } } while(!stack.isStackEmpty()){ add.append(stack.pop()); } return add.toString(); }  

2) main()

public static void main(String[]args) throws Exception{ ConvertDecimalIntoBinary convert = new ConvertDecimalIntoBinary(); System.out.println(convert.converter(41)); }