리스트 / 스택 /큐

1. 리스트 / 스택 / 큐

1) 연속된 자료구조/연결된 자료구조

(1) 연속된 자료구조

• 모든 원소를 단일 메모리 청크에 저장
• 각각의 원소는 모두 같은 타입 사용 → 같은 크기의 메모리 사용 →sizeof(type) 으로 표시
• 시작주소(Base Address)에서 sizeof(type)을 사용하여 i번째 주소에 접근 가능
  • BA + i * sizeof(type)
• 배열의 유형
  • 정적배열 : 선언된 블록이 끝나면 소멸, 스택 영역에 할당되어 자동으로 해제
  • 동적배열 : 배열의 생성 시점과 소멸 시점을 자유롭게 결정, 힙 영역에 할당되어 직접 해제 전까지 유지

(2) 연결된 자료구조

• 노드를 사용하여 여러 개의 메모리 청크에 데이터를 저장 → 서로 다른 메모리 위치에 저장
• 연결리스트
  • 각각의 노드는 저장할 데이터와 다음 노드를 가르키는 포인터를 가짐
  • 마지막 노드는 NULL을 통해 리스트의 마지막을 표현
  • 각 원소에 접근하기 위해서는 next 포인터를 이용하여 접근
  • 배열과 달리 원소의 삽입과 삭제를 매우 빠르게 수행 가능
• 연결리스트에서 새 원소 삽입
  • 새로운 노드 생성
  • 각 노드의 next 포인터를 수정하여 삽입될 노드의 위치를 조정
• 연결리스트에서 원소 삭제
  • 연결리스트에 연결되어 있지 않도록 next 포인터 수정
  • 이후 해당 노드 메모리 할당 해제

(3) 두 자료구조 비교

연속된 자료구조(배열) 연결된 자료구조(연결리스트)

모든 데이터가 연속적으로 저장	데이터는 노드에 저장, 노드는 메모리 곳곳에 저장
임의 원소에 즉각적으로 접근	임의 원소 접근하는 것은 선형복잡도를 가짐
데이터가 연속적으로 저장, 캐시지역성 효과로 데이터 순회가 빠름	캐시 지역성 효과가 없으므로 모든 데이터 순회가 느린편
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리 사용	각 노드에서 포인터 저장을 위해 여분의 메모리 사용

 

💡 C스타일의 배열의 제약사항

———————————————————————————————————————

• 메모리 할당과 해제를 수동으로 처리 ( 해제하지 않은 경우 메모리 릭 발생가능 )
• 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못함 ( 세그먼테이션 결함, 메모리 손상 가능 )
• 배열 중첩 사용 시 문법이 복잡하여 코드 이해에 어려움
• 깊은 복사가 동작하지 않음

 

2) std::array

(1) array

• 메모리를 자동으로 할당하고 해제
• 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 탬플릿

std::array<int, 10> arr1; // 크기가 10인 int 타입 배열 선언
arr1[0] = 1; // 첫 번째 원소를 1로 설정
std::cout<<arr.at(0)<<std::endl; // at 연산자를 통해 사용가능 -> 예외처리에 효과적

• 객체를 다른 함수에 전달하는 방식은 기본 데이터 타입과 유사
• 값 또는 참조로 전달가능 / const를 함께 사용가능 → C처럼 포인터 연산이나 역참조 연산 X

void print(std::array<int,5> arr)
{
	for(auto ele : arr)
		std::cout<<ele<<",";
}
std::array<int,5> arr={1,2,3,4,5};
print(arr);

// 실행결과
// 1,2,3,4,5

• std::array는 begin()과 end() 멤버함수 제공

for(auto it = arr.begin(); it != arr.end(); it++)
{
	auto element = (*it);
	std::cout<<element<<' ';
}

• 반복자를 통해 접근 가능

(2) array 원소 접근 함수

함수 설명

front()	- 배열의 첫 번째 원소에 대한 참조를 반환
back()	- 배열의 마지막 원소에 대한 참조를 반환
data()	- 배열 객체 내부에서 실제 데이터 메모리 버퍼를 가르키는 포인터를 반환

• 반환된 포인터를 이용하여 다양한 포인터 연산을 수행
• 포인터를 함수 인자로 받는 예전 스타일의 함수 사용 시 유용 |

