[4주차] Data Structure 2/4 (스택과 큐, 힙)

스택 & 큐

스택(Stack)

입력과 출력이 한 방향으로 제한

LIFO(Last In First Out, 후입선출) : 가장 나중에 들어온 것이 먼저 나옴

ex) 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에 사용됨

 

• sp: 스택 포인터

private int sp = -1; // 초기값

 

• push(): 스택에 데이터 넣기

public void push(Object o) {
    if(isFull(o)) {
        return;
    }
    
    stack[++sp] = o;
}

 

• pop(): 데이터 최상위 값 빼기

public Object pop() {
    
    if(isEmpty(sp)) {
        return null;
    }
    
    Object o = stack[sp--];
    return o;
    
}

 

• isEmpty(): 스택이 비어있는지 확인하기

private boolean isEmpty(int cnt) {
    return sp == -1 ? true : false;
}

 

• isFull(): 스택이 꽉 차있는지 확인하기

private boolean isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

 

동적 배열 스택

위처럼 구현하면 MAX_SIZE가 존재해야 한다. 

최대 크기가 없는 스택을 만드려면?

1. arraycopy를 활용한 동적배열 사용

public void push(Object o) {
    
    if(isFull(sp)) {
        
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }
    
    stack[sp++] = o;
}

꽉 찼을 경우 사이즈 2배로 증가시키기

 

2. 연결리스트로 구현해도 해결 가능함

public class Node {

    public int data;
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Stack {
    private Node head;
    private Node top;

    public Stack() {
        head = top = null;
    }

    private Node createNode(int data) {
        return new Node(data);
    }

    private boolean isEmpty() {
        return top == null ? true : false;
    }

    public void push(int data) {
        if (isEmpty()) { // 스택이 비어있다면
            head = createNode(data);
            top = head;
        }
        else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
            Node pointer = head;

            while (pointer.next != null)
                pointer = pointer.next;
           	// [질문하기: 탑 노드를 알 고 있는데 이 과정이 필요한가??]

            pointer.next = createNode(data);
            top = pointer.next;
        }
    }

    public int pop() {
        int popData;
        if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
            popData = top.data; // pop될 데이터를 미리 받아놓는다.
            Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터

            if (head == top) // 데이터가 하나라면
                head = top = null;
            else { // 데이터가 2개 이상이라면
                while (pointer.next != top) // top을 가리키는 노드를 찾는다.
                    pointer = pointer.next;

                pointer.next = null; // 마지막 노드의 연결을 끊는다.
                top = pointer; // top을 이동시킨다.
            }
            return popData;
        }
        return -1; // -1은 데이터가 없다는 의미로 지정해둠.

    }

}

 

---

 

큐(Queue)

입력과 출력이 한 쪽 끝

FIFO(First In Frist Out, 선입선출) : 가장 먼저 들어온 것이 가장 먼저 나옴

ex) 버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS에서 사용

 

첫 원소를 front, 마지막 원소를 rear라고 부름

들어올 때 rear로 들어오고, 나올 때는 front 부터 빠지는 특성을 가짐

 

 

• rear, front : 값이 들어오는 곳과 나가는 곳이 달라서 포인터가 2개 필요함

private int size = 0; 
private int rear = -1; 
private int front = -1;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

 

• enQueue() : 데이터 넣기

public void enQueue(Object o) {
    
    if(isFull()) {
        return;
    }
    
    queue[++rear] = o;
}

 

• deQueue() : 데이터 빼기

public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    Object o = queue[front];
    queue[front++] = null;
    return o;
}

 

• is Empty : 큐가 비어있는지 확인

public boolean isEmpty() {
    return front == rear;
}

 

• isFull()

public boolean isFull() {
    return (rear == queueSize-1);
}

 

일반 큐의 단점

큐에 빈 메모리가 남아 있어도 rear가 끝에 도달하면 꽉 차있는 것으로 판단할 수 있음

 

원형 큐

논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함

초기 공백 상태일 때 front와 rear가 0

 

공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워 둠

• 공백 상태 : front == rear
• 포화 상태 : front == (rear + 1) % MAX_SIZE

 

• 기본 값

