[Data Structures] 챕터5. 큐(Queue)

원형 큐

---

FIFO(First in First Out)

원형 큐에서 두 개의 index를 활용하여 비어있을 경우, 1개 있을 경우, 2개 있을경우, ..., 꽉 차있을 경우를 표현해야 한다.

모든 경우를 각각 유일하게 표현할 수 있도록 index를 사용하는 방법은 무엇인가?

1. front는 시작 index보다 1 작은 값을 가진다.
2. rear는 가장 마지막에 추가된 index이다.
3. front == rear일 때 원형 큐는 비어있다.

위 규칙을 적용하고 capacity -1 개의 저장공간만 사용한다(front가 가리키는 곳은 항상 비어있다)

 

원형 큐의 구현 원리

1. front와 rear 모두 0 index에서 시작한다.
2. 값을 추가하면 rear를 증가시켜 해당 index에 값을 할당한다

3.

1. 값을 뺄 때 front  값을 증가시키고 해당 index에 있는 값을 지운다.
2. rear 값이 capacity를 넘어가면 0에서 시작한다. rear = (rear + 1) % capacity

 

이 때 rear와 front가 같아지면 empty와 구분할 수 없으므로 capacity = capacity -1이 된다.

index 1은 비워야 한다

 

구현

int Size() const
{    
    // front_ == rear_ 일 때 Size = 0
    if (front_ <= rear_)
        return rear_ - front_;

    // front ~ (capacity-1)의 개수 +  0 ~ rear의 개수
    // (capacity - front -1)      +    (rear_ + 1)
    return capacity_ - front_ + rear_;

    //            비어있는 공간 개수
    // capacity  -  (front - rear)
}

 

ReSize

반복문 사용

내구현(if-else로 나누어 처리)

void Resize() // 2배씩 증가
{
    T* NewQueue= new T[capacity_ * 2];
    
    if (front_ > rear_)
    {
        for (int i = front_+1; i < capacity_; ++i)
            NewQueue[i - front_] = queue_[i]; // start idx is 1 not 0

        for (int i = 0;i <= rear_; ++i)
            NewQueue[capacity_ - front_ + i] = queue_[i]; // capacity_ - front_ = new start idx position
        // 예제 활용하기 front_=4, capacity=6
        // idx 4는 비어있고 idx 5는 값을 가지며 6-4 = 2이다
        // 이를 0으로 shift하면 idx 2(capacity - front)부터 채우면 된다.

        front_ = 0;
        rear_ = capacity_-1;
    }
    else
    {
        for (int i = 0; i < capacity_; ++i)
            NewQueue[i] = queue_[i];
    }
    
    delete[] queue_;
    queue_ = NewQueue;
    capacity_ *= 2;
}

 

추천구현(% 연산자를 활용)

void Resize()
{
    T* NewQueue= new T[capacity_ * 2];
    
    int count = 1; // start idx is 1
    for (int i = (front_ + 1) % capacity_; i != (rear_ + 1) % capacity_; i= (i+1) % capacity_)
    {
        NewQueue[count] = queue_[i]; 
        count++;
    }

    front_ = 0;
    rear_ = capacity_-1;
    delete[] queue_;
    queue_ = NewQueue;
    capacity_ *= 2;
}

 

memcpy 사용

내구현

void Resize() // 2배씩 증가
{
    T* NewQueue= new T[capacity_ * 2];
    
    if (front_ > rear_)
    {
        // 비어있는 front_ index부터 마지막 index까지 
        memcpy(NewQueue, &queue_[front_], (capacity_ - front_) * sizeof(T)); // T의 크기로 할당

        // 위에서 (capacity_ - front_)개수 만큼 채웠으므로 
        // (capacity_ - front_ -1) index까지 값이 할당됨. (capacity_ - front_)에서 시작.
        memcpy(&NewQueue[capacity_ - front_], queue_, (rear_+1)* sizeof(T)); // T의 크기로 할당

        front_ = 0;
        rear_ = capacity_-1; // 마지막 index를 가리킴
    }
    else
        memcpy(NewQueue, queue_, capacity_ * sizeof(T));

    front_ = 0;
    rear_ = capacity_-1;
    delete[] queue_;
    queue_ = NewQueue;
    capacity_ *= 2;
}

 

처음에 한 칸을 띄우지 않는 구현 방식(front가 마지막 index)

강의 21:48

 

Deque

void Dequeue() // 큐의 첫 요소 삭제, Pop()
{
    assert(!IsEmpty());

    front_ = (front_ + 1) % capacity_;
    //queue_[front_].~T(); // 자료형이 동적할당 메모리를 가질 경우
}

조세푸스 문제

---

 

덱(Deque)

---

• Deque(Double Ended Queue) 덱
• 양쪽을 모두 사용할 수 있다(queue의 기능을 확장) 
  • PushFront / PushBack, PopFront / PopBack
• dequeue와 deque는 다르다

위에서 구현한 Queue를 상속하면 PushBack == Enqueue, PopFront == Dequeue이므로 이미 구현되었다.

PushFront와 PopBack만 구현하면 된다.

구현

template<typename T>
class Deque : public Queue<T> // Deque가 사용하는 자료형 T와 동일한
{                             // 자료형을 사용하는 Queue를 상속
    typedef Queue<T> Base; // Queue<T> == Base (짧게 쓰기)
private:
    int& rear_ = Base::rear_;
    int& front_ = Base::front_;
    int& capacity_ =  Base::capacity_;
    T*& queue_ = Base::queue_;
};

참고 1) 위와 같이 부모 멤버 변수의 새 이름을 만들어 호출할 수 있다.

참고 2) 부모 클래스가 템플릿(template) 클래스일 경우 부모 클래스의 멤버를 아래와 같이 호출할 수 있다.