(3) 연습 문제 1 : 동적 크기 배열 구현하기

#include <iostream>
#include <algorithm>
#include <sstream>

template <typename T>
class dynamic_array
{
	T* data;
	size_t n;

public:
	dynamic_array(int n)
	{
		this->n = n;
		data = new T[n];
	}

	dynamic_array(const dynamic_array<T>& other)
	{
		n = other.n;
		data = new T[n];

		for (int i = 0; i < n; i++)
			data[i] = other[i];
	}

	T& operator[](int index)
	{
		return data[index];
	}

	const T& operator[](int index) const
	{
		return data[index];
	}

	T& at(int index)
	{
		if (index < n)
			return data[index];
		throw "Index out of range";
	}

	size_t size() const
	{
		return n;
	}

	~dynamic_array()
	{
		delete[] data; // 메모리 릭 방지
	}

	T* begin() { return data; }
	const T* begin() const { return data; }
	T* end() { return data + n; }
	const T* end() const { return data + n; }

	friend dynamic_array<T> operator+(const dynamic_array<T>& arr1, dynamic_array<T>& arr2)
	{
		dynamic_array<T> result(arr1.size() + arr2.size());
		std::copy(arr1.begin(), arr1.end(), result.begin());
		std::copy(arr2.begin(), arr2.end(), result.begin() + arr1.size());

		return result;
	}

	std::string to_string(const std::string& sep = ", ")
	{
		if (n == 0)
			return "";

		std::ostringstream os;
		os << data[0];

		for (int i = 1; i < n; i++)
			os << sep << data[i];

		return os.str();
	}
};

struct student
{
	std::string name;
	int standard;
};

std::ostream& operator<<(std::ostream& os, const student& s)
{
	return (os << "[" << s.name << ", " << s.standard << "]");
}

int main()
{
	int nStudents;
	std::cout << "1반 학생 수를 입력하세요: ";
	std::cin >> nStudents;

	dynamic_array<student> class1(nStudents);
	for (int i = 0; i < nStudents; i++)
	{
		std::string name;
		int standard;
		std::cout << i + 1 << "번째 학생 이름과 나이를 입력하세요: ";
		std::cin >> name >> standard;
		class1[i] = student{name, standard};
	}

	// 배열 크기보다 큰 인덱스의 학생에 접근
	try
	{
		// 아래 주석을 해제하면 프로그램이 비정상 종료합니다.
		// class1[nStudents] = student {"John", 8}; // 예상할 수 없는 동작

		class1.at(nStudents) = student{"John", 8}; // 예외 발생
	}
	catch (...)
	{
		std::cout << "예외 발생!" << std::endl;
	}

	// 깊은 복사
	auto class2 = class1;
	std::cout << "1반을 복사하여 2반 생성: " << class2.to_string() << std::endl;

	// 두 학급을 합쳐서 새로운 큰 학급을 생성
	auto class3 = class1 + class2;
	std::cout << "1반과 2반을 합쳐 3반 생성 : " << class3.to_string() << std::endl;

	return 0;
}

(4) 연습 문제 2 : 빠르고 범용적인 데이터 저장 컨테이너 만들기

#include <array>
#include <iostream>
#include <type_traits>

template <typename... Args>
auto build_array(Args &&... args) -> std::array<typename std::common_type<Args...>::type, sizeof...(args)>
{
    using commonType = typename std::common_type<Args...>::type;
    return {std::forward<commonType>(args)...};
}

int main()
{
    auto data = build_array(1, 0u, 'a', 3.2f, false);
    for (auto i : data)
        std::cout << i << " ";
    std::cout << std::endl;

    auto data2 = build_array(1, "Packt", 2.0);
}

3) std::vector

(1) std::array의 단점

• array의 크기는 컴파일 시간에 결정되는 상수이어야해서 프로그램 실행 중에는 변경 불가능
• 크기가 고정되어 원소를 추가하거나 삭제할 수 없음
• 항상 스택 메모리를 사용

(2) std::vector - 가변 크기 배열

• vector의 선언

std::vector<int> vec; // 크기가 0인 벡터 선언
std::vector<int> vec = {1,2,3,4,5}; // 지정한 초기값으로 이루어진 크기가 5인 벡터
std::vector<int> vec(10); // 크기가 10인 벡터
std::vector<int> vec(10,5); // 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언

