2023-07-20 백준 2164번

클래스 문제를 따라풀다가 자료구조 중 큐를 활용해야 하는 문제를 만났다. 

C++ STL의 큐를 사용해도 되지만 직접 구현해 보기로 하였다. 

22년도 겨울 계절학기에 자료구조를 수강한 기억을 떠올려서 

이중 연결리스트를 활용하여 큐를 구현하였다.

/*
* 백준 2164 카드2 문제 알고리즘 분류에 큐가 있어서 큐를 사용한다.
* 위, 오래된 것, 삭제 연산 수행, tail, 앞
* 아래, 최신의 것, 삽입 연산 수행, head, 뒤
* 카드는 아래에서 넣고 위에서 뺀다 
* 큐는 뒤에서 넣고 앞에서 뺀다.
*/

#include<iostream>
using namespace std;

class node {
public:
	int data;
	node* prev;
	node* next;
	node(int n) {
		this->data = n;
		this->prev = NULL;
		this->next = NULL;
	}
};

class queue {
public:
	node* head;
	node* tail;
	int count;
	queue() {
		this->head = NULL;
		this->tail = NULL;
		/*
		head->next = tail;
		tail->next = tail;
		head->prev = head;
		tail->prev = head;
		*/
		this->count = 0;
	}
	void enqueue(int N) {
		node* newnode = new node(N);
		if (tail == NULL) {
			head = tail = newnode;
			head->next = newnode;
			newnode->prev = head;
			tail->prev = newnode;
			newnode->next = tail;
			count++;
		}
		else {
			/*
			tail->prev->next = newnode;
			tail->prev = newnode;
			newnode->prev = tail->prev;
			newnode->next = tail;
			*/
			tail->next = newnode;
			newnode->prev = tail;
			tail = newnode;
			count++;
		}
		
	}
	void dequeue() {
		if(count!=0){
			node* oldnode = head;
			oldnode->next->prev = NULL;
			head = oldnode->next;
			delete oldnode;
			count--;
		}
	}

	int front() {
		return head->data;
	}

	void print() {
		node* current = head;
		cout << current->data;
	}
};

int main() {
	queue myqueue;
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		myqueue.enqueue(i);
	}
	while (myqueue.count != 1) {
		myqueue.dequeue();
		if (myqueue.count != 1) {
			int temp = myqueue.front();
			myqueue.dequeue();
			myqueue.enqueue(temp);
		}
		else {
			break;
		}
	}
	myqueue.print();
}

따로 큐 안의 원소의 수를 관리하는 count를 두지 않고 head포인터가 NULL인지 확인하는 방식이 더 효율적이지만 

아직은 코드가 손에 익지않아서 이런식으로 구현하였다.

아래는 직접짠 코드를 이용한 결과이고 위는 STL을 이용한 결과이다.