1. this->부모 멤버  (자신의 멤버와 부모의 멤버가 헷갈릴 수 있다)
2. Base::멤버
3. Queue<T>::멤버

 

PushFront

이 때 front_는 값을 가지지 않는 index이므로 해당 index에 값을 할당하고 이동시킨다.

void PushFront(const T& item)
{
    if (Base::IsFull())
        Base::Resize();

    Base::queue_[Base::front_] = item;
    Base::front_ = (Base::front_ + Base::capacity_ - 1) % Base::capacity_;
}

 

PopBack

void PopBack()
{
    assert(!Base::IsEmpty());

    Base::rear_ = (Base::rear_ + Base::capacity_ - 1) % Base::capacity_;
}

 

수식 계산

---

infix   : 숫자 사이에 연산자를 적는다(사람이 이해하기 편함)

A/B-C+D*E-A*C

 8 / 2 - 3 + 4 * 5 - 1 * 2 = 19

postfix : 계산 순서에 따라 숫자와 연산자를 나열한다(컴퓨터가 계산하기 편함)

AB/C-DE*+AC*-

8 2 / 3 - 4 5 * + 1 2 * - // 연산자를 만날때까지 진행
= 4 3 - 4 5 * + 1 2 * -
= 1 4 5 * + 1 2 * -
= 1 20 + 1 2 * -
= 21 1 2 * -
= 21 2 -
= 19

 

구현목표

1. infix를 posfix로 변환 (InfixToPostfix)
2. posfix를 계산 (EvalPostfix)

Queue는 문자열 데이터를 저장하는 용도로 쓴다. 알고리즘(로직)은 Stack을 활용한다.

Stack을 사용하는 이유 : 우선순위가 높은 연산자를 먼저 계산하기 위함

stack에 담겨있는 연산자와 새로운 연산자를 비교하여 우선순위가 높은 연산자를 먼저 계산한다

 

구현

// Function to return precedence of operators
// * is higher than - and +
int Prec(char c)
{
    if (c == '/' || c == '*')
        return 2;
    else if (c == '+' || c == '-')
        return 1;
    else
        return -1; // '('는 우선순위가 아주 낮은 것으로 처리, ')' 닫는 괄호를 만날때까지 남겨두기 위함
}

 

void InfixToPostfix(Queue<char>& q, Queue<char>& output)
{
    Stack<char> s; // 우선순위가 낮은 연산을 보류하기 위한 스택

    output.SetDebugFlag(false);

    while (!q.IsEmpty())
    {
        char c = q.Front();
        q.Dequeue();

        cout << c << endl;

        if (c >= '0' && c <= '9') // 숫자(피연산자)라면 output에 추가
            output.Enqueue(c);
        else if (c == '(') // 여는 괄호라면 스택에 추가
            s.Push(c);
        else if (c == ')') // 닫는 괄호를 만나면
        {
            // 여는 괄호 전까지를 스택에서 꺼내서 출력에 넣기
            // 여는 괄호 제거
            while (s.Top() != '(')
            {
                output.Enqueue(s.Top());
                s.Pop();
            }
            s.Pop();
        }
        else // 연산자를 만나면
        {
            // 스택에서 c보다 우선순위가 높거나 같은 것들을 꺼내서 추가
            while (!s.IsEmpty() && Prec(c) <= Prec(s.Top()))
            {
                output.Enqueue(s.Top());
                s.Pop();
            }

            // c는 스택에 추가
            s.Push(c);
        }

        cout << "Stack: ";
        s.Print();
        cout << "Output:";
        output.Print();
        cout << endl;
    }

    // 스택에 남아있는 것들을 모두 추가
    while (!s.IsEmpty())
    {
        output.Enqueue(s.Top());
        s.Pop();
    }
}

 

int EvalPostfix(Queue<char>& q)
{
    Stack<int> s;

    while (!q.IsEmpty())
    {
        char c = q.Front();
        q.Dequeue();

        cout << c << endl;

        if (c != '+' && c != '-' && c != '*' && c != '/')
        {
            // 입력이 연산자가 아니면 일단 저장
            // 문자를 숫자로 변환 c - '0' 예: int('9' - '0') -> 정수 9
            s.Push(c - '0');
        }
        else
        {
            cout << "Operator: " << c << endl;

            // 입력이 연산자이면 스택에서 꺼내서 연산에 사용
            int second = s.Top();
            s.Pop();
            int first = s.Top();
            s.Pop();

            if (c == '+')
                s.Push(first + second);
            else if (c == '-')
                s.Push(first - second);
            else if (c == '*')
                s.Push(first * second);
            else if (c == '/')
                s.Push(first / second);
            else
            {
                cout << "Wrong operator" << endl;
                exit(-1); // 강제 종료
            }
        }

        cout << "Stack: ";
        s.Print();
    }

    return s.Top();
}

 

더 해볼 것들

숫자가 두자리 이상인 경우

 character 자료형은 1 2 3 4를 12, 34 혹은 123,4로 구분할 수 없다. 따라서 두자리 숫자는 하나의 자료형으로 저장해야 하므로 Queue 자료형을 string 혹은 여러 숫자를 저장할 수 있는 자료형으로 변경해야 한다.

이 때 기존에 구현한 Queue는 메모리 해제 delete 와 소멸자를 호출하고 있다.

std::string은 자체적으로 메모리를 관리하므로 소멸자를 따로 호출할 필요가 없다. 

str is not a pointer to dynamically allocated memory, so you cannot delete it. In fact, you don't have to: it is a member of a class and maneges owned memory itself.

string 자료형에다 곧바로 memcpy을 사용할 수 없다.