[자료구조/Week 4] 교재 4장 프로그래밍 프로젝트 / HW04

문제

1. 덱은 스택의 기능과 큐의 기능을 모두 합니다. 그렇다면 왜 덱을 쓰지 않고 스택과 큐를 쓸까요?

스택은 먼저 들어온 데이터가 나중에 나오고, 나중에 들어온 데이터가 가장 먼저 나가는(LIFO) 방식이며, 큐는 먼저 들어온 데이터가 먼저 나가는(FIFO) 방식이다. 덱은 이런 스택과 큐의 기능을 모두 하기 때문에 양쪽에서 삽입, 삭제가 필요한 작업에 사용된다. 그러나, 이러한 작업이 필요한 경우가 많지 않고 스택과 큐에 비해 비교적 구현이 어렵기 때문에 덱보다 스택과 큐를 많이 사용한다.

 

2. (연습문제6)큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 될까요? 

큐는 먼저 들어온 데이터가 먼저 나가는(FIFO) 자료구조이다. 데이터를 삽입할 때는 맨 뒤에, 삭제할 때는 맨 앞에서 삭제한다. 데이터를 삽입할 때는 데이터의 개수와는 상관 없이 자료의 맨 뒤에 자료가 삽입되는 연산만 수행되므로 시간 복잡도는 O(1)이다. 자료의 삭제 또한 맨 앞의 자료가 삭제되는 동일한 연산이 수행되므로 시간 복잡도는 O(1)이다. 자료를 검색할 때는 맨 앞의 요소부터 맨 마지막 요소까지 차례대로 검색해야 하기 때문에 시간 복잡도는 O(n)이다.

 

프로그래밍 프로젝트 4장 - 미팅 프로그램 만들기

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

inline void error( char* str ) {
	cout << str << endl;
	exit(1);
};

#define MAX_QUEUE_SIZE	100

class CircularMeeting
{
protected:
	int	front;					
	int	rear;					
	char **data;	
public:
	CircularMeeting() {
		front = rear = 0;
		data = new char*[MAX_QUEUE_SIZE];
		for (int i = 0; i < MAX_QUEUE_SIZE; i++)
		data[i] = new char[20];
	}
	~CircularMeeting() {
		for (int i = 0; i < MAX_QUEUE_SIZE; i++)
		delete[]data[i];
		delete[]data;
	}

	bool isEmpty()	{ return front == rear; }
	bool isFull()	{ return (rear+1)%MAX_QUEUE_SIZE == front; }

	void enqueue( char *name ) {
		if(isFull() ) {
			cout << "Error: 큐가 포화상태입니다." << endl; exit(-1);}
		else {
			rear = (rear+1) % MAX_QUEUE_SIZE;
			strcpy(data[rear], name);
		}
	}

	char *dequeue( ) {	
		if(isEmpty() ){
			cout << "Error: 큐가 공백상태입니다." << endl; exit(-1);}
		else {
			front = (front+1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}

	char *peek( ){		
		if(isEmpty() ){
			cout << "Error: 큐가 공백상태입니다." << endl; exit(-1);}
		else 
			return data[(front+1) % MAX_QUEUE_SIZE];
	}

	void display( ) {	
		cout << "큐 내용: ";
		int maxi = (front < rear) ? rear : rear+MAX_QUEUE_SIZE;
		for( int i = front+1 ; i<=maxi ; i++ )
			cout << data[i % MAX_QUEUE_SIZE] << " ";
		cout << endl;
	}
};


int main()
{
	CircularMeeting female, male; // 여학생, 남학생
	char name[100];
	char gender;

	cout << "미팅 주선 프로그램입니다." << endl;

	while (1)
    {
		cout << "고객이름: ";
		cin >> name; // 학생 이름 입력

		cout << "성별을 입력하세요(f or m) ";
		cin >> gender; // 학생 이름 입력

		if (gender == 'm')
			male.enqueue(name);

		else if (gender == 'f')
			female.enqueue(name);

		if (!male.isEmpty() && !female.isEmpty()) //여자 남자 한쌍을 이룰 경우
		{
			char boy[20], girl[20];
			
			strcpy(boy, male.dequeue()); // 남학생 큐에 있는 문자열을 boy에 복사
			strcpy(girl, female.dequeue()); // 여학생 큐에 있는 문자열을 girl에 복사

			cout << "커플이 탄생했습니다! " << boy << "와 " << girl << endl << endl;
		}

		else
			cout << "아직 대상자가 없습니다. 기다려주십시요." << endl << endl;
	}

    return 0;

	}