• vector 원소 추가

vec.push_back(1); // 새 원소를 벡터의 맨 뒤에 추가
vec.insert(vec.begin(),0); // 반복자 위치에 해당 원소 삽입

• vector 원소 제거

vec.pop_back(); // 맨 마지막 원소 하나를 제거
vec.erase(vec.begin()); // 맨 처음 원소를 제거

• vector의 나머지 유용한 멤버함수

clear() // 모든 원소를 제거하여 완전히 비어있는 벡터로 만든다
reverse(capacity) // 벡터에서 사용할 용량을 지정, 
									// 현재 용량보다 매개변수가 클 경우 매개변수 크기만큼 재할당
									// 벡터의 크기를 변경하지 않음 (용량만 증가)
shrink_to_fit() // 여분의 메모리 공간을 해제하는 용도로 사용
								// 벡터의 용량이 현재 벡터 크기와 같게 설정

(3) std::vector 할당자

• 템플릿 매개변수에서 데이터 타입 다음에 할당자를 전달 가능
• 사용자 정의 할당자를 통해 배열의 단점을 해결할 수 있음

4) std::forward_list

• 연결 리스트에 대한 래퍼 클래스

(1) std::forward_list에서 원소 삽입과 삭제

• 원소 삽입

std::forward_list<int> fwd_list = {1,2,3};
fwd_list.push_front(0); // 맨 앞에 0 추가 : {0,1,2,3}
auto it = fwd_list.begin();
fwd_list.insert_after(it,5); // 맨 처음 원소 뒤에 5 추가 : {0,5,1,2,3}
fwd_list.insert_after(it,6); // 같은 위치에 6 추가 : {0,6,5,1,2,3}

• 원소 삭제

std::forward_list<int> fwd_list = {1,2,3,4,5};
fwd_list.pop_front(); // 맨 앞 원소를 삭제 : {2,3,4,5}
auto it = fwd_list.begin();
fwd_list.erase_after(it); // 맨 앞의 다음 원소 삭제 : {2,4,5}
fwd_list.erase_after(it,fwd_list.end()); // 맨 앞 원소 다음부터 맨 마지막 원소까지 삭제 : {2}

(2) std::forward_list의 기타 멤버 함수

• remove() / remove_if() : 해당하는 원소를 찾아 삭제하는 멤버 함수
  • remove는 등호 연산을 통해 삭제
  • remove_if는 좀 더 유연한 조건부 삭제 수행

(3) 연습 문제 3: 연결 리스트에서 remove_if() 함수를 이용한 조건부 원소 삭제

#include <string>
#include <iostream>
#include <forward_list>

struct citizen
{
	std::string name;
	int age;
};

std::ostream &operator<<(std::ostream &os, const citizen &c)
{
	return (os << "[" << c.name << ", " << c.age << "]");
}

int main()
{
	std::forward_list<citizen> citizens = {
		{"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
	};

	auto citizens_copy = citizens; // 깊은 복사

	std::cout << "전체 시민: ";
	for (const auto &c : citizens)
		std::cout << c << " ";
	std::cout << std::endl;

	citizens.remove_if([](const citizen &c) {
		// 나이가 19세보다 작으면 리스트에서 제거합니다.
		return (c.age < 19);
	});

	std::cout << "투표권이 있는 시민: ";
	for (const auto &c : citizens)
		std::cout << c << " ";
	std::cout << std::endl;

	citizens_copy.remove_if([](const citizen &c) {
		return (c.age != 18);
	});

	std::cout << "내년에 투표권이 생기는 시민: ";
	for (const auto &c : citizens_copy)
		std::cout << c << " ";
	std::cout << std::endl;
}

5) 반복자

• 반복자는 포인터와 비슷하지만 STL 컨테이너에 대한 공통적인 인터페이스를 제공
• advance() : 해당 반복자와 거리 값을 인자로 받고 반복자를 거리 값만큼 증가
• next() / prev(): 해당 반복자와 거리 값을 인자로 받고 지정한 거리만큼 떨어진 위치의 반복자 반환
• 해당 반복자가 지원할 경우에만 동작 → 순방향 반복자에서는 prev() 사용 불가

(1) 연습 문제 4: 다양한 반복자에서 이동하기

