JAVA 풀스택 40일차 - Algorithm (재귀함수 / 이중연결리스트 / 스택,큐)

1. 재귀함수 (Recursion)

자기 자신을 다시 호출하는 함수

1-1 특징

함수 안에서 자기 자신을 다시 실행

종료 조건이 반드시 있어야 함

1-2 팩토리얼 함수

public static int factorial(int no) {
    return (no==1)? 1: no*factorial(no-1);
}

- no가 1이면 1 반환 아니면 '현재값 * factorial(no-1)' 반환

2. 유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

public static int eculid(int no1, int no2) {
    if(no2==0) {
        return no1;
    }else {
        return eculid(no2,no1%no2);
    }
}

- 큰 수를 작은 수로 나눈 나머지를 이용
- 나머지가 0이 될 때의 수가 최대공약수

3. 하노이탑

public static void hanoi(int no, int x, int y) {
	if(no>1) {
		hanoi(no-1,x,6-x-y);
	}
	System.out.println("원판: " + no +"을 " + x + "기둥에서 " + y + "기둥으로 옮김");	
	if(no>1) {
		hanoi(no-1,6-x-y,y);
	}
}

 

매개변수	의미
no	원판 개수
x	시작 기둥
y	목표 기둥
6-x-y	남은 기둥 번호

4. 이중 연결 리스트

4-1 연결 리스트

데이터를 배열처럼 순서대로 저장하지만 각 데이터가 다음 데이터를 직접 가리키는 구조

배열은 인덱스로 접근하지만, 연결 리스트는 노드끼리 연결

4-2 이중 연결 리스트

각 노드가 두방향을 기억

이전 노드 ← 현재 노드 → 다음 노드

4-3 Node 클래스

class Node<E>{
	private E data;    
	private Node<E> prev;  
	private Node<E> next; 	
    
	Node(){
		data = null;
		prev = this;
		next = this;
	}
	Node(E obj, Node<E> prev, Node<E> next){
		data = obj;
		this.prev = prev;
		this.next = next;
	}
}

필드	의미
data	실제 저장할 데이터
prev	이전 노드 주소
next	다음 노드 주소

4-4 head, crnt

private Node<E> head;
private Node<E> crnt;

 

변수	의미
head	리스트의 시작을 관리하는 더미 노드
crnt	현재 선택된 노드

4-5 리스트가 비었는지 확인

public boolean isEmpty() {
    return head.next == head;
}

- head.next 가 head라면 중간에 데이터 노드가 없다는 것

head → head

상태이면 리스트가 비어있다는 것

4-6 데이터 추가

public void add(E obj) {
    Node<E> node = new Node<E>(obj,crnt,crnt.next);
    crnt.next = crnt.next.prev = node;
    crnt = node;
}

- 현재 노드 뒤에 새로운 노드 추가

현재 노드와 다음 노드 사이에 새 노드를 끼워 넣는 것

4-7 맨 앞 / 맨 뒤 추가

public void addFirst(E obj) {
    crnt = head;
    add(obj);
}

- head 바로 뒤에 추가하므로 첫번째 위치로 들어감

public void addLast(E obj) {
    crnt = head.prev;
    add(obj);
}

- 마지막 노드 뒤에 추가하므로 맨 뒤에 들어감

4-8 노드 삭제

public void removeCrnt() {
    if(!isEmpty()) {
        crnt.prev.next = crnt.next;
        crnt.next.prev = crnt.prev;
        crnt = crnt.prev;
    }
}

 - 앞 노드와 뒤 노드를 서로 연결해서 삭제할 노드를 연결 구조에서 제외

4-9 전체 삭제

public void clear() {
    while(!isEmpty()) {
        removeFirst();
    }
}

- 리스트가 빌 때까지 첫 번째 노드를 계속 삭제

5. stack

마지막에 넣은 데이터가 먼저 나오는 방식의 자료 구조 (LIFO)

5-1 stack 필드

private int[] s;
private int capacity;
private int ptr;

- 배열을 이용하여 정수 데이터 저장

 

필드	의미
s	데이터 저장 배열
capacity	스택 최대 용량
ptr	현재 저장된 데이터 개수이자 다음 저장 위치

5-2 push()

스택에 데이터를 추가하는 기능

public int push(int no) throws Exception {
    if(ptr>= capacity) {
        System.out.println("[스택이 가득 참]");
        throw new Exception();
    }
    return s[ptr++] = no;
}

ptr 위치에 값을 넣고 ptr을 1 증가시킴

5-3 pop()

가장 마지막에 넣은 데이터를 꺼냄

public int pop() throws Exception {
    if(ptr <= 0) {
        System.out.println("[스택이 비었음]");
        throw new Exception();
    }
    int res = s[--ptr];
    return res;
}

ptr을 먼저 1 줄이고, 그 위치의 데이터를 꺼냄 (배열의 인덱스는 0부터 시작)

5-4 peek()

데이터를 꺼내지는 않고 맨 위 데이터를 확인만 함

public int peek() throws Exception {
    if(ptr <= 0) {
        System.out.println("[스택이 비었음]");
        throw new Exception();
    }
    return s[ptr-1];
}

6. Queue

먼저 넣은 데이터가 먼저 나오는 자료구조(FIFO)

6-1 Queue 필드

private int[] q;
private int capacity;
private int num;
private int front;
private int rear;

 

필드	의미
q	데이터 저장 배열
capacity	큐 최대 용량
num	현재 저장된 데이터 개수
front	가장 앞 데이터 위치
rear	다음 데이터가 들어갈 위치

6-2 enqueue()

큐에 데이터를 추가하는 기능

public int enqueue(int no) throws Exception {
    if(num>=capacity) {
        System.out.println("[큐가 가득참]");
        throw new Exception();
    }
    q[rear++] = no;
    num++;

    if(rear == capacity) {
        rear = 0;
    }
    return no;
}

데이터는 rear 위치에 들어가고, rear은 다음 위치로 이동

6-3 dequeue()

가장 먼저 들어온 데이터를 꺼냄

public int dequeue() throws Exception {
    if(num <= 0) {
        System.out.println("[큐가 비었다]");
        throw new Exception();
    }

    int val = q[front++];
    num--;

    if(front == capacity) {
        front = 0;
    }

    return val;
}

데이터는 front 위치에서 꺼내고, front는 다음 위치로 이

6-4 원형 큐

if(rear == capacity) {
    rear = 0;
}

if(front == capacity) {
    front = 0;
}

배열의 끝까지 갔을 경우 다시 0번 인덱스로 돌아감

배열을 일직선이 아니라 동그랗게 이어진 것처럼 사용

7. Stack / Queue 차이

구분	Stack	Queue
구조	마지막 데이터가 먼저 나옴	먼저 넣은 데이터가 먼저 나옴
방식	LIFO	FIFO
비유	접시 쌓기	줄 서기
추가	push	enqueue
삭제	pop	dequeue
확인	peek	peek