스택과 큐

1. 스택 ( stack )

• 데이터를 임시 저장할 때 사용하는 자료구조
• 후입선출 ( LIFO )
• push : 스택에 데이터를 넣는 작업
• pop : 스택에서 데이터를 꺼내는 작업
• top : 스택의 바깥쪽, 입구
• bottom : 스택의 안쪽`

2. 스택 구현하기

1 ) 스택의 구성 요소

• 스택 배열 ( stack ) : 데이터를 저장하는 스택 본체
• 스택 크기 ( capacity ) : 스택의 최대 크기
• 스택 포인터 ( ptr ) : 스택에 쌓여 있는 데이터 개수를 나타내는 정숫값
  • 스택이 비어 있으면 ptr = 0
  • 스택이 가득 차있으면 ptr = capacity

2 ) 스택의 예외처리

• EmptyError : pop 또는 peek 함수 호출 시 스택이 비어있으면 보내는 에러
• FullError : push 함수 호출 시 스택이 가득차면 보내는 에러

3 ) 스택의 구성 함수

• getLength : 스택에 쌓여 있는 데이터 개수 반환
• isEmpty : 스택이 비어 있는지 확인
• isFull : 스택이 차 있는지 확인
• push : 스택의 top에 데이터 추가
• pop : 스택의 top에서 데이터 제거
• peek : 스택의 top에 있는 데이터 확인
• clear : 스택의 모든 데이터 삭제
• find : 특정 데이터 검색
• count : 스택에 있는 특정 데이터 개수 확인
• contain : 스택에 특정 데이터 존재 여부 확인
• dump : 스택에 있는 모든 데이터 출력

4 ) 구현해보기

class Stack {
    private stack: unknown[];
    private capacity: number;
    private ptr: number;

    constructor(capacity = 5) {
        this.stack = new Array(capacity);
        this.capacity = capacity;
        this.ptr = 0;
    }

    private EmptyError = (): void => {
        throw new Error("스택이 비어 있습니다.");
    };

    private FullError = (): void => {
        throw new Error("스택이 가득찼습니다.");
    };

    public getLength = (): number => {
        return this.ptr;
    };

    public isEmpty = (): boolean => {
        return this.ptr === 0;
    };

    public isFull = (): boolean => {
        return this.ptr === this.capacity;
    };

    public push = (data: unknown): void => {
        if (this.isFull()) this.FullError();

        this.stack[this.ptr] = data;
        this.ptr++;
    };

    public pop = (): unknown => {
        if (this.isEmpty()) this.EmptyError();

        this.ptr--;
        return this.stack[this.ptr];
    };

    public peek = (): unknown => {
        if (this.isEmpty()) this.EmptyError();

        return this.stack[this.ptr];
    };

    public clear = (): void => {
        this.ptr = 0;
    };

    public find = (data: unknown): number => {
        for (let idx = this.ptr; idx >= 0; idx--) {
            if (this.stack[idx] === data) return idx;
        }
        return -1;
    };

    public count = (data: unknown): number => {
        let count = 0;
        this.stack.forEach((stackData) => {
            if (stackData === data) count++;
        });

        return count;
    };

    public contain = (data: unknown): boolean => {
        return this.count(data) > 0;
    };

    public dump = (): unknown[] => {
        return this.stack.slice(0, this.ptr);
    };
}

3. 큐 ( queue )

• 데이터를 임시 저장할 때 사용하는 자료구조
• 선입선출 ( FIFO )
• enqueue : 큐에 데이터를 추가하는 작업
• dequeue : 큐에서 데이터를 꺼내는 작업
• front : 데이터를 꺼내는 쪽
• rear : 데이터를 넣는 쪽
  

4. 배열로 큐 구현하기

• enqueue : 맨 끝 데이터 다음에 데이터 추가
  • 복잡도 O(1)
• dequeue : 맨 앞에 있는 데이터를 꺼낸 뒤 남은 모든 데이터 한 칸 씩 앞으로 이동
  • 복잡도 O(n)

5. 링 버퍼로 큐 구현하기

1 ) 링 버퍼 ( Ring Buffer )

• 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
• front : 맨 앞 원소의 인덱스
• rear : 맨 끝 원소의 바로 다음 인덱스
• 논리적인 데이터 순서일 뿐 매열의 물리적 원소의 순서는 아님

2 ) 큐의 구성 요소

• 큐 배열 ( queue ) : 데이터를 저장하는 큐 본체
• 큐 크기 ( capacity ) : 큐의 최대 크기
• 큐 데이터 개수 ( length ) : 큐에 쌓여 있는 데이터 개수를 나타내는 정숫값
  • 큐가 비어 있으면 length = 0
  • 큐가 가득 차있으면 length = capacity
• 큐의 앞단 ( front ) : 맨 앞 원소 커서
• 큐의 말단 ( rear ) : 맨 끝 원소 커서

3 ) 큐의 예외처리

• EmptyError : pop 또는 peek 함수 호출 시 큐가 비어있으면 보내는 에러
• FullError : push 함수 호출 시 큐가 가득차면 보내는 에러

4 ) 큐의 구성 함수

• getLength : 큐에 쌓여 있는 데이터 개수 반환
• isEmpty : 큐가 비어 있는지 확인
• isFull : 큐가 차 있는지 확인
• enqueue : 큐의 rear에 데이터 추가
• dequeue : 큐의 front에서 데이터 제거
• peek : 큐의 front에 있는 데이터 확인
• clear : 큐의 모든 데이터 삭제
• find : 특정 데이터 검색
• count : 큐에 있는 특정 데이터 개수 확인
• contain : 큐에 특정 데이터 존재 여부 확인
• dump : 큐에 있는 모든 데이터 출력

5 ) 구현해보기

class Queue {
    private queue: unknown[];
    private capacity: number;
    private length: number;
    private front: number;
    private rear: number;

    constructor(capacity = 5) {
        this.queue = new Array(capacity);
        this.capacity = capacity;
        this.length = 0;
        this.front = 0;
        this.rear = 0;
    }

    private EmptyError = (): void => {
        throw new Error("큐가 비어 있습니다.");
    };

    private FullError = (): void => {
        throw new Error("큐가 가득찼습니다.");
    };

    public getLength = (): number => {
        return this.length;
    };

    public isEmpty = (): boolean => {
        return this.length === 0;
    };

    public isFull = (): boolean => {
        return this.length === this.capacity;
    };

    public enqueue = (data: unknown): void => {
        if (this.isFull()) this.FullError();

        this.queue[this.rear] = data;
        this.rear++;
        this.length++;

        if (this.rear === this.capacity) this.rear = 0;
    };

    public dequeue = (): unknown => {
        if (this.isEmpty()) this.EmptyError();

        const data = this.queue[this.front];
        this.front++;
        this.length--;

        if (this.front === this.capacity) this.front = 0;

        return data;
    };

    public peek = (): unknown => {
        if (this.isEmpty()) this.EmptyError();

        return this.queue[this.front];
    };

    public clear = (): void => {
        this.length = 0;
        this.front = 0;
        this.rear = 0;
    };

    public find = (data: unknown): number => {
        for (let i = 0; i < this.length; i++) {
            const idx = (this.front + i) % this.capacity;
            if (this.queue[idx] === data) return idx;
        }
        return -1;
    };

    public count = (data: unknown): number => {
        let count = 0;
        for (let i = 0; i < this.length; i++) {
            const idx = (this.front + i) % this.capacity;
            if (this.queue[idx] === data) count++;
        }

        return count;
    };

    public contain = (data: unknown): boolean => {
        return this.count(data) > 0;
    };

    public dump = (): unknown[] => {
        if (this.front > this.rear)
            return [
                ...this.queue.slice(this.front),
                ...this.queue.slice(0, this.rear),
            ];
        return this.queue.slice(this.front, this.rear);
    };
}