Java 자료구조 - 스택과 큐

스택

Last-In First-Out

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로,
데이터의 입력과 출력 순서가 후입선출이다.
스택에 데이터를 넣는 작업을 푸시,
스택으로부터 데이터를 꺼내오는 작업을 팝이라고 한다.

스택은 실생활에서 접시 그릇을 차곡차곡 쌓아둔 모습에 비유할 수 있다.

스택의 활용 예시

폰노이만 아키텍쳐 즉, 프로그램 내장식 컴퓨터를 설계할 때,
CPU 안에 스택을 두어 이용해서 폰노이만 병목에서
발생하는 트래픽을 효과적으로 줄이는 방법이 있다.

프로시저 호출을 위해 범용 레지스터를 사용하지 않고
스택을 활용하여 프로시저를 중첩호출 하는 방법도 스택의 활용 예이다.

스택을 활용한 함수의 중첩 호출과정을 살펴보자.

class Main {
    static void main(String[] args) {
        A();
        D();
    }

    static void A() {
        B();
        ...
    }

    static void B() {
        C();
        ...
    }

    static void C() {
        ...
    }

    static void D() {
        ...
    }
}

A() 호출
스택의 최상위에는 B()를 호출하는 명령어(A() call) 다음으로 실행할 명령어의 위치를 담는다.

B() 호출
A() 에서는 B()를 호출한다.
따라서 스택의 최상위에는 B()를 호출하는 명령어 다음으로 오는 명령어의 위치를 담는다.

B() return
B() 실행을 모두 마치고 복귀할 때에는 스택 최상위에 담겨있던 A()에서 B()를 호출한 부분 다음으로 오는 명령어를 실행한다.

A() return
A()의 호출이 끝났으므로, 스택 최상위에 담겨있는 A()를 호출하는 명령어 다음에 오는 명령어를 실행한다.

• 후위 표기법

연산자를 피연산자 뒤에 표기하는 방법 예) AB+
중위표기법의 수식을 후위표기법으로 변환하는 방법을 알아보자.
수식 A*B-C/D를 후위 표기법으로 변환하면,
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
((A*B)-(C/D)

2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

((AB)*(CD)/)-

3) 괄호를 제거한다.

AB*CD/-

우리가 일반적으로 사용하는 표기법은 중위 표기법(A*B-C/D)이지만,
컴퓨터 내부에서 수식을 처리하기에 가장 효율적인 방법은 후위 표기법이다.
후위 표기법을 사용하면 괄호나 연산자 우선순위를 따로 처리하지 않고
왼쪽에서 오른쪽으로 표기된 순서대로 처리할 수 있다.

우리가 컴퓨터에 중위 표기법 형태의 수식을 입력하면 컴퓨터 내부에서는
효율적인 처리를 위해 스택을 사용하여 입력된 수식을 후위 표기법으로 변환하게 된다.

컴퓨터 내부에서 후위 표기법의 수식을 연산할 때도 스택을 사용할 수 있다.
스택을 사용하여 수식을 계산하는 방법은,

1) 피연산자를 만나면 스택에 삽입한다.
2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고
3) 연산 결과를 다시 스택에 삽입한다.
4) 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

실행과정

// 피연산자를 만나면 스택에 삽입한다.
push A
push B

// 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고
pop A
pop B
mul A B 

// 연산 결과를 다시 스택에 삽입한다.
push (A*B)

// 피연산자를 만나면 스택에 삽입한다.
push C
push D

// 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고
pop C
pop D
div C D

// 연산 결과를 다시 스택에 삽입한다.
push (C/D)

// 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고
pop (A*B)
pop (C/D)
sub (A*B) (C/D)

// 연산 결과를 다시 스택에 삽입한다.
push ((A*B)-(C/D))

// 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.
pop ((A*B)-(C/D))

출처: https://ryumin13.tistory.com/entry/자료구조-스택의-응용 [진정한 프로그래머가 되길 꿈꾸며..]

큐

FIFO,First-In, First-Out
큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조이다.
가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입 선출 구조로 되어있다.

큐의 실생활에성의 활용 예로는 은행 창구나 마트 계산대에 길게 선 대기 손님들의
모습을 예로 들 수 있다.

큐에서 데이터를 넣는 작업을 인큐, 데이터를 꺼내는 작업을 디큐라고 보통 얘기한다.
또한, 데이터를 꺼내는 쪽을 보통 front라고 얘기하고, 데이터를 넣는 쪽을 rear라고 얘기한다.

큐의 활용 예시

너비 우선 탐색

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후
시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든
정점들에 대해서도 너비 우선 검색을 적용한다.

BFS 너비 우선 탐색 구현
1) 현재 노드로부터 연결된 노드들 중 방문하지 않은 노드들을 큐에 넣는다.
2) 큐에서 가장 나중에 들어간 노드를 큐에서 빼내고 해당 노드를 방문한다.
3) 위의 1),2) 과정을 반복한다.

큐를 이용하여 코드로 구현한다.
특정한 상황, 간선이 가중치가 없는 그래프일 경우에만 적용될 수 있다.
즉, 노드에서 다른 노드로 가는 비용이 모든 간선에서 동일하지 않을경우에는 사용할 수 없다.

위 그림에서 너비 우선 탐색 과정은 다음과 같다.

• 1을 큐에 넣는다.
• 1을 큐에서 빼낸 후, 1에 방문한다.
• 2, 3을 큐에 넣는다.
• 2를 큐에서 빼낸 후, 2를 방문한다.
• 4, 5를 큐에 넣는다.
• 3을 큐에서 빼낸 후, 3을 방문한다.
• 6,7을 큐에 넣는다.
• 4를 큐에서 뺀다.
• 5를 큐에서 뺀다.
• 6을 큐에서 뺀다.
• 7을 큐에서 뺀다.

결과적으로
1-2-3-4-5-6-7 순서로 노드를 방문한다.