[자료구조] PHP로 원형큐 구현

 

---

 

1. 생성

<?php

class CircularQueue 
{
    private int $front;
    private int $rear;
    private array $items;
    private int $maxSize;

    public function __construct(int $size) 
    {
        $this->maxSize = $size + 1; // 한 칸을 비워두는 방식으로 진행
        $this->items = array_fill(0, $this->maxSize, null);
        $this->front = 0;
        $this->rear = 0;
    }
}

 

2. 공백 상태 확인

front와 rear 포인터가 같은 위치를 가리키면 큐는 비어있는 것으로 판단한다. 생성자에서 front와 rear를 모두 0으로 초기화했고, 모든 요소가 dequeue 되어도 front가 rear를 따라잡아 같은 위치를 가리키게 된다.

public function isEmpty(): bool 
{
    return $this->front == $this->rear;
}

 

3. 포화 상태 확인

rear의 다음 위치가 front의 위치와 같다면, 이는 큐에 더 이상 데이터를 추가할 공간이 없음을 의미한다. maxSize를 실제 원하는 크기보다 1 크게 잡았기 때문에, rear의 다음이 front라는 것은 배열에서 front가 가리키는 한 칸을 제외하고 모든 공간이 사용되었다는 뜻이다.

public function isFull(): bool 
{
    return ($this->rear + 1) % $this->maxSize == $this->front;
}

 

4. enqueue

public function enqueue($item): bool 
{
    if ($this->isFull()) {
        return false; // 삽입 실패
    }
    $this->rear = ($this->rear + 1) % $this->maxSize; // 다음 위치로 이동
    $this->items[$this->rear] = $item; // 삽입
    return true; // 삽입 성공
}

 

5. dequeue

public function dequeue() 
{
    if ($this->isEmpty()) {
        return null; // 실패, 빈 큐에서 꺼낼 데이터 없음
    }
    $this->front = ($this->front + 1) % $this->maxSize; // front 다음 칸으로 이동
    $item = $this->items[$this->front]; // 반환할 요소 값 저장
    return $item; // 반환
}

 

6. peek

public function peek() 
{
    if ($this->isEmpty()) {
        return null;
    }
    // front 다음 위치의 아이템을 반환
    return $this->items[($this->front + 1) % $this->maxSize];
}

 

7. clear

front와 rear 포인터를 모두 0으로 재설정하여 큐를 초기 상태(비어있는 상태)로 만든다. 이렇게 하면 기존에 있던 요소들은 접근 불가능하게 되어 사실상 비워진 것과 같다.

public function clear(): void 
{
    $this->front = 0;
    $this->rear = 0;
}

 

8. getLength

단순히 'rear - front'로 계산하면, rear가 front 보다 작은 경우(rear가 배열의 끝을 지나 앞으로 되돌아온 경우) 음수 값이 나올 수 있기 때문에 아래와 같이 계산해 나머지 값으로 저장된 요소의 수를 반환한다.

public function getLength(): int 
{
    return ($this->rear - $this->front + $this->maxSize) % $this->maxSize;
}

 

 

9. display

public function display(): void 
{
    if ($this->isEmpty()) {
        return;
    }
    echo "Queue (front: {$this->front}, rear: {$this->rear}): ";
    $i = ($this->front + 1) % $this->maxSize; // 큐의 첫번째 요소 위치 설정
    while ($i != ($this->rear + 1) % $this->maxSize) { // rear가 가리키는 위치 다음칸에 도달할 때까지 순회
        echo $this->items[$i] . " "; 
        $i = ($i + 1) % $this->maxSize;
    }
    echo "\n";
}