#include <iostream>
#include <forward_list>
#include <vector>

int main()
{
	std::vector<std::string> vec = {
		"Lewis Hamilton", "Lewis Hamilton", "Nico Roseberg",
		"Sebastian Vettel", "Lewis Hamilton", "Sebastian Vettel",
		"Sebastian Vettel", "Sebastian Vettel", "Fernando Alonso"
	};

	auto it = vec.begin(); // 상수 시간
	std::cout << "가장 최근 우승자: " << *it << std::endl;

	it += 8; // 상수 시간
	std::cout << "8년전 우승자: " << *it << std::endl;

	advance(it, -3); // 상수 시간
	std::cout << "그후 3년 뒤 우승자: " << *it << std::endl;

	std::forward_list<std::string> fwd(vec.begin(), vec.end());

	auto it1 = fwd.begin();
	std::cout << "가장 최근 우승자: " << *it1 << std::endl;

	advance(it1, 5); // 선형 시간
	std::cout << "5년전 우승자: " << *it1 << std::endl;

	// std::forward_list는 순방향으로만 이동할 수 있으므로
	// 아래 코드는 에러가 발생합니다. 
	// advance(it1, -2);

(2) 연습 문제 5: 기본적인 사용자 정의 컨테이너 만들기

#include <iostream>
#include <algorithm>

struct singly_ll_node
{
	int data;
	singly_ll_node* next;
};

class singly_ll
{
public:
	using node = singly_ll_node;
	using node_ptr = node*;

private:
	node_ptr head;

public:
	void push_front(int val)
	{
		auto new_node = new node{val, NULL};
		if (head != NULL)
			new_node->next = head;
		head = new_node;
	}

	void pop_front()
	{
		auto first = head;
		if (head)
		{
			head = head->next;
			delete first;
		}
	}

	struct singly_ll_iterator
	{
	private:
		node_ptr ptr;

	public:
		singly_ll_iterator(node_ptr p) : ptr(p) {}

		int& operator*() { return ptr->data; }

		node_ptr get() { return ptr; }

		singly_ll_iterator& operator++() // 선행 증가
		{
			ptr = ptr->next;
			return *this;
		}

		singly_ll_iterator operator++(int) // 후행 증가
		{
			singly_ll_iterator result = *this;
			++(*this);
			return result;
		}

		friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right)
		{
			return left.ptr == right.ptr;
		}

		friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right)
		{
			return left.ptr != right.ptr;
		}
	};

	singly_ll_iterator begin() { return singly_ll_iterator(head); }
	singly_ll_iterator end() { return singly_ll_iterator(NULL); }
	singly_ll_iterator begin() const { return singly_ll_iterator(head); }
	singly_ll_iterator end() const { return singly_ll_iterator(NULL); }

	singly_ll() = default;

	singly_ll(const singly_ll& other) : head(NULL)
	{
		if (other.head)
		{
			head = new node{0, NULL};
			auto cur = head;
			auto it = other.begin();
			while (true)
			{
				cur->data = *it;

				auto tmp = it;
				++tmp;
				if (tmp == other.end())
					break;

				cur->next = new node{0, NULL};
				cur = cur->next;
				it = tmp;
			}
		}
	}

	singly_ll(const std::initializer_list<int>& ilist) : head(NULL)
	{
		for (auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
			push_front(*it);
	}
};

int main()
{
	singly_ll sll = {1, 2, 3};
	sll.push_front(0);

	std::cout << "첫 번째 리스트: ";
	for (auto i : sll)
		std::cout << i << " "; // 출력: 0 1 2 3
	std::cout << std::endl;

	auto sll2 = sll;
	sll2.push_front(-1);
	std::cout << "첫 번째 리스트를 복사한 후, 맨 앞에 -1을 추가: ";
	for (auto i : sll2)
		std::cout << i << ' '; // 출력: -1 0 1 2 3
	std::cout << std::endl;

	std::cout << "깊은 복사 후 첫 번째 리스트: ";

	for (auto i : sll)
		std::cout << i << ' '; // 출력: 0 1 2 3
	std::cout << std::endl;
}

(3) 실습 문제 1: 음악 재생 목록 구현하기 ( 원형 연결 리스트 구현)

#include <iostream>

