스택과 큐 - 제약을 통한 문제 해결 전략

이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자료구조에 대해 알아보겠습니다.
스택과 큐는 임시데이터를 처리할 수 있는 도구입니다.
임시데이터란 사용 후에는 의미 없는 데이터로서 제거해도 무관합니다.
스택과 큐는 임시데이터를 처리하며 주로 처리 "순서"에 중점을 둡니다.

---

1. 스택 ( Stack )이란?

스택이 데이터를 저장하는 방법은 배열과 같습니다.
다만 몇 가지의 제약 사항을 가지고 있습니다.

• 데이터는 스택의 끝에만 삽입 가능 => push
• 데이터를 스택의 끝에서만 삭제 가능 => pop
• 마지막 원소( Top )만 읽기가 가능 => peek

 

 

스택의 연산은 보통 두 문장으로 LIFO ( Last-In, First-Out / 후입선출 )으로 표현합니다.

항상 삽입된 마지막 항목이 첫 번째로 출력됩니다.

 

---

 

2. 스택의 구현

class Stack {
    arr = [];
    size = 0;

    empty() {
        return this.size === 0;
    }

    push(number) {
        this.arr.push(number);
        this.size++;
    }

    pop() {
        let ret = -1
        if (!this.empty()) {
            ret = this.arr[this.size - 1];
            this.arr.splice(this.size - 1);
            this.size--;
        }
        return ret;
    }

    top() {
        if(this.empty()) return -1;
        return this.arr[this.size - 1];
    }
}

스택의 구현은 보통 추상 데이터 타입으로 정의합니다.

내부에서 쓰이는 자료구조의 종류에 개의치 않기 때문입니다.

스택은 사실 규칙의 집합이며 특정 결과를 얻기 위해 배열과 상호 작용을 하는 방식을 다룹니다.

그러면 여기서 의문이 들 수 있습니다.

'이거 다 배열로 할 수 있는 일 아니야?'

 

---

3. 제약을 갖는 데이터 구조의 중요성

 하지만 제약을 갖는 데이터 구조를 정의 함으로써 얻을 수 있는 이점이 있습니다.

• 제약을 갖는 데이터 구조는 의도치 않은 상황에서 발생하는 잠재적 버그를 막을 수 있음
• 문제를 해결하는데 새로운 사고 모델 ( Metal model )을 제공

 

---

4. 큐 ( Queue )란?

 큐 역시 임시 데이터 처리를 위해 디자인된 데이터 구조입니다.

데이터 처리의 순서만 제외하면 많은 면에서 스택과 닮아있습니다.

 극장의 매표소 줄을 큐로 생각해 볼 수 있습니다.

줄에 가장 먼저 섰던 사람이 가장 먼저 출에서 나와 입장하게 됩니다,

큐에 가장 처음 추가된 데이터가 가장 먼저 나가게 됩니다.

• 데이터는 큐의 끝 ( Rear )를 통해서만 삽입 가능 => Enqueue
• 데이터는 큐의 앞 ( Front )를 통해서만 삭제 가능 => Dequeue
• 큐의 앞 ( Front )의 값만 읽기 가능

 

큐의 연산은 보통 두 문장으로 FIFO ( First-In, First-Out / 선입선출 )으로 표현합니다.

 

---

 

5. 큐의 구현

class Queue {
    _arr = [];

    size() {
        return this._arr.length;
    }

    empty() {
        return this.size() === 0 ? 1 : 0;
    }

    push(number) {
        this._arr.push(number);
    }

    pop() {
        if (this.empty()) {
            return -1
        }
        return this._arr.shift();
    }

    front() {
        if (this.empty()) return -1;
        return this._arr[0];
    }
}

---

마치며

 알고리즘을 간결하게 처리할 수 있도록 돕는 스택과 큐에 대해서 알아보았습니다.
실무에서 굉장히 많이 활용되는 자료구조이기에 머리뿐만 아니라 손에 익히는 것이 좋겠습니다.
감사합니다.