[자료구조] 배열을 이용한 스택과 큐 구현

들어가기 전

앞서 시간 까지는 연결 리스트에 대해서 정리하였고, 이번에는 스택과 큐에 대해서 알아보고 이에 대한 구현을 시도해보고자 한다. 마지막에는 내가 생각하기에 배열을 이용한 경우 생길 수 있는 장단점에 대해 언급하며 끝내고자 한다.

 

불가능이 현재 불가능인 것이지 앞으로 불가능이라고는 확신할 수 없다. 정진하자.

 

스택과 큐

스택

우선 스택의 경우에는 후입선출(Last In First Out) 의 구조를 지니는데, 마지막에 들어온 요소가 먼저 나가는 특징을 보인다. 흔히 자바스크립트에서 실행 컨텍스트가 쌓이는 구조가 스택 자료구조를 따르며 그래서 이름 또한 호출 스택 ( Call Stack)으로 불린다.

 

큐

큐를 한 단어로 정리하면 대기줄이다.

 

보통 영화관 입장이나 놀이공원 입장을 생각해보면 먼저 온 사람이 앞에서 표를 끊고, 늦게 온 사람은 다음 순서를 기다려며 대기하고 있다.

 

이게 큐의 전부이다. 따라서 큐의 경우에는 선입선출(First In First Out) 의 구조를 지니며, 먼저 들어온 요소가 먼저 나가는 특징을 보인다.

 

스택 구현하기

찾아보니 스택을 구현하는 방법은 연결 리스트를 사용한 방법이 있고, 이미 구현되어 있는 배열을 사용하는 방법이 있다고 한다. 우선 이번 시간에는 제일 간단하게 사용할 수 있는 배열을 이용해서 스택을 구현해볼 것이다.

 

사실 구현할게 크게 없다. 배열은 이미 만들어져 있고, 스택 구현에 필요한 메서드도 모두 구비가 되어 있기 때문에 스택의 이미지에 맞게 가져다 사용하기만 하면 된다. 

// 스택
class Stack {
    constructor(){
        this.items = [];
    }

    push(data) {
       return this.items.push(data);
    }

    pop(){
       if(!this.empty() return "터엉~"
        return this.items.pop();
    }

    top(){
        return this.items.at(-1);
    }

    isEmpty(){
        return this.items.length === 0; // 비었으면 true, 있으면 false
    }
}

 

여기서 push 를 요소를 제일 위에 올리고, pop 은 제일 위에 올려진 요소를 꺼내는 기능을 한다.

 

top 은 쌓여진 스택에서 제일 위에 있는 요소를 반환하고, isEmpty 는 스택이 비어 있는지 체크 하여 pop 메소드가 아무것도 없는 스택을 대상으로 연산하는 것을 막는 역할을 한다.

 

큐 구현하기

큐의 구현도 스택하고 크게 다를 게 없다.  스택이 지면에 막혀서 나갈 수 있는 구멍이 위에 하나 뿐이라면, 큐는 터널이다. 그래서 양방향으로 뚫린 형태가 된다. 사실 현재 구현하는 큐는 단방향으로만 들어가고 나가기만 가능하다. 큐도 유형이 다양해서 양쪽으로 들어왔다 나갔다 하는 형태도 존재한다.

 

암튼 큐는 양쪽 구멍이 뚫려 있지만, 들어온 방향으로는 나가지 못하고 무조건 입구를 지나 출구로만 나가야 한다.

class Queue {
   arr =[];
   enqueue(value){
    return this.arr.push(value);
  }
   dequeue() {
    if(this.isEmpty()) return ‘매진’ ; 
    return this.arr.shift(); // 큐에 가장 먼저들어온 요소가 꺼내진다
  }
   peek() {  // peek 는 엿보다는 의미가 있음
    return this.arr[0];
  }
   isEmpty() {
    return this.items.length === 0
 }
  get length(){
   return this.arr.length
  }
}

const queue = new Queue();

 

큐에서는 push 하는 것(입구로 들어오는 것)을 enqueue 라 부르고, shift 하는 것(출구로 나가는 것)을 dequeue 라고 부른다. 즉, queue.enqueue(5) 라고 출력하면 5라는 값이 큐 대기열에 등록된다. 반대로 queue.dequeue() 를 입력하면 5라는 값이 큐 대기열에서 빠져나온다.

 

peek 은 앞서 스택에서 살펴본 top() 과 유사한 목적을 수행하는데, 차이점이 있다면 peek() 은 큐 대기열의 첫 번째 요소가 무엇인지 찾아서 값을 반환한다는 점이 있다.

 

마지막으로 get length 는 대기열의 길이를 반환한다. get 이라는 게터를 사용하면 queue.length 와 같이 함수 내 로직을 실행할 수 있다. 즉, 명시적으로 호출하는 함수 length() 와는 다르게 호출할 함수를 바인딩 하여 일반적인 프로퍼티에 접근하는 것처럼 함수를 호출할 수 있다.

 

자세한 내용은 여기(https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Functions/get)를 참고 하길 바란다.

 

배열로 스택과 큐를 구현하면 이런 점이 편하다.

앞서 스택과 큐의 경우는 연결리스트로도 구현할 수 있는데, 그 이전에 배열을 사용하여 구현을 하게 되면, 메모리를 관리하기가 매우 간편하다는 장점이 있다. 배열의 경우 요소에 접근할 때 인덱스를 기반으로 접근하기 때문에 상수시간복잡도로 일정한 시간이 걸리기 때문에 효율적인 편이다.

 

무엇보다 구현하기가 매우 간편해진다는 점이 제일 편한 것 같다.

 

반면 이런 점은 문제일 수 있다.

이는 연결리스트와 비교되는 것인데, 배열의 경우에는 데이터(요소)를 메모리 공간 상에 연속적으로 확보하기 때문에, 배열의 구조를 크게 변경하는 작업이 많은 경우에는 오히려 시간복잡도가 최악이 될 수 있겠다는 생각이 들었다.

 

이 외에도 더 있을 것 같긴 한데, 스스로 분석해보기에는 이 정도가 있는 것 같다.

 

나가는 말

현재 까지 자료구조에 대한 부분을 연결 리스트 -> 스택과 큐 까지 이어 왔다. 직접 일일이 고민하며 구현하고 어떤 장점과 단점이 있을까 고민하며 나름  시간복잡도와 공간복잡도에 대한 계산도 해보며 조금씩 알고리즘에서 자료구조가 어떻게 쓰이고 있는 지 약간의 시야가 넓어진 느낌이 든다.

 

오늘은 배열을 사용하여 스택과 큐를 구현해보았지만, 다음에 시간이 날 때는 앞서 배웠던 연결리스트를 사용해서 구현해보는 로직을 작성하고, 연습해보고 나서 포스트에 기록을 남겨보려고 한다.