[자료구조] Stack, Queue

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

Stack

• Insert / Delete만 제공한다. search가 없다.
• push를 통해 data를 추가하고, pop을 통해 data를 삭제한다.
• 마지막에 추가한(push) data가 먼저 삭제되기때문에 Last in First out 줄여서 LIFO 라고도 부른다.
• Push와 Pop모두 상수시간안에 진행된다. O(1)

▶ stack을 구현할때는 다음에 넣을 자리를 가리키는 stack pointer가 하나 필요하다.

위의 사진에서 예를들어 2를 막 push한 상황이라면 2의 위를 stack pointer가 가리키고 있을 것 이다.

 

Queue

• Insert / Delete만 제공한다. search가 없다.
• enqueue를 통해 data를 추가하고, dequeue를 통해 data를 삭제한다.
• 먼저 추가한(enqueue) data가 먼저 삭제되기때문에 First in First out 줄여서 FIFO 라고도 부른다.
• enqueue와 dequeue 모두 O(1)안에 진행된다.

queue에서는 stack pointer와 같이 다음 자료를 삽입할 곳을 가리키는 Tail과 자료를 꺼낼 위치를 가리키는 Head가 있다.

다음 사진을 통해 확인해 보자. (수업에서와는 조금 다르게~)

문제는 이 Head와 Tail이 같은 곳을 가리키는 경우에 Queue가 비어있다는 의미와 Queue가 가득차있다는 의미 둘다가 가능하다.

따라서 queue에서는 한칸은 공백으로 만들어 가득찬 경우에 tail이 그 공백을, head는 그 한칸 앞을 가리키고 있도록 만들면 된다.

 

Stack, Queue 응용 : 미로찾기

수업중에서는 현위치 중심으로 인근 8방위를 생각하자고 하셨으나, 글 정리에서는 간단하게 상,하,좌,우 만 고려하도록 작성하겠다.

 

다음과 같은 미로가 있다고 생각해 보자.

왼쪽 상단 모퉁이가 시작지점으로 좌표는 (0, 0)이 된다. 또한 각 칸마다 있는 0은 진행가능한 길을, 1을 막힌 벽을 의미한다.

매 노드를 방문할때마다 방문 노드 또한 표시해줄 수 있어야 한다.

 

● DFA 명시적 Stack

int Map[M][N]; // 미로
int i,j; // 현재 위치

int Find() {
    i = j = 0; Map[i][j] = '*';
    while (1) {
        if (i == M - 1 && j == N - 1) // 미로탈출 성공
        Map[i][j+1], Map[i][j-1], Map[i+1][j], Map[i-1][j] 중 '0'이 있는가?
        '0' 이 있으면 전진 (다음 코드는 오른쪽으로 이동했다 가정)
        Push(i, j); i = i + 1; Map[i][j] = '*';

        0이 없으면
            stack empty이면 실패.
            j = Pop();
            i = Pop();
    }
}

 

<DFS의 정확성 검증>

시작 위치에서 갈수있는 길은 전부다 간다는 것 을 증명하려 한다. 이는 귀류법으로 증명해보자.

 

1) (0, 0)에서 목표지점인 (s, t)로 가는 길이 있다. 모든 가능한 경로를 다 탐색하면 해답이 나온다 => Brute Force 방식

 

2) (0, 0) -> (a1, b1) -> (a2, b2) -> ... -> (s, t)인 해답으로 가는 경로가 있다. 하지만 귀류법으로 목적지인 (s, t)에 안간다고 생각해보자.

o(가봄) o o ... o x ... x

3) 경로를 따라 가던중 막 아직 안가본 어떤 칸(Ap, Bp)에 도착했다 가정해 보자. 지금 막 도착했으니 방문표시를 한 후, 인근 칸들에 대한 탐색을 해야한다. 이때 아직 안간곳(Ap+1, Bp+1)이 있다면 무조건 전진해야한다.

 

4) 하지만 (Ap+1, Bp+1)에 안갔다라는 것은 전진을 안했다는 말이다. 이는 불가능 하다.

따라서 목적지 까지 가는 길이 있으면 반드시 찾는다.

 

● BFS 명시적 Queue

int Map[M][N];
int i, j;

int Find() {
    Enqueue(0, 0);
    while(1) {
         // if Queue is empty, break;
         (i, j) = Dequeue();
         // (i, j)가 이미 가본곳이라면 포기
         // (i, j)가 안가본 곳 이라면, 방문 표시를 한 후,
         // 주변칸들은 Queue에 Enqueue한다.
    }    
}