13 일차

환형 큐

∙ 배열을 이용한 큐의 구현

- 크기가 8인 배열에 3개의 데이터가 추가된 큐의 상태

 

 ∙ 배열을 이용하여 구현한 큐의 문제점

- 큐에 데이터의 삽입과 삭제가 지속적으로 발생할 경우, 배열의 앞부분에 무효화되는 공간이 늘어남

 

∙ 환형 큐(circular queue)

- 선입 선출(FIFO) 원칙에 따라 작업이 수행되고, 마지막 위치가 마치 원을 이루듯이 다시 첫 번째 위치에 연결되는 선형 데이터 구조

- 큐의 front와 rear 값이 시계 방향으로 한 칸씩 이동하는 형태

> 실제 구현에서는 배열 전체 크기를 이용하여 나머지(%) 연산을 수행

- 큐가 empty 또는 full 상태인지를 확인하기 위해 원소의 개수를 따로 저장해야 함

 

 

∙ 환형 큐에서 데이터 추가

rear = (rear + 1) % capacity; // 전체 배열 크기의 나머지 
arr[rear] = e;
count++;

 

 ∙환형 큐에서 데이터 삭제

front = (front + 1) % capacity;
count--;

 

∙ 환형 큐 클래스 소스코드

#include <iostream>

#define MAX_QUEUE 10

template <typename T>
class CircularQueue
{
public:
	CircularQueue(int sz = MAX_QUEUE)
	{
		arr = new T[sz];
		front_idx = 0;
		rear_idx = -1;
		count = 0;
		capacity = sz;
	}

	~CircularQueue()
	{
		delete [] arr;
	}

	void enqueue(const T& e)
	{
		if (full()) {
			std::cout << "Overflow error!" << std::endl;
			return;
		}

		rear_idx = (rear_idx + 1) % capacity;
		arr[rear_idx] = e;
		count++;
	}

	void dequeue()
	{
		if (empty()) {
			std::cout << "Underflow error!" << std::endl;
			return;
		}

		front_idx = (front_idx + 1) % capacity;
		count--;
	}

	const T& front() const { return arr[front_idx]; }

	bool empty() const { return count == 0; }
	int full() const { return count == capacity; }
	int size() const { return count; }

private:
	T* arr;
	int front_idx;
	int rear_idx;
	int count;
	int capacity;
};

using namespace std;

int main()
{
	CircularQueue<int> q(5);

	q.enqueue(10);
	q.enqueue(20);
	q.enqueue(30);
	q.enqueue(40);
	q.enqueue(50);  // full 상태
	q.dequeue();
	q.dequeue();    // 원소 2개 삭제
	q.enqueue(60);
	q.enqueue(70);  // full 상태
	q.enqueue(80);  // 오버플로우 에러!

	while (!q.empty()) {
		auto& e = q.front();
		cout << e << ", ";
		q.dequeue();
	}
	cout << endl;
}

 

양방향 큐

∙ 양방향 큐

- deque [dek] [덱] Double Ended QUEue

- 삽입과 삭제가 양쪽 끝에서 모두 가능한 자료 구조

 

- 양방향 큐의 주요 연산

> push_front(e) : 양방향 큐의 맨 앞에서 원소 e를 추가

> pop_front() : 양방향 큐의 맨 앞에 있는 원소를 삭제

 

> push_back(e) : 양방향 큐의 맨 뒤에 원소 e를 추가

> pop_back() : 양방향 큐의 맨 뒤에 있는 원소를 삭제

 

> front() : 양방향 큐의 맨 앞에 있는 원소를 참조

> back() : 양방향 큐의 맨 뒤에 있는 원소를 참조

 

> empty() : 양방향 큐가 비어 있으면 true를 반환

> size() : 양방향 큐의 원소 개수를

 

∙ 양방향 큐의 구현

- 배열을 이용한 양방향 큐의 구현

> 환형 큐와 비슷한 방식으로 양방향 큐의 맨 앞과 맨 마지막 위치를 갱신

 

- 연결 리스트를 이용한 양방향 큐의 구현

> 이중 연결 리스트를 이용하여 연결 리스트의 맨 앞과 맨 뒤에 자료를 각각 추가 & 삭제 가능

 

 

∙ std::deque

- 양방향 큐의 동작을 지원하는 순차 컨터이너

- <deque>에 정의되어 있음

- deque의 특징

> 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작

> 맨 앞과 맨 뒤에 자료를 추가 또는 삭제하는 연산이 O(1) 시간 복잡도로 동작

> 중간 위치에서 자료를 삽입 또는 삭제는 O(n) 시간 복잡도로 동작(n은 원소 개수)

> stack, queue 등의 STL 컨테이너 어댑터의 기본 컨테이너로 사용

 

∙ std::deque의 구현 방식

- C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며, 어떻게 구현해야 하는지 정의하지 않음

- 보통 std::deque은 단인 메모리 청크를 사용하지 않으며, 대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장함

 

∙ 소스 코드

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    // deque 생성
    deque<int> d = {10, 20, 30, 40};
    
    // 데이터 추가
    d.push_front(50); // 50, 10, 20, 30, 40
    d.push_back(60); // 50, 10, 20, 30, 40, 60
    
    // 데이터 출력 1
    for (int i = 0; i < d.size(); i++){
        cout << d[i] << ",";
    }
    cout << endl;
    
    // 데이터 출력 2
    for (auto i : d){
    	cout << i << ", ";
    }
    cout << endl;
}