[JS] 스택 / 큐

스택(Stack)과 큐(Queue)는 프로그래밍이라는 개념이 탄생할 때부터 고전적인 자료구조 중 하나이다.

이 두 자료구조는 자바스크립트에 내장되어있진 않지만 배열(Array)과 내장함수들을 이용해 스택과 큐를 흉내낼 수 있다.

또한 프로그래밍에 있어 중요한 자료구조이며 대부분의 알고리즘 문제를 풀 때 배열을 이용해 풀어도 통과하지만,

시간복잡도라던가 데이터의 양이 매우 큰 경우 통과할 수 없어 알고 있어야 한다.

 

스택 (Stack)

1. LIFO(Last in, Last out) 원칙으로 만들어진 자료구조이며 가장 나중에 들어온 데이터가 먼저 나간다. (후입선출)
2. 함수 실행 콘텍스트들이 쌓이는 콜스택과 브라우저 방문 기록이 쌓이는 히스토리 스택이 대표적이다.
3. 서로 관계가 있는 여러 작업을 연달아 수행하며 이전 작업 내용을 저장할 필요가 있을 때 사용한다.
4. 스택이 비어있을 때 stack.pop을 하는 것은 stack underflow 이며, 스택이 꽉 차 있을 때 stack.push를 시도하면 stack overflow가 발생한다.
5. 박스 쌓기를 하는 것처럼 스택을 쌓는다고 할 때, 데이터를 쌓아 올리는 과정이 push이고 스택에서 데이터를 제거하는(꺼내는) 작업이 pop이다.
6. push하고 pop하는 맨 윗 부분을 꼭대기(top)이라 하고, 아랫부분을 바닥(bottom)이라 지칭한다.
7. 스택의 크기(capacity)란 스택에 쌓을 수 있는 데이터의 최대 개수를 의미한다.
8. 스택의 포인터(ptr)는 데이터 개수를 나타내는 정수값으로 스택이 비어있으면 0이고 가득차 있으면 capacity와 같은 값이다.

스택의 flow

[속성]

• top : 스택 맨 위의 아이템

[메서드]

• push : 스택 맨 위에 아이템을 삽입한다.
• pop : 스택 맨 위의 아이템을 제거하고 그 아이템을 반환한다.
• contains : 해당 아이템이 스택에 존재하는지 확인한다.
• size : 현재 스택에 있는 아이템 총 개수를 반환한다.

[스택 사용 사례]

• 재귀 알고리즘
• 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어준다.
• 재귀함수를 빠져나와 퇴각 검색(backtrack) 할 때 스택에 넣었던 임시 데이터를 빼야 한다.
• 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.
• 스택은 재귀 알고리즘을 반복적 형태를 통해 구현가능하게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) ex) 올바른 괄호 문자열(VPS, Vaild Parenthesis String) 판단하기
• 후위 표기법 계산

---

JavaScript 배열로 스택 구현

export default class Stack {
    constructor(){
        //item받을 배열 생성
        this.items = [];
    }
    push(item){
        this.items.push(item);
    }
    pop(){
        return this.items.pop();
    }
    lastElement(){
        if(this.items.length === 0){
            return null;
        }
        return this.items[this.items.length - 1];
        //items 배열의 마지막 item만 가져온다. pop()과 다르게 배열에서 아이템이 빠지는게 아니라 
        //유지된 채로 마지막 값만 받는다.
    }
    getSize(){
        return this.items.length;
    }
    isEmpty(){
        return this.getSize() === 0;
    }
}

---

큐 (Queue)

• First in, First out 원칙으로 만들어진 자료구조. 먼저 들어온 데이터가 먼저 나간다.
• 예시로 은행 창구나, 마트에서 계산을 기다리는 대기열 방식의 입출력 방식이다.
• 자바스크립트 엔진에서 비동기 함수 실행시 콜백들이 대기열로 들어오는 Task queue가 대표적 예시이다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등 작업을 할 수 있다.
• 데이터를 꺼내는 쪽 맨 앞을 front 라고 하며 넣는 쪽의 맨 끝을 rear 라고 지칭한다.
• 큐 자료구조는 모든게 뚫려있는 터널과 같은 자료구조라고 상상하면 된다.
• 큐는 순서대로 처리해야하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

[속성]

• first : 큐 맨 앞의 아이템

[메서드]

• dequeue : 큐 맨 앞의 아이템을 제거하고 아이템을 반환한다.
• enqueue : 큐에 아이템을 추가한다.
• contains : 해당 아이템이 큐에 존재하는지 확인한다.
• size : 현재 큐에 있는 아이템 총 개수를 반환한다.

[사용 사례]

• 데이터가 입력된 시간 순서대로 처리할 필요가 있을 때 이용한다.
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
• 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

---

JavaScript 배열로 큐 구현

dequeue 에서 shift()를 이용해 간단히 구현할 수 있다. 하지만 shift() 특성상 배열 맨 앞 요소(0번째 요소)를 삭제하면 배열의 길이(length)만큼 기존 요소들을 앞으로 당겨야해서 시간복잡도가 O(n)이 된다.

정석대로의 큐라면 시간복잡도가 O(1)이 되어야 한다.

export default class Queue {
    constructor(){
        //item받을 배열 생성
        this.items = [];
    }
    enqueue(item){
        this.items.push(item);
    }
    dequeue(){
        return this.items.shift();
    }
    firstElement(){ //FIFO
        return this.items[0];
    }
    getSize(){
        return this.items.length;
    }
    isEmpty(){
        return this.getSize() === 0;
    }
}

 

 

[출처]

https://algoroot.tistory.com/54

[알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기 (+개념이해)

https://algoroot.tistory.com/55

[알고리즘, 자료구조] 자바스크립트로 큐(Queue)구현하기 (+개념이해)