자료구조 5. 큐

코드

• 모든 코드는 깃허브에서 확인하실 수 있습니다.

큐(queue)

• 대기줄과 비슷한 형태의 자료구조
  • 데이터를 추가할 때는 맨 뒤에만 추가 가능(enqueue, push)
  • 데이터를 삭제할 때는 맨 앞에만 삭제 가능(dequeue, pop)
  • 이러한 구조를 FIFO(First In First Out)라고 부름
• queue의 기능
  • isFull: 큐가 포화상태인지 확인
  • isEmpty: 큐가 비어있는지 확인
  • enqueue: 큐의의 맨 뒤에 새로운 값을 추가
    • isFull로 포화상태가 아닌것을 확인 후 값 추가
  • dequeue: 큐의 맨 앞의 값을 제거하고 반환
    • isEmpty로 스택이 비어있지 않았다는 것을 확인 후 값 삭제
  • peek: 큐의 맨 앞의 값을 확인
    • isEmpty로 스택이 비어있지 않았다는 것을 확인 후 값 확인
• 대기열이나 버퍼에 사용

선형 큐(linear queue)

• 위 그림처럼 front와 rear를 이용해 앞과 뒤를 표시
  • 처음에는 front와 rear 모두 -1
  • enqueue를 한다면 rear가 1 증가
  • dequeue를 한다면 front가 1 증가
  • 대부분 front는 첫 원소의 이전 index를 나타냄
• 선형 큐의 단점
  • Dequeue를 하면 앞에 빈 공간이 생김
  • 뒤의 원소를 앞으로 이동시키는 방법이 있지만 오래 걸림
• c언어

  • 선형 큐 구조체 정의

    typedef struct
    {
    	int front;
    	int rear;
    	int elements[MAX_QUEUE_SIZE];
    } Queue;
    

    • 구조체 초기화 시 front와 rear를 -1로 초기화

  • IsFull

    int IsFull(const Queue* queue)
    {
    	return (queue->rear == MAX_QUEUE_SIZE - 1);
    }
    

  • IsEmpty

    int IsEmpty(const Queue* queue)
    {
    	return (queue->front == queue->rear);
    }
    

  • Enqueue

    void Enqueue(Queue* queue, int value)
    {
    	assert(!IsFull(queue));
        
    	queue->elements[++(queue->rear)] = value;
    }
    

  • Dequeue

    int Dequeue(Queue* queue)
    {
    	assert(!IsEmpty(queue));
        
    	return queue->elements[++(queue->front)];
    }
    

  • Peek

    int Peek(Queue* queue)
    {
    	assert(!IsEmpty(queue));
        
    	return queue->elements[queue->front + 1];
    }
    

원형 큐(circular queue)

• 선형 큐의 단점을 보완한 큐
• 포화상태와 공백상태를 구별하기 위해 항상 공간 하나를 비워둠
  • 처음에는 front와 rear 모두 0
  • 만약 rear가 front의 한칸 뒤에 있다면 포화상태
• c언어

  • 원형 큐 구조체 정의

    typedef struct
    {
    	int front;
    	int rear;
    	int elements[MAX_QUEUE_SIZE];
    } CircularQueue;
    

    • 구조체 초기화 시 front와 rear를 -1로 초기화

  • IsFull

    int IsFull(const CircularQueue* queue)
    {
    	return (queue->front == (queue->rear + 1) % MAX_QUEUE_SIZE);
    }
    

  • IsEmpty

    int IsEmpty(const CircularQueue* queue)
    {
    	return (queue->front == queue->rear);
    }
    

  • Enqueue

    void Enqueue(CircularQueue* queue, int value)
    {
    	assert(!IsFull(queue));
        
    	queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    	queue->elements[queue->rear] = value;
    }
    

  • Dequeue

    int Dequeue(CircularQueue* queue)
    {
    	assert(!IsEmpty(queue));
        
    	queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    	return queue->elements[queue->front];
    }
    

  • Peek

    int Peek(CircularQueue* queue)
    {
    	assert(!IsEmpty(queue));
        
    	return queue->elements[(queue->front + 1) % MAX_QUEUE_SIZE];
    }
    

덱(deque)

• double ended queue의 줄임말
• 앞과 뒤에서 모두 삽입과 삭제가 가능
• 원형 큐를 응용해 구현
• deque의 추가적인 기능
  • add_rear: 맨 뒤에 원소 추가
  • delete_rear: 맨 뒤의 원소 제거
  • add_front: 맨 앞에 원소 추가
  • delete_front: 맨 앞의 원소 제거
  • get_rear: 맨 뒤의 원소 확인
  • get_front: 맨 앞의 원소 확인
• c언어

  • 덱 구조체 정의

    typedef struct
    {
    	int front;
    	int rear;
    	int elements[MAX_QUEUE_SIZE];
    } Deque;
    

    • 구조체 초기화 시 front와 rear를 -1로 초기화

  • IsFull

    int IsFull(const Deque* queue)
    {
    	return (queue->front == (queue->rear + 1) % MAX_QUEUE_SIZE);
    }
    

  • IsEmpty

    int IsEmpty(const Deque* queue)
    {
    	return (queue->front == queue->rear);
    }
    

  • AddRear

    void AddRear(Deque* queue, int value)
    {
    	assert(!IsFull(queue));
        
    	queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    	queue->elements[queue->rear] = value;
    }
    

  • DeleteRear

    int DeleteRear(Deque* queue)
    {
    	assert(!IsEmpty(queue));
        
    	int ret = queue->elements[queue->rear];
        
    	queue->rear = (queue->rear - 1) % MAX_QUEUE_SIZE;
        
    	return ret;
    }
    

  • AddFront

    void AddFront(Deque* queue, int value)
    {
    	assert(!IsFull(queue));
        
    	queue->elements[queue->front] = value;
    	queue->front = (queue->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    }
    

  • DeleteFront

    int DeleteFront(Deque* queue)
    {
    	assert(!IsEmpty(queue));
        
    	queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    	return queue->elements[queue->front];
    }
    

  • GetRear

    int GetRear(Deque* queue)
    {
    	assert(!IsEmpty(queue));
        
    	return queue->elements[queue->rear];
    }
    

  • GetFront

    int GetFront(Deque* queue)
    {
    	assert(!IsEmpty(queue));
        
    	return queue->elements[(queue->front + 1) % MAX_QUEUE_SIZE];
    }