template <typename T>
struct cir_list_node
{
	T* data;
	cir_list_node* next;
	cir_list_node* prev;

	~cir_list_node()
	{
		delete data;
	}
};

template <typename T>
struct cir_list
{
public:
	using node = cir_list_node<T>;
	using node_ptr = node*;

private:
	node_ptr head;
	size_t n;

public:
	cir_list() : n(0)
	{
		head = new node {NULL, NULL, NULL}; // 모두 NULL로 구성된 기본 노드
		head->next = head;
		head->prev = head;
	}

	size_t size() const
	{
		return n;
	}

	void insert(const T& value)
	{
		node_ptr newNode = new node {new T(value), NULL, NULL};
		n++;
		auto dummy = head->prev;
		dummy->next = newNode;
		newNode->prev = dummy;
		if (head == dummy)
		{
			dummy->prev = newNode;
			newNode->next = dummy;
			head = newNode;
			return;
		}
		newNode->next = head;
		head->prev = newNode;
		head = newNode;
	}

	void erase(const T& value)
	{
		auto cur = head, dummy = head->prev;
		while (cur != dummy)
		{
			if (*(cur->data) == value)
			{
				cur->prev->next = cur->next;
				cur->next->prev = cur->prev;
				if (cur == head)
					head = head->next;
				delete cur;
				n--;
				return;
			}
			cur = cur->next;
		}
	}

	struct cir_list_it
	{
	private:
		node_ptr ptr;

	public:
		cir_list_it(node_ptr p) : ptr(p) {}

		T& operator*()
		{
			return *(ptr->data);
		}

		node_ptr get()
		{
			return ptr;
		}

		cir_list_it& operator++()
		{
			ptr = ptr->next;
			return *this;
		}

		cir_list_it operator++(int)
		{
			cir_list_it it = *this;
			++(*this);
			return it;
		}

		cir_list_it& operator--()
		{
			ptr = ptr->prev;
			return *this;
		}

		cir_list_it operator--(int)
		{
			cir_list_it it = *this;
			--(*this);
			return it;
		}

		friend bool operator==(const cir_list_it& it1, const cir_list_it& it2)
		{
			return it1.ptr == it2.ptr;
		}

		friend bool operator!=(const cir_list_it& it1, const cir_list_it& it2)
		{
			return it1.ptr != it2.ptr;
		}
	};

	cir_list_it begin()
	{
		return cir_list_it {head};
	}

	cir_list_it begin() const
	{
		return cir_list_it {head};
	}

	cir_list_it end()
	{
		return cir_list_it {head->prev};
	}

	cir_list_it end() const
	{
		return cir_list_it {head->prev};
	}

	cir_list(const cir_list<T>& other) : cir_list()
	{
		// 아래 코드는 원소를 역순으로 삽입하지만, 
		// 원형 리스트이기 때문에 문제가 없습니다.
		for (const auto& i : other)
			insert(i);
	}

	cir_list(const std::initializer_list<T>& il) : head(NULL), n(0)
	{
		// 아래 코드는 원소를 역순으로 삽입하지만, 
		// 원형 리스트이기 때문에 문제가 없습니다.
		for (const auto& i : il)
			insert(i);
	}

	~cir_list()
	{
		while (size())
		{
			erase(*(head->data));
		}

		delete head;
	}
};

struct playlist
{
	cir_list<int> list;

	void insert(int song)
	{
		list.insert(song);
	}

	void erase(int song)
	{
		list.erase(song);
	}

	void loopOnce()
	{
		for (auto& song : list)
			std::cout << song << " ";
		std::cout << std::endl;
	}
};

int main()
{
	playlist pl;
	pl.insert(1);
	pl.insert(2);
	std::cout << "재생 목록 : ";
	pl.loopOnce();

	playlist pl2 = pl;
	pl2.erase(2);
	pl2.insert(3);
	std::cout << "두 번째 재생 목록 : ";
	pl2.loopOnce();
}

6) std::list

• 이중 연결 리스트의 구조

(1) std::list의 멤버 함수

• std::forward_list와 유사하거나 같은 멤버함수
• insert() / emplace() → forward_list의 insert_after / emplace_after와 대응
• push_back() / emplace_back() / pop_back() → forward_list에서 사용할 수 없는 멤버함수

