[JavaScript] 배열을 통한 Queue, Stack 구현

개요

자료구조에 가장 기본적인 구조이자 많이 사용하는 Queue 구조와 Stack 구조가 있다. Java의 경우 Queue 인터페이스가 있고, Stack 인터페이스가 있으며 이를 구현한 구현체인 LinkedList나 ArrayList가 있기에 이를 그대로 사용하면 되지만 JavaScript에서는 어떻게 구현하는 것이 좋을까 하다가 의외로 내장 객체인 Array 객체에 이를 구현하는데 큰 도움이 되는 함수들이 있어서 기록하고자 한다.

 

Queue와 Stack

JavaScript에서 두 구조를 구현하는 방법에 대한 글이기 때문에 각 자료구조에 대해서는 간단히 설명하고 넘어가고자 한다.

Queue의 경우 FIFO( 선입 선출 )의 특징을 갖고 있는 자료구조로 파이프와 같은 형태의 데이터 저장소라고 보면 된다.

Stack의 경우 FILO( 선입 후출 )의 특징을 갖고 있는 자료구조로 물통과 같은 형태의 데이터 저장소라고 보면 된다.

즉, Queue는 먼저 들어간 데이터가 나중에 들어간 데이터보다 반드시 먼저 나와야 한다는 특징을 갖고 있으며, Stack은 먼저 들어간 데이터가 나중에 들어간 데이터보다 반드시 나중에 나와야 한다는 특징을 갖고 있다. 각 데이터가 들어간 순서에 따른 입출력 순서가 정해진 자료구조라고 보면 된다.

 

Queue의 구현

let queue = [];

// 데이터 입력
queue.push( 1 );
queue.push( 2 );
queue.push( 3 );

// 데이터 출력
queue.shift();    // 1
queue.shift();    // 2
queue.shift();    // 3

push() 함수는 해당 배열의 맨 마지막에 특정 값을 추가하는 함수이다. 

순서대로 1, 2, 3을 queue라는 배열에 넣었다. 그렇게 되면 Queue는 선입 선출 구조를 가져야 하기 때문에 맨 앞의 값부터 나와야 한다.

이 때, shift() 함수는 맨 앞의 요소를 제거하며 가져오는 함수이기에 이 작업을 수행해줄 수 있다.

 

Stack의 구현

let stack = [];

// 데이터 입력
stack.push( 1 );
stack.push( 2 );
stack.push( 3 );

// 데이터 출력
stack.pop();   // 3
stack.pop();   // 2
stack.pop();   // 1

마찬가지로 데이터를 입력하는 것은 뒤로 쌓아야 하기 때문에 push() 함수를 사용한다.

다만 Stack은 선입 후출이라는 구조를 가져야 하기 때문에 마지막에 입력한 값부터 가져오고 반환을 해야 한다. 

pop()이라는 함수는 배열의 마지막 요소를 가져온 후 요소를 배열에서 제거한다. 

Stack의 출력 원리와 완전히 동일하게 작동하기 때문에 이를 통해 Stack을 구현할 수 있다.

 

역방향 Stack과 Queue의 구현

이렇게 할 일은 잘 없겠지만 ( 사실 굳이... 싶다 ) 역방향으로 Queue와 Stack을 구현하는 방법도 있다.

Queue의 선입 선출, Stack의 선입 후출의 원리를 유지하되 역방향으로만 구현하는 것이다.

let reverseQueue = []

// 데이터 입력. 역방향이기 때문에 배열의 맨 앞으로 데이터를 추가한다.
reverseQueue.unshift( 1 );
reverseQueue.unshift( 2 );
reverseQueue.unshift( 3 );
// [ 3, 2, 1 ] 형태

// 데이터 출력. 역방향이기 때문에 배열의 맨 뒤로 데이터를 가져온다.
reverseQueue.pop();   // 1
reverseQueue.pop();   // 2
reverseQueue.pop();   // 3

역방향 Queue의 예제이다. 원래 Queue는 뒤로 들어와 앞으로 나가는 형태였다면 역방향은 앞으로 들어와 뒤로 나가는 형태이다.

즉, 출입구가 반대가 되었다고 생각하면 된다.

[ 1 ] >>> [ 1, 2, ] >>> [ 1, 2, 3 ]    이런 형태로 기존에는 높은 인덱스에 새로운 값이 추가되었다.

[ 1 ] >>> [ 2, 1 ] >>> [ 3, 2, 1 ]     역방향이 되면 이렇게 방향이 반대가 된다. 왼쪽에서 데이터가 들어왔으니 당연히 오른쪽부터 데이터가 빠져야 하므로 pop()을 사용해준 것이다.

 

let reverseStack = []

// 데이터 추가. 역방향이기 때문에 앞으로 데이터를 추가한다.
reverseStack.unshift( 1 );
reverseStack.unshift( 2 );
reverseStack.unshift( 3 );

// 데이터 제거. 역방향이기 때문에 앞에서 데이터를 출력한다.
reverseStack.shift();   // 3
reverseStack.shift();   // 2
reverseStack.shift();   // 1

역방향 Stack의 예제이다. 기존의 Stack이 뒤로 들어와 뒤로 나가는 형태였기에 역방향을 앞으로 들어와 앞으로 나가는 형태가 된다. 마찬가지로 출입구 위치가 뒤에서 앞으로 바뀌었다고 생각하면 된다.

[ 1 ] >>> [ 1, 2 ] >>> [ 1, 2, 3 ] >>> [ 1, 2 ] >>> [ 1 ]    이런 형태로 기존에 입출력이 이루어졌다.

[ 1 ] >>> [ 2, 1 ] >>> [ 3, 2, 1 ] >>> [ 2, 1 ] >>> [ 1 ]    역방향은 이렇게 위치를 바꾸어 앞에서 입출력이 이루어지게 만든 것이다.

 

결론

Java보다 확실히 JavaScript가 자료구조를 구현하기 쉽다. 또한 기본 내장 객체 및 함수들이 워낙 잘되어 있어서 그런 것 같기도 하다. 특히 역방향이 기본 함수로도 가능하다는 점에서 굉장히 인상적이었다. Java로는 구현하려면 꽤나 애먹을 것 같은데... JavaScript로 프론트엔드 로직을 구현할 때 도움이 많이 되지 않을까 싶다.