큐와 스택 (Queue & Stack)

이건 알고리즘이라기 보다는 자료구조지만, 일단 기본이니까 짚고 넘어가보자.

오늘 있었던 2022 Sogang Programming Open Contest에서 쉬워보였던 스택/큐 문제를 못풀어서 그런것도 있고.. 일단 고

---

큐와 스택에 대해 가장 단순하게 설명하는 방법은 FIFO와 LIFO다.

FIFO : First In First Out

LIFO : Last In First Out

 

큐는 FIFO 형식으로 넣은 순서대로 출력하는 구조로 모두가 같은 속도로 달리는 터널이라고 생각하면 쉽다.

모두가 같은 속도로 달리고 있기 때문에, 먼저 들어간 차가 나중에 들어간 차보다 먼저 터널을 탈출할 것은 자명하다.

스택은 LIFO 형식으로 가장 늦게 넣은것이 먼저 출력된다. 스택은 하노이의 탑을 생각하면 편하다.

가장 나중에 쌓아올린 것을 가장 먼저 출력해야한다.

 

비유를 뭐 이딴 거지같은걸로 해놔서 더 헷갈린다! 할 수도 있으니 코드로 보자.

class Queue <T> {
    T[] queue;
    int push;
    int pop;
    
    public void push(T element) {
    	queue[push++] = element;
    }
    
    public T pop() {
    	return queue[pop++];
    }
}

예시를 위해 작성한 코드로, 배열 queue의 크기는 무한하다고 생각하고 보자.

push는 새로운 데이터가 입력될 포인터, pop은 데이터가 출력될 포인터다.

T는 제너릭을 쓴건데.. 잘 모른다면 그냥 Object로 되있다고 생각하면 된다.

 

먼저 큐에 원소를 3개 집어넣어 보겠다.

 push(E1) : queue[0] = E1, length = 1;
 push(E2) : queue[1] = E2, length = 2;
 push(E3) : queue[2] = E3, length = 3;

 

그리고 이 큐에서 원소를 하나 출력하면

  pop() : return queue[0](=E1), pop = 1

이 될 것이고, 두 번 더 출력하면 E2, E3의 순서로 출력될 것이다.

이렇게 '입력한 순서를 지켜서 출력'하는 방식이 큐 (Queue)다.

 

우리가 pop을 할 때 NPE를 보지 않으려면, 큐가 비어있는지 알아야할 것이다.

큐가 비었는지 확인하는 방법은 간단하다.

public boolean empty(){
    return push == pop;
}

push값에 데이터를 입력하는데, 데이터를 입력해야할 곳을 출력하려고 하면 당연히 NULL일 것이다.

※ 큐 구현 문제 (https://www.acmicpc.net/problem/10845)

 

 

다음으로 스택은 어떨까?

class Stack <T> {
    T[] array;
    int pointer;
    
    public void push(T element) {
    	array[pointer++] = element;
    }
    
    public T pop() {
    	return array[--pointer];
    }
}

스택은 더 쉽다.

현실에서 물건을 쌓아 올리면 위에 있는 것 부터 빼듯이, 스택도 '마지막 입력을 가장 먼저 출력'한다.

 

스택이 비었는지 확인하는 방법은?

public boolean empty() {
    return pointer == 0;
}

pop함수를 보면 간단하다.

array[--pointer]를 통해 값을 빼내고 있는데, pointer가 0이라면 IndexOutOfBound가 뜰 것이다.

이를 통해 pointer가 0이면 Empty라는 사실을 쉽게 생각해낼 수 있다.

※ 스택 구현 문제 (https://www.acmicpc.net/problem/10828)

 

 

아는 것보다 가르치는게 더 힘들다고, 아는 내용을 글로 쓰는 것도 뭐라고 써야할지 생각하니 막막해서 대충 의식흐름대로 쓰긴 했는데, 알고리즘이 아니라 자료구조기 때문에 단순한 스택과 큐는 쉬우므로, 개념을 한번 보고 구현 문제를 풀어보면 쉽게 스르륵 이해가 될 것이다.

 

간단한 큐와 스택만 하면 섭섭하니까 우선순위 큐 (Priority Queue)도 보자.

사실 우선순위 큐는 큐보다는 Heap Tree라고 하는게 더 정확하지 않을까 라고 생각하는데...

네이밍이 큐라서 일단 트리보다 먼저 해보도록 하겠다.

 

'우선순위'큐 이기 때문에, 큐의 성질이였던 FIFO는 죽어버렸다.

큐에 데이터를 순서대로 집어넣고, 꺼낼 때 우선순위에 따라서 꺼내는 방식인데.

가장 우선순위가 높은 것부터 꺼내냐 혹은 낮은 것부터 꺼내냐에 따라 최대 힙, 최소 힙으로 구분된다.

 

.

위의 두 개와 달리, '트리'개념에 가깝다 보니 실제로 문제를 푼 코드로 가져와봤다.

※ 최대 힙 구현 (https://www.acmicpc.net/problem/11279)

※ 최소 힙 구현 (https://www.acmicpc.net/problem/1927)

 

내 코드에서는 트리를 포화이진트리로 만들어버리기 위해, log를 이용해 depth를 구한 후 배열의 크기를 설정했는데, 이런 방식은 문제에서 주어지는 N의 크기가 커지면 답이 없어지므로, 예상되는 범위에서 만들면 좋다.

물론, 이 문제는 입력의 범위가 제대로 주어지지 않아서 N+1로 대체하는거라서 큰 차이는 없다.

 

기본적으로 우선순위 큐의 방식은 간단하다.

데이터를 삽입(push)할 때는 가장 끝 노드에 넣은 뒤, 부모 노드와 비교, Swap하면서 올라온다.

데이터를 추출(pop)할 때는 1번 노드의 값을 가져온 뒤, 가장 끝 노드 값을 1번 노드에 넣고,

1번 노드의 값을 자식 2개와 비교하면서 Swap하면 된다.

 

push의 경우는 끝에서 부모와 비교하면서 올라가서 IndexOutOfBound가 일어날 일이 없지만,

pop의 경우는 위에서 아래로 탐색하는 Top-Down방식이기 때문에 IndexOutOfBound를 주의해야한다.

 

쉽게 구현하는 방법은, 조회를 할 자식노드의 Key가 마지막 노드의 Key를 넘냐 안넘냐를 확인하면 된다.

내 코드를 보면 push에서 데이터를 length에 넣고 있는 것을 볼 수 있는데,

조회할 자식의 Key가 length보다 크거나 같으면 빈 노드 or 트리 바깥을 조회하는 것이므로 캔슬해야한다.

자식 노드가 2개기 때문에 일반적으로 두 번 비교를 해야하는데,

이게 맘에 안들어서 나는 포화 이진 트리 크기로 대체한것이다.

 

아무튼, 데이터를 전부 넣고 정렬하는 것은 O(N *logN)의 시간 복잡도를 가지므로,

Priority Queue를 이용하면 O(logN)으로 최소값 혹은 최대값을 추출할 수 있다는 이점이 있다는 것을 알아두면 좋을 것이다.