(2) 연습 문제 6 : std::list의 삽입 또는 삭제 함수 사용하기

#include <iostream>
#include <list>

int main()
{
	std::list<int> list1 = {1, 2, 3, 4, 5};
	list1.push_back(6);                   // {1, 2, 3, 4, 5, 6}
	list1.insert(next(list1.begin()), 0); // {1, 0, 2, 3, 4, 5, 6}
	list1.insert(list1.end(), 7);         // {1, 0, 2, 3, 4, 5, 6, 7}
	list1.pop_back();                     // {1, 0, 2, 3, 4, 5, 6}

	std::cout << "삽입 & 삭제 후 리스트: ";
	for (auto i : list1)
		std::cout << i << " ";
}

(3) 양방향 반복자

• std::list는 역방향 이동이 가능하지만 임의 접근 반복자처럼 한 번에 이동하지는 못함
• 따라서 선형 시간 복잡도를 가지고 있음

(4) 반복자 무효화

• vector의 경우 push_back()과 insert() 함수 사용 시 기존에 사용하던 반복자와 포인터 참조는 모두 무효화
• list의 경우 삽입, 삭제 동작에서 원소 이동이 필요없어 반복자 무효화되지 않는다
• 다만 특정 원소 삭제의 경우, 삭제되는 원소를 가리키던 반복자는 무효화

(5) 실습 문제 2 : 카드게임 시뮬레이션

#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>

struct card
{
	int number;

	enum suit
	{
		HEART,
		SPADE,
		CLUB,
		DIAMOND
	} suit;

	std::string to_string() const
	{
		std::ostringstream os;
		
		if (number > 0 && number <= 10)
			os << number;
		else
		{
			switch (number)
			{
			case 1:
				os << "Ace";
				break;
			case 11:
				os << "Jack";
				break;
			case 12:
				os << "Queen";
				break;
			case 13:
				os << "King";
				break;
			default:
				return "Invalid card";
			}
		}
		
		os << " of ";
		
		switch (suit)
		{
		case HEART:
			os << "hearts";
			break;
		case SPADE:
			os << "spades";
			break;
		case CLUB:
			os << "clubs";
			break;
		case DIAMOND:
			os << "diamonds";
			break;
		}
		
		return os.str();
	}
};

struct game
{
	std::array<card, 52> deck;
	std::vector<card> player1, player2, player3, player4;

	void buildDeck()
	{
		for (int i = 0; i < 13; i++)
			deck[i] = card {i + 1, card::HEART};
		for (int i = 0; i < 13; i++)
			deck[i + 13] = card {i + 1, card::SPADE};
		for (int i = 0; i < 13; i++)
			deck[i + 26] = card {i + 1, card::CLUB};
		for (int i = 0; i < 13; i++)
			deck[i + 39] = card {i + 1, card::DIAMOND};
	}

	void dealCards()
	{
		unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
		std::shuffle(deck.begin(), deck.end(), std::default_random_engine(seed));
		player1 = {deck.begin(), deck.begin() + 13};
		player2 = {deck.begin() + 13, deck.begin() + 26};
		player3 = {deck.begin() + 26, deck.begin() + 39};
		player4 = {deck.begin() + 39, deck.end()};
	}

	bool compareAndRemove(std::vector<card>& p1, std::vector<card>& p2)
	{
		if (p1.back().number == p2.back().number)
		{
			p1.pop_back();
			p2.pop_back();
			return true;
		}
		return false;
	}

	void playOneRound()
	{
		if (compareAndRemove(player1, player2))
		{
			compareAndRemove(player3, player4);
			return;
		}
		else if (compareAndRemove(player1, player3))
		{
			compareAndRemove(player2, player4);
			return;
		}
		else if (compareAndRemove(player1, player4))
		{
			compareAndRemove(player2, player3);
			return;
		}
		else if (compareAndRemove(player2, player3))
		{
			return;
		}
		else if (compareAndRemove(player2, player4))
		{
			return;
		}
		else if (compareAndRemove(player3, player4))
		{
			return;
		}

		unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
		std::shuffle(player1.begin(), player1.end(), std::default_random_engine(seed));
		std::shuffle(player2.begin(), player2.end(), std::default_random_engine(seed));
		std::shuffle(player3.begin(), player3.end(), std::default_random_engine(seed));
		std::shuffle(player4.begin(), player4.end(), std::default_random_engine(seed));
	}

