Queue 자료구조

선형구조를 가지는 자료구조

특징

Stack과 달리 Queue는 뒤에서 삽입, 앞에서 삭제
선입선출구조(FIFO:First In First Out)
- Queue에 삽입한 순서대로 원소가 저장
- 가장 먼저 삽입된 원소는 가장 먼저 삭제 됨
Ex) 서비스를 받기위해 줄서있는 사람들의 모습

사용법

enqueue(item) : 큐 뒷쪽(rear)에 item을 삽입
dequeue() : 큐 앞쪽(front)에서 원소를 삭제하고 반환
isEmpty() : 공백상태인지 확인
isFull() : 꽉차있는지 확인

배열의 앞을 나타내는 front와 뒤를 나타내는 rear (index라고 보면 됨)

큐에 값이 삽입될때는 rear값이 증가하고

큐에 값이 삭제될때는 front를 증가하면서 각 자리를 가리킨다.

front와 rear가 같으면 큐가 비어있다고 생각하면 된다.

큐의 종류

선형 큐
- 배열 사용
  - 초기상태 : front = rear = -1
  - 공백상태 : front = rear
  - 포화상태 : rear = n - 1(n:배열의 크기, n - 1 배열의 마지막 인덱스)
  문제점 : 인큐와 디큐를 반복하면 front 와 rear가 하나씩 뒤로 이동하는데 이때 큐의 앞부분은 비어있지만 rear가 n - 1에 다다름으로 가득 차있는것으로 보는 문제가 있다. 이것을 원형큐로 해결가능하다.
원형 큐
- 배열 사용
  
  1차원 배열을 사용하되, 논리적으로 배열의 처음과 끝이 연결되어 원형 형태의 Queue를 이룬다고 가정하고 사용
- 초기 공백 상태 : front = rear = 0
- 공백상태 : front = rear
- 포화상태
  - 삽입할 rear의 다음 위치 = 현재 front 일때
    - (rear + 1) mode n = front
- Index의 순환 :
  - front와 rear가 배열의 마지막 인덱스인 n - 1을 가리킨 후, 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
  - 이를 위해 mod나머지 연산을 사용
- front 변수 :
  - 그래도 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둬야됨
- 삽입 위치 및 삭제 위치 :
  - 선형 큐 : | | 삽입 위치 | 삭제 위치 | | :——– | :——–: | ——–: | | 선형 큐 | rear = rear + 1 | front = front + 1 | | 원형 큐 | rear = (rear + 1) mod n | front = (front + 1) mod n |
디큐로 뺄때는 front 증가시켜 front가 가리키는 장소를 빼고, 인큐로 삽입할때는 rear 증가시켜 rear가 가리키는 장소에 삽입, 이때 rear는 mod(모듈러계산)을 통해 큐의 길이만큼 됬을때 다시 0 번째부터 가리키토록 indexing해야됨.

구현

class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return ((tail + 1) % size) == head;
    }
};

연결 큐
- 리스트 형식 사용
응용 -> 우선순위 큐(Priority Queue)

구현

1차원 배열을 이용하여 구현하면, 구현이 쉬운반면에 Stack의 크기를 변경하기가 어렵다. 그래서 —> Stack을 동적으로 할당하여 구현하는것이 더 좋은 방법이 되겠다. 동적 Linked List를 이용해서 구현해보자. 그러면 메모리를 효율적으로 사용가능하다.

#=> 소스코드 입력

Call Stack

프로그램에서 함수 호출과 return에 의한 복귀에 따른 수행 순서를 관리하기 위해 Stack자료구조를 사용

Memoization

재귀함수를 사용할때 무수한 중복호출을 방지하는 방법. (DP : Dynamic Programming, 동적계획법)의 핵심이 되는 기술

예를들어 피보나치 수열을 구하는 문제의 실행 Tree를 살펴보면 똑같은 함수호출이 반복된다는 것을 알 수 있다.

#=> Tree 사진

이전의 계산한 값을 메모리에 저장해서 매번 다시 연산하지 않도록 해서 실행속도를 높이는 방법

DP(Dynamic Programming, 동적계획법)

음….상향식의…문제풀이 방법??

Greedy Algorithm 설계 기법과 같이 최적화 문제를 해결하는 설계기법
일단 입력크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 더 큰 덩어리를 해결
최종적으로 원래 주어진 입력으로 문제를 해결

피보나치 수열 구하는것과 같이

부분문제로 분할 가능한지 확인하고 가능하면 부분 문제로 분할하고
분할 한 작은 부분으로 작은 부분부터 문제를 해결하고
그 결과를 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 그 위의 문제의 정답을 구함

구현방식

재귀(Recursive)방식
- 재귀적 구조는 내부에 시스템 호출 Stack을 사용하는 Overhead가 발생할 수 있음
반복문(Iteractive)방식
- Memoization을 재귀적 구조에 사용하는 것보다 반복문과 같이 DP를 구현하는 것이 성능면에서 보다 효율적이라고 한다.