추상 데이터 타입

추상(Abstract)는 기능이 구체적으로 구현된 것이 아닌, 구현해야만 사용할 수 있는, 뼈대를 의미한다. 예를 들어, 추상 클래스를 상속 받게 되면, 추상 클래스의 메서드를 구현해야 사용할 수 있는 것과 같다.

똑같이, 추상 데이터 타입 또한, 데이터 타입의 I/O와 저장 방법, 검색 방법등을 직접 구현하여야 한다. 이 중 대표적인 자료구조가, 스택과 큐 이다.

스택(Stack)

스택의 원리

추상 데이터 타입중 하나인 스택은 LIFO(Last In First Out) 구조를 가진다.
가장 마지막에 들어간 자료가 제일 먼저 나가는 구조이다.

위 의 그림을 참조하면 이해에 도움이 될 것이다. 바닥이 막힌 컵에 자료를 쌓는다고 생각하면 된다. (그렇다고 해서 젠가처럼 중간에서 뺄순 없다 ...!)

스택에 자료를 입력하는 것을 Push라고 하고, 자료를 내보내는 것을 Pop이라고 한다. 이 두가지 기능과 LIFO를 구현해야 스택을 구현했다고 한다. 스택을 구현할 때 언어에 내장된 배열을 사용하던, 집합을 사용하던, 심지어, 해시 테이블을 사용하던 상관없다. 앞서 말한 Push, Pop, LIFO 만 구현하면 된다. 하지만, 어떻게 구현하느냐에 따라서 성능이 달라지는 것은 명확하다.

스택 구현(JSLint)

자바스크립트 린터(Linter)는 자바스크립트의 코드를 검사해주는 프로그램을 의미한다. 이 린터의 시작 부분을 만들면서 스택을 사용해보자.

예제에서는 린터의 한 가지 측면인 여는 괄호와 닫는 괄호에만 초점을 맞추겠다. 소괄호, 중괄호, 대괄호를 포함하는 괄호는 문법 오류를 일으키는 아주 흔한 원인이다.

이 문제를 풀려면 어떤 종류의 괄호 문법이 올바르지 않은지 분석해야 한다. 문제를 나눠 생각해 보면 문법 오류는 세 가지 상황에서 발생한다.

첫째, 다음처럼 여는 괄호는 있는데 닫는 괄호가 없는 경우

(var x = 2;

둘째, 여는 괄호가 앞에 나오지 않았는데 닫는 괄호가 나오는 경우

var x = 2;)

셋째, 닫는 괄호가 바로 앞에 나온 여는 괄호와 종류가 다를 경우

(var x = [1,2,3)];

위 세가지 경우를 검사해주는 린터를 스택을 활용하여 제작해보자. 먼저 빈 스택이 필요할 것이다. 그럴려면 스택을 구현해야한다. 다음은 Java로 작성한 스택의 구현체이다. 구현 자료구조로는 ArrayList를 사용했다. 제네릭스를 이용하여 타입 또한 자유롭게 변환할 수 있다.

package com;
import java.util.List;
import java.util.ArrayList;

public class MyStack<T> {

    private List<T> x = new ArrayList<T>();        
    private int idx = -1;

    public void push(T data) {
        x.add(data);
        idx ++;
    }

    public T pop() {
        
        if(idx == -1) {
            return null;
        }

        T temp = x.get(idx);
        x.remove(idx);
        idx --;

        return temp;
    }

    public List<T> getData() {
        return x;
    }
}

아래의 main 메서드는 테스트를 위한 코드이다. 추가로 위 급조(?)한 코드에는 문제점이 하나 존재한다. 바로 데이터가 없을 때 pop 메서드를 호출하면 당연히 오류가 날것이다. (스택의 마지막 인덱스를 기록하는 idx가 -1부터 시작하므로, 데이터를 하나 이상 삽입 하여야 idx가 0부터 시작하게 된다.)

이제 구현한 Stack을 이용하여 린터를 만들어 보자. 어떻게 동작할지 먼저 보자.

1단계: 첫 번째 문자는 여는 소괄호이다.

(var x = {y: [1,2,3]})
👆

2단계: 여는 괄호이므로, 스택에 Push 한다.
현재 스택의 상태.

(

3단계: 나머지 문자는 무시하고, 다음 여는 괄호가 나왔다.

(var x = {y: [1,2,3]})
		 👆

4단계: 스택에 푸쉬한다.
현재 스택의 상태.

(	{

5단계: 다음 여는 대괄호가 나왔다.

(var x = {y: [1,2,3]})
			 👆

6단계: 마찬가지로 스택에 푸쉬.
현재 스택의 상태.

(	{	[

7단계: 닫는 괄호가 처음 나왔다. 닫는 대괄호이다.

(var x = {y: [1,2,3]})
				   👆

8단계: 닫는 괄호가 나오면 스택에서 pop을 실행해보고, 닫는 대괄호와 같은 종류이면 통과한다. 같은 종류이므로 통과하고 진행한다.

현재 스택의 상태.

(	{

9단계: 다음으로 닫는 중괄호가 나온다.
10단계: 마찬가지로 pop을 실행하여 대조하여. 같은 종류이면 진행한다.

현재 스택의 상태

(

11단계: 닫는 소괄호가 나왔다.
12단계: 마찬가지로 스택의 원소를 pop하여 대조한다.

구현 코드

다음은 위에서 말한 알고리즘을 토대로 간단한 린터를 스택을 이용해 구현한 예제이다.
작성 언어는 Java이다.

import com.MyStack;

public class Linter {
    
    public static boolean lint(String code, MyStack<Character> stack) {
        //char 어레이를 만들어 입력받은 문자열을 문자 배열로 만든다.
        char[] charArray = code.toCharArray();
        
        // char 배열을 순회.
        for(int i = 0; i < charArray.length; i++) {
            // 괄호의 시작이 나오면 스택에 담는다
            if(charArray[i] == '(' || charArray[i] == '{' || charArray[i] == '[') {
                stack.push(charArray[i]);
            }

            // 닫는 괄호가 나오면 스택에서 데이터를 pop 한다. 만약, 빈 스택이면 에러를 반환한다.(앞에 여는 괄호가 나오지 않은것이므로.)
            if(charArray[i] == ')' || charArray[i] == '}' || charArray[i] == ']') {

                if(stack.pop() == null) {
                    System.out.println("에러 발생");
                    // 검사 결과 에러시 false 반환
                    return false;
                } else if((stack.pop() != charArray[i] && stack.pop() != ')') ||
                          (stack.pop() != charArray[i] && stack.pop() != '}') ||
                          (stack.pop() != charArray[i] && stack.pop() != ']')) {

                    System.out.println("괄호의 종류가 다릅니다.");
                    //검사 결과 에러시 false 반환
                    return false;
                }
            }
            
        }
        // 스택이 비어있지 않다면 false 반환
        if(!(stack.pop() == null)) {
            return false;
        }

        // 모든 검사가 성공적으로 끝나면 True 반환
        return true;
    }
    public static void main(String[] args) {

        MyStack<Character> myStack = new MyStack();

        boolean result = lint("(var x = {y: [1,2,3]})", myStack);

        System.out.println(result);

    }
}