스택과 큐로 간결한 코드 생성

스택과 큐는 배열과 배열과 큰 차이가 없다. 다만 제약을 갖는 배열일 뿐이다. 좀 더 구체적으로 설명하면 임시 데이터를 처리 할 수 있는 간결한 도구다. 운영 체제 아키텍쳐부터 출력 집과 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 사용해 뛰어난 알고리즘을 만들 수 있다. 임시 데이터란 처리 후에는 전혀 의미 없는 정보이므로 다 쓴 후에는 버려도 된다.

스택

스태익이 데이터를 저장하는 방법은 배열과 같다. 즉, 단수히 데이터들의 리스트이다. 다만 한 가지 스택에는 다음과 같은 세 가지 제약이 있다.

1. 데이터는 스택 끝에만 삽입 할 수 있다.
2. 데이터는 스택 끝에서만 삭제 할 수 있다.
3. 스택의 마지막 원소만 읽을 수 있다.

접시 더미를 스택처럼 생각 할 수 있다. 맨 위 접시는 보이지만 그 아래 접시에는 무엇이 들어있는지 모른다. 스택도 비슷하다.
{2,6,9,1,4,8} 배열이 있다면 맨 뒤는 8 맨 앞은 2다. 즉 맨 뒤 배열만 읽을 수 있다.

이를 비어진 스택을 []에 값을 추가 5라는 값을 추가한다. [5] 이어서 3을 추가한다. [5,3] 이어서 0을 추가한다. [5,3,0] 이렇게 데이터를 추가하는 과정을 push라고 한다.
그렇다면 데이터를 어떻게 읽을까??
[5,3,0]에서 pop을 하게 되면 맨 뒤에 있는 0의 값이 배열에서 지워지면서 그 값을 반환한다. [5,3] 이를 차례대로 반복하면 3,5의 값이 차례대로 반환된다. 스택 연산은 마지막에 들어온 값이 가장 먼저 빠져나온다. 따라서 Last in, First Out, LIFO라고 한다.

추상 데이터 타입

class stack<T>{
    private ArrayList<T> arrayList;

    public stack(){
        this.arrayList = new ArrayList<T>();
    }
    public void push(T data){
        arrayList.add(data);
    }
    public T pop(){
        T removedData = arrayList.get(arrayList.size() - 1);
        arrayList.remove(arrayList.size() - 1);
        return removedData;
    }
    public T read(){
        return arrayList.get(arrayList.size() - 1);
    }
}

위 코드는 제네릭을 사용하여 단순하게 스택을 구현해 보았다. 스택을 초기화 하면 주어진 사이즈 만큼 빈 배열을 생성한다. 그 후 데이터를 push,pop,read 할 수 있다. 배열의 경우 바로 데이터르 읽을 수 있다. 하지만 스택 클래스를 만들었기 때문에 배열의 맨 마지막 부분의 정보만을 읽을 수 있다. 스택 데이터 구조는 배열과 그 종류가 다르다. 배열은 대부분의 프로그래밍 언어의 내장되어 있고, 컴퓨터 메모리와 직접 상호작용한다. 반면 스택은 사실 규칙 집합이며 특정 결과를 얻기 위해 배열과 상호작용하는 방식을 다룬다.
스택은 내부적으로 어떤 데이터 구조를 쓰든 개의치 않는다. LIFO 방식으로 동작하는 데이터들의 리스트면 된다. 배열을 쓰든 그 외 다른 내장 데이터 구조를 쓰든 실제로 중요하지 않다. 그래서 스택은 추상 데이터 타입에 속한다. 다른 내장 데이터 구조를 사용하는 이론적 규칙 집합으로 이뤄진 데이터 구조다.

스택 다뤄보기

프로그래머가 작성한 코드를 검사해서 각 줄이 문법적으로 올바른지 확인하는 프로그램이 있다.
이 프로그램은 (var x = 1의 경우 ) 빠졌으므로 오류라고 프로그래머에게 알려준다. 이 프로그램의 오류는 세 가지다.

1. 여는 괄호는 있는데 닫는 괄호는 없다. (var x = 1
2. 여는 괄호는 없는데 닫는 괄호만 있다. var x = 1)
3. 여는 괄호와 닫는 괄호가 쌍이 다르다. ([var x = 1)]

이러한 프로그램은 다음과 같이 동작한다.

1. 괄호가 아닌 문자는 무시하고 넘어간다.
2. 여는 괄호가 나오면 스택에 푸시한다.
3. 닫는 괄호가 나오면 스택에 원소를 팝해서 확인한다.
4. 줄 끝에 도달하면 스택이 비었는지 확인한다.

    public static Boolean linter(String input_str){
        //여는 가로를 해시 테이블에 추가
        Hashtable<Character, Boolean> openings = new Hashtable<>();
        openings.put('(',true);
        openings.put('{',true);
        openings.put('[',true);
        //닫는 가로를 해시 테이블에 추가
        Hashtable<Character, Boolean> closings = new Hashtable<>();
        closings.put(')',true);
        closings.put('}',true);
        closings.put(']',true);
        //여는 가로와 닫는 가로를 매치
        Hashtable<Character,Character> match = new Hashtable<>();
        match.put('(',')');
        match.put('{','}');
        match.put('[',']');
        // 스택 생성
        stack<Character> stack = new stack<>();
        //문자열을 끝까지 확인
        for(int i = 0; i < input_str.length(); i++){
            //여는 가로일 경우
            if(openings.get(input_str.charAt(i)) != null){
                stack.push(input_str.charAt(i)); // 스택에 추가
            }
            //닫는 가로일 경우
            else if (closings.get(input_str.charAt(i)) != null){
                //스택이 비었다면  false 반환
                if(stack.read() == null) {
                    return false;
                };
                //스택을 pop()
                char openTemp = stack.pop();
                //닫는 가로와 여는 가로가 매치되지 않으면 false 반환.
                if(match.get(openTemp) != (input_str.charAt(i))){
                    return false;
                };
            }
        }
        //스택이 데이터가 남으면 false 반환
        if (stack.read() != null){
            return false;
        }
        return true;
    }

위와 같은 코드를 만들 수 있다. 이 코드를 작성하면서 스택은 내부적으로 배열을 사용하는데 반드시 스택을 활용해야하는지 의문이 생길 수 있다.

제약을 갖는 데이터의 중요성

스택이 제약을 갖는 배열이라면, 배열도 스택이 하는 일을 할 수 있다는 뜻이다.
그렇다면 스택의 이점은 무엇일까???
1. 제약을 갖는 자료구조를 사용하면 잠재적 버그를 막을 수 있다. 위에 문법을 검사하는 코드에서 스택의 중간 인덱스를 실수로 제거 할 경우 이 프로그램의 알고리즘은 고장난 정상적으로 동작 할 수 없게 된다.
2. 스택 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델을 제공한다. 가령 스택은 LIFO 프로세스에 대한 전반적인 아이디어를 제공한다. 이렇게 되면 방금 본 알고리즘과 같은 종류의 문제를 쉽게 해결 할 수 있다.
3. 자료 구조의 속성을 이해 하고 작성한 코드는, 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 알고리즘에서 스택을 발견하는 순간, 그 알고리즘의 동작 방식을 이해 할 수 있다.

스택 요약

스택은 마지막에 들어온 데이터부터 먼저 처리해야 할 때 이상적이다. 가령 워드프로세스에서 되돌리기와 같은 기능들이 스택의 훌륭한 사례다.

큐

임시 데이터를 처리하기 위해 디자인된 데이터 구조다. 데이터를 처리하는 순서만 제외하면, 많은 면에서 스택과 비슷하다. 큐 또한 추상 데이터 타입이다.
큐는 먼저 들어온 값이 먼저 나간다. 즉 First In, First out, FIFO다.
큐의 시작은 front 앞 , 끝을 back 뒤라고 부른다.

큐는 다음과 같은 세 가지 제약을 갖는 배열이다.
1. 데이터는 큐의 끝에만 삽입 할 수 있다.
2. 데이터는 큐의 앞에서만 삭제 할 수 있다.
3. 큐의 앞에 있는 데이터만 읽을 수 있다.

큐는 다음과 같이 동작한다. 빈 큐[]이 있을 때 데이터를 삽입하면서 알아보자.
5를 삽입 -> [5], 9를 삽입 -> [5,9], 100을 삽입 -> [5,9,100]

이제 데이터를 삭제(디큐)해보자.
큐 맨 앞을 삭제 -> [9,100], 디큐 -> [100], 디큐 []

자바 코드 구현

class Queue2<T>{
    private ArrayList<T> arrayList;
    public Queue2(){
        this.arrayList =  new ArrayList<T>();
    }
    public void enqueue(T data){
        arrayList.add(data);
    }
    public T dequeue(){
        T removedData = arrayList.get(0);
        arrayList.remove(0);
        return removedData;
    }
    public T read(){
        if (arrayList.size() == 0) return null;
        return arrayList.get(0);
    }
}

자바에서 큐를 사용하려면 큐와 링크드 리스트를 임포트 한 후 사용해야 한다.

큐 다뤄보기

출력 잡부터 웹 애플리케이션 백그라운드 워커에 이르기까지 많은 애플리케이션에서 흔하게 큐를 사용한다. 네트워크 프린터가 여러 컴퓨터로 부터 요청 받은 순서대로 각 문서를 출력한다고 가정하고 인터페이스를 구현해보자.

class printManager{
    private Queue2<String> queue;
    public printManager(){
        queue = new Queue2<>();
    }
    public void queuePrintJop(String data){
        queue.enqueue(data);
    }
    public void run(){
        while (queue.read() != null){
            System.out.println(queue.dequeue());
        }
    }
}}

프린터가 컴퓨터에게 문서 출력을 요청 받으면 큐에 데이터를 저자장한다. 그 후 입력 받은 순으로 데이터를 출력한다.

        printManager printManager = new printManager();
        printManager.queuePrintJop("First");
        printManager.queuePrintJop("Second");
        printManager.queuePrintJop("Third");
        printManager.run();

큐는 요청받은 순서대로 데이터를 처리하므로 비동기식 데이터를 처리하는 완벽한 도구이다. 이 외에 이륙을 기다리는 비행기, 의사를 기다리는 환자 등등 정해진 순서대로 이벤트가 발생하는 실세계 시나리오를 모델링하는데 흔하게 쓰인다.

결론

스택과 큐는 실용적인 알고리즘을 간결하게 처리 할 수 있는 프로그래머의 도구다.