5. Stack과 Queue

Stack과 Queue는 앞에서 다루었던 Array나 List와는 다른 확실한 개성을 갖고 있는 자료구조입니다. Array와 List가 자료를 공간에 하나씩 배정하고 특정 공간을 지목하여 자료를 꺼내 사용하는 단순한 방식을 지향한다면 Stack과 Queue는 자료가 들어온 순서와 그 순서에 따라 자료를 꺼내는 방식을 취하고 있습니다. Array와 List처럼 특정 주소를 지목하여 값을 꺼낼 수 없고, 중간에 입력된 자료를 꺼내기 위해서는 그 자료 앞이나 뒤에 있는 모든 자료를 비워내었을 때 그 자료를 꺼낼 수 있는 것입니다. 사용하기에 불편할 것 같은 이 자료구조는 왜 그리고 어떻게 사용하는 것인지 알아보겠습니다. 

먼저 Stack부터 설명하겠습니다. Stack은 쌓다라는 뜻을 갖고 있습니다. Stack은 단순하게 말해서 길쭉한 통에 물건을 차곡차곡 쌓는 것과 같습니다. 물건은 자료가 되는 것이고 긴 통은 Stack이 되는 것이죠. Stack은 물건을 쌓듯 push로 자료를 쌓고, 쌓여있는 물건을 꺼내듯 pop으로 자료를 꺼내게 됩니다. 그렇다면 쌓여있는 물건을 다시 꺼낼 때는 어떻게 꺼내야할까요. 물건이 공교롭게도 통과 딱맞는 모양과 크기라고 한다면 위에서부터 하나씩 꺼낼 수 밖에 없을 것입니다. 그렇게 들어간 순서와 역순으로 물건을 꺼내게 되면 제일 마지막에 들어간 물건은 제일 먼저 나오게되고 제일 먼저 들어간 물건은 제일 나중에 나오게 됩니다. 이러한 순서를 선입후출이라고 합니다. 혹은 후입선출이라고도 합니다. (LIFO: Last in, First out)

Queue는 줄, 혹은 줄서서 기다리다라는 의미를 갖고 있습니다. 우리가 어떠한 서비스를 받기 위하여 줄을 서고 있다면, 우리는 어떤 순서로 서비스를 받는게 공평하다고 생각할까요. 일반적인 경우라면 먼저 온사람이 먼저 서비스 받는 것이 옳다고 생각할 것입니다. Queue는 마치 줄을 서서 기다리는 것처럼 먼저 들어온 자료가 먼저 나가는 구조로 되어있습니다. Queue는 입력을 받게되면 add를 이용하여 뒤에서부터 줄을 세우고 poll을 통하여 앞에서부터 자료를 빼내게 되어 있습니다. 이러한 구조를 선입선출이라고 합니다. (FIFO: First in, First out)

그렇다면 Stack이나 Queue는 어떤 목적으로 사용할까요. Stack을 사용해서 후위연산을 구현할 수 있습니다. 숫자를 Stack에 저장하였다가 연산기호가 나올 때마다 Stack에서 pop하여 숫자 두 개를 연산한 뒤 다시 Stack에 집어 넣는 로직을 이용하여 연산을 처리할 수 있습니다. 그외에도 괄호의 좌우가 복잡하게 얽혀있을 때 서로 정확하게 fair를 이루고 있는지 확인하는 문제도 Stack으로 풀어낼 수 있습니다.

9012번: 괄호 - Baekjoon Online Judge

https://www.acmicpc.net/problem/9012

Queue는 그래프류의 문제에서 자주 사용됩니다. 일반적인 BFS(Breadth First Search:너비 우선 탐색)을 예시로 들면, 노드와 간선이 주어진다고 하였을 때, 최초 시작점에서 갈 수 있는 모든 Node들을 탐색한 뒤, 갈 수 있는 모든 노드 정보들을 다시 Queue에 집어넣고 Queue에서 다시 하나씩 탐색노드들을 뽑아 그 노드에서 다시 갈 수 있는 모든 노드들을 탐색하고 Queue에 집어넣는 반복적인 행동을 통해서 접근가능한 모든 노드들을 탐색할 수 있습니다. BFS에 대한 추가적인 설명은 다음 회차에 이어서 하도록 하겠습니다.

이제 실제 구현된 코드를 통해 설명하도록 하겠습니다.

Stack Code

import java.util.Stack;
 
public class StackTest {
    public static void main(String[] args) {
        // Stack 객체를 생성합니다.
        // 이때 <>안에는 Generic type을 넣어줍니다.
        // 예제에서는 Integer type을 사용하도록 하겠습니다.
        Stack<Integer> stack = new Stack<Integer>();
        
        // 1에서 5까지 순차적으로 Stack에 넣어보겠습니다.
        // 넣을 때는 push가 일반적이지만 add를 사용해도 무관합니다.
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        
        // Stack이 비어있는 상태인지는 isEmpty() 함수로 확인할 수 있습니다.
        // Stack이 비었다면 isEmpty는 true를 비어있지 않다면 false를 return할 것입니다.
        // 이에 따라 Stack이 비어있지 않다면 while문은 계속해서 돌 것입니다.
        while(!stack.isEmpty()) {
            // stack의 자료는 pop()으로 꺼낼 수 있습니다.
            // 만일 꺼내지 않고 제일 위의 값이 무엇인지 확인하려면 peek()을 이용합니다.
            int data = stack.peek();
            System.out.println("peek: " + data);
            data = stack.pop();
            System.out.println("pop: " + data);
            // peek은 값을 꺼내지 않기 때문에 출력되는 두 값은 같은 값이 나오게 됩니다.
            // 값은 넣은 순서의 역순인 5, 4, 3, 2, 1 순으로 출력됩니다.
        }
        // stack안의 모든 데이터는 빠져나온 상태이므로 isEmpty()의 return값은 true가 된다.
        System.out.println(stack.isEmpty());
    }
}

Queue Code

import java.util.ArrayDeque;
import java.util.Queue;
 
public class QueueTest {
    public static void main(String[] args) {
        // Queue는 Stack과 다르게 Interface로 되어있습니다.
        // 그래서 객체 생성할 때는 Queue로 선언하지만
        // 실제 객체 안에 담기는 것은 ArrayDeque나 LinkedList입니다.
        // 이 두 class는 사실 구조적으로 Queue를 구현할 수 있을 뿐만 아니라
        // Stack이나 Deque를 구성할 수도 있습니다.
        // 하지만 여기서는 Queue를 구현하는데 사용될 것입니다.
        Queue<Integer> queue = new ArrayDeque<Integer>();
        
        // Queue에 자료를 입력할 때는 add를 이용합니다.
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        
        // Queue의 isEmpty() 함수는 Stack과 마찬가지로 
        // Queue에 자료가 들어있는지를 판단해서 알려주게 되어있습니다.
        // 만일 자료가 하나라도 담겨있다면 false를 
        // 자료가 담겨있지 않다면 true를 return할 것입니다.
        // while이 시작했을 때, Queue에는 5개의 자료가 담겨 있으므로 
        // Queue가 비워질 때까지 돌게 될 것입니다.
        while(!queue.isEmpty()) {
            // Queue의 peek은 Stack과 마찬가지로 데이터를 자료에서 꺼내지 않은 상태에서 
            // 확인할 수 있다는 점에서 동일한 성격의 함수라고 할 수 있습니다.
            // 하지만 Stack이 맨 마지막에 입력된 자료를 반환하는 것과 다르게
            // Queue에서는 제일 처음 입력된 자료를 반환하게 됩니다.
            // peek은 어느 자료구조든 가장 먼저 꺼내지게 되는 값을 반환한다라고 외워두면 편할 것 같습니다.
            int data = queue.peek();
            System.out.println("peek: " + data);
            
            // Queue는 Stack과 다르게 poll로 자료를 뽑아주게 되어있습니다.
            // 그리고 Stack과 반대로 제일 처음 입력된 값부터 나오게 되어있습니다.
            // 그러므로 이 경우에는 1, 2, 3, 4, 5 순서로 출력될 것입니다.
            data = queue.poll();
            System.out.println("poll: " + data);
        }
    }
}