private int size = 0; 
private int rear = 0; 
private int front = 0;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

 

• enQueue() : 데이터 넣기

public void enQueue(Object o) {
    
    if(isFull()) {
        return;
    }
    
    rear = (++rear) % size;
    queue[rear] = o;
}

rear index 줄 때, size로 나눈 나머지 값으로 설정하는 것 주의(원형 큐)

 

 

• deQueue(): 데이터 빼기

public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    preIndex = front;
    front = (++front) % size;
    Object o = queue[preIndex];
    return o;
}

 

• isEmpth()

public boolean isEmpty() {
    return front == rear;
}

 

• isFull()

public boolean isFull() {
    return ((rear+1) % size == front);
}

 

원형 큐의 단점

메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한됨

 

연결리스트 큐

큐의 크기가 제한이 없고, 삽입과 삭제가 용이하다. 

 

• enQueue

public void enqueue(E item) {
    Node oldlast = tail; // 기존의 tail 임시 저장
    tail = new Node; // 새로운 tail 생성
    tail.item = item;
    tail.next = null;
    if(isEmpty()) head = tail; // 큐가 비어있으면 head와 tail 모두 같은 노드 가리킴
    else oldlast.next = tail; // 비어있지 않으면 기존 tail의 next = 새로운 tail로 설정
}

 

• deQueue()

public T dequeue() {
    // 비어있으면
    if(isEmpty()) {
        tail = head;
        return null;
    }
    // 비어있지 않으면
    else {
        T item = head.item; // 빼낼 현재 front 값 저장
        head = head.next; // front를 다음 노드로 설정
        return item;
    }
}

 

---

 

힙(Heap)

힙은, 우선순위 큐를 위해 만들어진 자료구조

 

우선순위 큐

우선순위의 개념을 큐에 도입한 자료구조

우선순위가 높은 데이터가 먼저 나감

ex) 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 사용됨

 

배열, 연결리스트, 힙으로 구혐됨 (힙으로 구현하는 것이 가장 효율적임)

 

힙의 경우

삽입 : O(logn), 삭제 : O(logn)

 

1. 힙의 개념

완전 이진 트리의 일종

반정렬 상태(느슨한 정렬 상태, 완전히 정렬되지는 않고 큰 값이 레벨에 있고 작은 값이 하위 레벨에 있다는 정도를 뜻 함)

힙 트리는 중복된 값 허용 (이진 탐색 트리는 중복값 허용하지 않음)

 

힙의 종류

최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

 

최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

2. 구현

힙을 저장하는 표준적인 자료구조는 배열

구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용되지 않음

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음

 

부모 노드와 자식 노드 관계

• 왼쪽 자식 index = (부모 index) * 2
• 오른쪽 자식 index = (부모 index) * 2 + 1
• 부모 index = (자식 index) / 2

 

힙의 삽입

1. 힙의 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입

2. 새로운 노드를 부모 노드들과 교환

 

void insert_max_heap(int x) {
    
    maxHeap[++heapSize] = x; 
    // 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
    
    for( int i = heapSize; i > 1; i /= 2) {
        
        // 마지막 노드가 자신의 부모 노드보다 크면 swap
        if(maxHeap[i/2] < maxHeap[i]) {
            swap(i/2, i);
        } else {
            break;
        }
        
    }
}

 

힙의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다. 

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴

3. 힙을 제구성

int delete_max_heap() {
    
    if(heapSize == 0) // 배열이 비어있으면 리턴
        return 0;
    
    int item = maxHeap[1]; // 루트 노드의 값을 저장
    maxHeap[1] = maxHeap[heapSize]; // 마지막 노드 값을 루트로 이동
    maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드 0 초기화
    
    for(int i = 1; i*2 <= heapSize;) {
        
        // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝
        if(maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) {
            break;
        }
        
        // 왼쪽 노드가 더 큰 경우, swap
        else if (maxHeap[i*2] > maxHeap[i*2+1]) {
            swap(i, i*2);
            i = i*2;
        }
        
        // 오른쪽 노드가 더 큰 경우
        else {
            swap(i, i*2+1);
            i = i*2+1;
        }
    }
    
    return item;
    
}

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog