• Insert/Delete 만 제공한다. Search는 제공하지 않는다.
• Insert/Delete를 Push/Pop이라고 부른다.
• Last in, First out. 나중에 들어간 데이터가 먼저 나간다.
• 성능
• Push : O(1)
• Pop : O(1)

• Insert/Delete 만 제공한다.
• First in, First out. 먼저 들어간 데이터가 먼저 나간다.
• Insert는 O(1), Delete는 O(1) 시간이 걸린다.

int Stack[N];
SP = 0;

void Push(int x) {
    Stack[SP++] = x;
}

int Pop() {
    return Stack[--SP];
}

Queue 구현

int Queue[N];
int Head = 0, Tail = 0;

int isEmpty() {
    return Head == Tail;
}

void insert(int x) {
    Queue[Head] = x;
    Head = (Head + 1) % N;
}

int delete() {
    int RetVal;
    RetVal = Queue[Tail];
    Tail = (Tail + 1) % N;
    return RetVal;
}

Stack, Queue의 응용 - 미로 찾기

char Map[M][N] = {...};
int i = 0, j = 0;  // 현재 방문 위치. (0, 0)에서 시작

int[][] Find() {
    while (i != M-1 || j != N-1) {  // 미로 끝에 도달할 때 까지 반복
        int ip = -1, jp = -1;
        인접한 위치에 빈 공간('0')이 있으면 좌표를 ip, jp에 대입;
        if (ip != -1) {  // 근처에 빈 공간이 있다면
            push(i);
            push(j);
            i = ip;
            j = jp;
            Map[i][j] = '*';
        }
        else {  // 근처에 빈 공간이 없다면
            Map[i][j] = 'X';  // 후진한 위치는 'X'로 표시
            j = Pop();
            i = Pop();
        }
    }
    return Map;
}

• (0, 0)에서 (s, t)로 가는 길이 존재할 때, 알고리즘은 그 길을 따라 도착 지점 (s, t)에 도달할 수 있다.

• (0, 0)에서 (s, t)로 가는 길이 존재한다는 것은 다음과 같은 의미이다.
• (0, 0), (a₁, b₁), (a₂, b₂), ..., (s, t)라는 좌표 배열은, 인접한 두 원소의 좌표 차이가 1이며, 초기에 ‘0’이 적혀 있다.
  
• Base : (0, 0)은 루프 시작때부터 이미 도달해 있다.
• Step : (0, 0) 부터 (a_k, b_k)까지 도달했다고 가정한다.
• 만약 (a_k, b_k)에 인접한 ‘0’인 위치가 (a_k+1, b_k+1) 뿐이면, 알고리즘이 (a_k+1, b_k+1)를 방문함이 자명하다.
• 만약 (a_k, b_k)에 인접한 ‘0’인 위치로 (a_k+1, b_k+1) 외에 (x, y)가 존재하고, (a_k+1, b_k+1)가 아닌(x, y) 를 방문했다면
  
• (x, y)를 방문하기 직전에 (a_k, b_k)의 좌표를 스택에 push했을 것이다.
• while문의 각 루프마다 push 또는 pop이 발생하므로
• 결국 (a_k, b_k)의 좌표가 pop되어 (a_k, b_k)로 돌아오게 될 것이다. 또다시 (a_k+1, b_k+1)가 아닌 (x’, y’) 를 방문해도 마찬가지 이유로 (a_k, b_k)로 돌아오게 되고, 결국 (a_k+1, b_k+1)을 방문하게 된다.
• push와 pop이 반복되어 (a_k, b_k)로 돌아오지 않고 무한 루프에 빠지는 일은 없다. 오직 ‘0’인 위치의 좌표만 push할 수 있고, push한 뒤에는 ‘*’로 바뀌므로, push가 일어날 수 있는 횟수에 한계가 있기 때문이다.
• (a_k, b_k)의 좌표가 pop되기 전에 while루프가 끝나 버릴 수는 있는데, 이는 (a_k, b_k)로 돌아오지 않고 (s, t) 에 도달한 경우이므로 문제가 없다.
  
• 따라서 다른 길을 통해 (s, t)에 도달한 경우를 제외하면, 알고리즘은 (0, 0), (a1, b1), (a2, b2), ..., (s, t)를 방문한다.

1. 시작 좌표 (0, 0)을 큐에 넣고, (0, 0)에 적힌 수를 1로 고친다.
2. 큐에서 좌표 하나를 delete하고, delete된 좌표로 방문한다.
3. 방문하고 있는 칸에 적힌 수가 k라 하자. 방문하고 있는 칸에 인접한 아직 방문하지 않은 칸들의 숫자를 k+1로 고치고, 큐에 넣는다.
•     
  
4. (M-1, N-1) 을 방문할 때까지 2, 3을 반복한다.

int Map[M][N];

int[][] Find() {
    // 시작 좌표를 큐에 삽입
    insert(0);
    insert(0);

    // 시작 위치까지의 최단 경로 길이 1을 적음
    Map[0][0] = 1;

    while (true) {
        int i = delete(), j = delete();  // 큐에서 좌표를 꺼냄
        if(i == M-1 && j == N-1) 
            break; // 미로 끝에 도달하면 루프 종료
        int k = Map[i][j];  // 좌표에 적힌 값을 읽음
        for 0이 적혀 있고 (i, j)에 인접한 모든 좌표 (pi, pj) 에 대해 {
            Map[pi][pj] = k + 1;
            insert(pi);
            insert(pj);
        }    
    }

    return Map;
}

• 큐에 저장된 좌표값이 [ x₁, y₁, x₂, y₂, ..., x_r, y_r ] 이고, x₁쪽에서 삭제 연산, y_r쪽에서 삽입 연산이 일어날 때, 
• 1 <= i < r 인 i에 대해, Map[x_i][y_i] <= Map[x_i+1][y_i+1] 가 성립하고
• Map[x_r][y_r] <= Map[x₁][y₁] + 1 이 성립한다.
  
• 예를 들어, 큐에 적힌 좌표가 가리키는 숫자를 순서대로 나열하면
• 2, 2, 2, 2, 3, 3, 3
• 12, 12, 12, 13, 13
• 5, 5, 5
• k, k, k, k, k+1, k+1
• k, k, k

• 와 같은 형태가 된다.

• Base : 큐에 0, 0 만이 저장되어 있고, 이는 1을 가리키므로 성립
• Step : n 번째 while 루프가 끝날 때 성립한다고 가정한다.
• n+1번째 while루프가 시작될 때, Map[x₁][y₁] = k라 하면, Map[x_r][y_r]은 k또는 k+1이다.
• x₁, y₁은 delete되고, Map에 적힌 숫자가 k+1인 좌표들이 insert 된다.
• 왼쪽에서 k가 지워지고, 오른쪽에서 k+1이 삽입되므로, n+1번째 루프가 끝날 때도 성립한다.

• Base
• 최단 경로가 1인 칸은 (0, 0)뿐이다. 알고리즘 시작 시 (0, 0)을 방문하고, 그 위치에 1을 올바르게 적으므로 명제1 이 증명된다.
• while 루프 안에서 k는 1 이상이고, k+1이 Map에 적히므로, 1은 오직 (0, 0)칸에만 적힌다. 따라서 명제 2가 증명된다.
• Step : 1~n에 대해 명제 1, 2가 참이라고 가정한다.
• 명제 1 증명 :
• 최단 경로 길이가 n+1인 임의의 칸 b에 대해, 최단 경로 길이가 n인 칸 a가 적어도 하나 인접해 있다. 가정에 따라 a에는 n이 적혀 있을 것이고, a를 방문할 때 for 루프에서 b에 n+1을 적게 된다.
• b가 a에 인접해 있음에도 for루프에서 n+1 을 적지 못했다면, b에 이미 0이 아닌 숫자가 적혀 있다는 것이다.
• 그 숫자가 n+1보다 클 수는 없다. 변수 k의 값이 감소하지 않기 때문이다.
• 이미 n+1이 적혀 있었다면, 문제가 없다.
• n+1보다 작다면, 명제 2가 n이하에서 참이라고 가정했으므로 실제 최단 경로 길이가 n 이하가 되고, 이는 b의 최단 경로 길이가 n+1이라는 가정에 모순이다.
• 따라서 b에는 n+1이 적히고, n+1에서도 명제 1이 참이다.
• 명제 2 증명 :
• 알고리즘이 어떤 a라는 칸에 방문하고 있을 때, for 루프에서 b라는 칸에 n+1을 적었다고 하자.
• b에 n+1을 적기 위해선 a와 b가 인접해야 하고, a에 적힌 숫자가 n이여야 한다.
• 즉, a까지의 최단 경로는 n이고, 시작지점에서 a를 거쳐 b로 가는 길이가 n+1인 경로가 존재하게 된다.
• 그런데 b로 가는 n+1보다 더 짧은 경로는 존재할 수 없다. n이하에서 명제가 참이라고 가정했으므로, 최단 경로 길이가 n 이하라면 그 값이 n+1 대신 적혀야 하기 때문이다.
• 따라서 b로 가는 최단 경로의 길이는 n+1이다.

• 미로 내 임의의 좌표 (s, t)에 대해, (0, 0), (a₁, b₁), (a₂, b₂), ..., (s, t)  이라는 길이가 L이하인 경로가 존재한다면, 좌표 (s, t) 는 큐에 삽입된다.

• Base : 알고리즘 시작 시 (0, 0)은 큐에 삽입된다.
• Step : (a_n, b_n)은 큐에 삽입되었다고 가정하자
• 그러면 (a_n, b_n)은 언젠가 큐에서 삭제되고, 그 좌표로 방문하게 된다.
• (a_n, b_n)을 방문한 시점에 (a_n+1, b_n+1)에 적힌 숫자가 0이라면, (a_n+1, b_n+1)은 큐에 들어가게 된다.
  
• 만약 (a_n+1, b_n+1)에 0이 아닌 숫자가 적혀 있었다면, 이미 (a_n+1, b_n+1)가 한번 큐에 들어갔다 나갔다는 뜻이다.
• 수학적 귀납법에 의해, 결국 (s, t)도 큐에 삽입된다.