	bool isGameComplete() const
	{
		return player1.empty() || player2.empty() || player3.empty() || player4.empty();
	}

	void playGame()
	{
		while (not isGameComplete())
		{
			playOneRound();
		}
	}

	int getWinner() const
	{
		if (player1.empty())
			return 1;
		if (player2.empty())
			return 2;
		if (player3.empty())
			return 3;
		if (player4.empty())
			return 4;
	}
};

int main()
{
	game newGame;
	newGame.buildDeck();
	newGame.dealCards();
	newGame.playGame();
	auto winner = newGame.getWinner();
	std::cout << winner << "번 플레이어가 이겼습니다!" << std::endl;
}

7) std::deque

• 양방향 큐 (double-ended queue) 구조

(1) deque의 구조

• deque의 경우, 양방향으로 매우 빠르게 확장 가능/ 모든 원소에 임의 접근을 제공
• 모든 메모리 청크 주소를 연속적인 메모리 구조에 저장할 경우 임의 접근 가능
• 따라서, 맨 앞에 원소 추가 시 메모리 청크의 앞의 메모리 여유 공간이 있을 경우 청크 할당 후 첫 번째 메모리 주소로 설정
• 이 때 새로 할당하는 메모리 공간은 새로 할당하지만 이전에 있던 메모리는 그대로 유지
• 벡터와 같이 임의 접근 반복자 제공 / 사용자 정의 반복자 사용 가능

8) 컨테이너 어뎁터

(1) std::stack

• std::deque를 기본 컨테이너로 사용
• LIFO의 특징 제공
• 모든 연산이 O(1)의 시간 복잡도
• 어뎁터 반복자는 따로 제공하지 않음

(2) std::queue

• FIFO의 특징 제공
• std::deque를 기본 컨테이너로 사용
• 모든 연산이 O(1)의 시간 복잡도
• 어뎁터 반복자는 따로 제공하지 않음

(3) std::priority_queue

• 우선순위 큐는 힙 구조를 제공
• 따라서 최소 / 최대 원소 접근이 제일 빠름
• 삽입/삭제는 O(log N) 시간 복잡도로 제공
• std::vector를 기본 컨테이너로 사용
• 어뎁터 반복자는 따로 제공하지 않음

(4) 실습 문제 3 : 사무실 공유 프린터의 인쇄 대기 목록 시뮬레이션

#include <iostream>
#include <queue>

class Job
{
	int id;
	std::string user;
	int pages;

	static int count;

public:
	Job(const std::string& u, int p) : user(u), pages(p), id(++count) {}

	friend std::ostream& operator<<(std::ostream& os, const Job& j)
	{
		os << "id: " << j.id << ", 사용자: " << j.user << ", 페이지수: " << j.pages << "장";
		return os;
	}
};

int Job::count = 0;

template <size_t N>
class Printer
{
	std::queue<Job> jobs;

public:
	bool addNewJob(const Job& job)
	{
		if (jobs.size() == N)
		{
			std::cout << "인쇄 대기열에 추가 실패: " << job << std::endl;
			return false;
		}

		std::cout << "인쇄 대기열에 추가: " << job << std::endl;
		jobs.push(job);
		return true;
	}

	void startPrinting()
	{
		while (not jobs.empty())
		{
			std::cout << "인쇄 중: " << jobs.front() << std::endl;
			jobs.pop();
		}
	}
};

int main()
{
	Printer<5> printer;

	Job j1("광희", 10);
	Job j2("정다", 4);
	Job j3("현수", 5);
	Job j4("유미", 7);
	Job j5("채원", 8);
	Job j6("시원", 10);

	printer.addNewJob(j1);
	printer.addNewJob(j2);
	printer.addNewJob(j3);
	printer.addNewJob(j4);
	printer.addNewJob(j5);
	printer.addNewJob(j6); // 인쇄 대기열이 가득 차있어서 추가할 수 없음
	printer.startPrinting();

	printer.addNewJob(j6); // 인쇄 대기열이 비었으므로 추가 가능
	printer.startPrinting();
}

 

 

출처 : 길벗 (코딩테스트를 위한 자료 구조와 알고리즘 with C++)