한빛출판네트워크

제공 : 한빛 네트워크
저자 : Michael McMillan
역자 : 권원상
원문 : Stacks in JavaScript

이전 글(자바스크립트에서의 자료구조)에서 자바스크립트 개발자가 스택, 리스트, 큐 등 컴퓨터 과학의 고전적인 자료 구조에 대한 구현 방법을 배우는 것이 왜 중요한 지에 대해 설명했다. 또한 해결하고자 하는 문제가 특정한 자료 구조를 암시하고 있어서 문제를 표현하는 어떤 알고리즘으로 귀결되는 경우가 얼마나 많은지에 대해서도 설명했다. 이번에는 바로 그런 경우에 대한 예를 들어 보려고 한다.

첫 번째 문제를 살펴보자. 주어진 텍스트를 검사하여 회문(Palindromes)이 있는 지를 찾는 문제이다. 회문은 앞뒤로 읽어도 동일한 단어나 어구를 가리킨다. 예로는 "bob"와 "racecar" 등이 있다.

스택의 핵심

이 문제를 풀기 위해 사용할 자료 구조는 스택이다. 스택은 가장 위 쪽(또는 앞쪽)에만 접근이 허용되는 리스트(list) 구조이다. 구내 식당에서 쟁반이 쌓여 있는 것을 생각해 보자. 쟁반을 하나 가져오려면, 제일 위쪽에 있는 쟁반을 집어야 한다. 다른 쟁반으로 바꾸려면 손에 있는 쟁반을 다른 곳에 두고 다시 맨 위쪽에 있는 쟁반을 하나 집어 올리게 된다. 바로 이런 식으로 스택에 저장된 데이터를 사용하게 된다.

일반적으로 스택을 구현할 때는 스택에 데이터를 저장할 때 사용하는 push() 함수와 스택의 가장 위쪽에 있는 데이터를 가져오면서 삭제하는 pop(), 스택의 가장 위쪽 요소를 보여주는 peek() 또는 top(), 스택에 있는 요소의 수를 확인하는 length() 나 size() 등의 함수를 같이 구현한다. 스택의 좋은 기능 중 하나는 바로 이렇게 제한된 인터페이스이다. 스택을 배워서 사용하기 쉬운 것은 이렇게 몇 개의 단순한 조작만을 허용하기 때문이다.

회문을 검사하는 데 스택이 완벽한 자료 구조인 이유는 바로 스택의 후입(last-in) 선출(first-out) 특성 때문이다. 스택에 단어의 모든 문자를 순서대로 넣은 다음, 한 문자씩 다시 꺼내어 단어를 만들면, 새로 생긴 단어는 원래 단어의 반대가 된다.예를 들면, 스택에 "hello"를 넣고(push), 빼면 (pop) "olleh" 문자열이 된다.

자바스크립트의 배열로 스택 만들기

자바스크립트의 좋은 기능 중 하나는 Array 객체에 이미 우리가 배열을 스택처럼 사용하는 데 필요한 모든 함수가 구현되어 있다는 점이다. Array를 사용하면 스택을 만들기 위해 따로 코딩을 해야 하는 번거로움을 줄일 수 있다. push() 함수를 사용하여 단어의 각 문자를 배열에 저장하고, pop() 함수로 배열에 저장된 문자를 가져오기만 하면 된다. 그리고 실수로 아무 것도 없는 스택에서 문자를 가져오려고 시도하지 않도록 length 속성으로 확인할 수 있다.

그럼 다음과 같이 코드를 작성할 수 있다.

var letters = []; // this is our stack
var rword = "";
putstr("Enter a word: ");
var word = readline();
for (var i = 0; i < word.length; i++) {
   rword += letters.pop(); // pop off the stack in reverse order
}
if (rword === word) {
   print(word + " is a palindrome.");
}
else {
   print(word + " is not a palindrome.");
}

다음은 위의 프로그램을 실행시켜 본 몇 가지 예이다.

Enter a word: bob
bob is a palindrome.
 
Enter a word: racecar
racecar is a palindrome.
 
Enter a word: hello
hello is not a palindrome.

위의 프로그램은 단어만을 처리하는 데 문장을 처리하도록 바꿔 볼 수도 있을 것이다.이를 테면, 공백을 제거하고 나면 ""a man a plan a canal panama"는 회문이 된다. 이번에는 문장에서 공백을 제거하고 난 다음에 스택에 넣는 형태로 앞에서 만든 프로그램을 확장해 보자.

다음과 같이 공백을 제거하는 기능을 넣을 수 있을 것이다.

var letters = [];
var rword = "";
putstr("Enter a sentence: ");
var sentence = readline();
var sword = "";
for (var i = 0; i < sentence.length; i++) {
   if (sentence[i] == " ") {
      ;
   }
   else {
      sword += sentence[i];
   }
}
for (var i = 0; i < sword.length; i++) {
   letters.push(sword[i]);
}
while (letters.length > 0) {
   rword += letters.pop();
}
if (rword === sword) {
   print(sentence + " is a palindrome.");
}
else {
   print(sentence + " is not a palindrome.");
}

다음은 확장된 프로그램을 실행하여 문장을 입력해 본 예이다.

Enter a sentence: a man a plan a canal panama
amanaplanacanalpanama is a palindrome.
 
Enter a sentence: now is the time for all good people
nowisthetimeforallgoodpeople is not a palindrome.

물론, 스택을 사용하지 않고도 회문을 처리하기 위한 프로그램을 만드는 방법이 여러 가지 있을 것이다. 그리고, 위의 방법이 가장 간단한 형태로 프로그램을 만드는 방법도 여러 가지 있을 것이다. 그러나, 스택의 동작에 대해서 이해하고 있는 프로그래머라면, 주어진 데이터의 역순으로 어떤 작업을 처리해야 한다라는 문제를 만나게 되면 스택으로 처리할 수 있겠구나 하는 감을 잡을 수 있을 것이다. 물론 스택만 이런 장점을 제공하는 유일한 자료 구조는 아니다. 다양한 형태의 자료 구조와 자료 구조의 활용 방법에 대한 잘 알고 있는 자바스크립트 프로그래머라면, 매일 매일 작업에서 만나게 되는 여러 문제에 대한 풍부한 해결책을 가지고 있는 것과 같다.