문제
1. 데크는 스택과 큐 역할을 모두 수행합니다. 그렇다면 데크 대신 스택과 큐를 사용하는 이유는 무엇입니까?
스택은 선입선출(LIFO) 방식과 선입선출(FIFO) 방식이 있습니다. 데크는 스택과 큐의 역할을 하기 때문에 양쪽에서 삽입 및 삭제가 필요한 작업에 사용됩니다. 하지만 이러한 연산이 필요한 경우가 많지 않고 스택과 큐에 비해 상대적으로 구현이 어려우므로 데크보다 스택과 큐를 많이 사용한다.
2. (연습 6) 큐에서 항목을 삽입하고 삭제하는 데 시간이 얼마나 걸립니까?
큐는 선입선출(FIFO) 데이터 구조입니다. 데이터는 끝에 삽입되고 처음에 삭제됩니다. 데이터를 삽입할 때 데이터의 개수에 관계없이 데이터의 끝에 데이터를 삽입하는 연산만 수행하기 때문에 시간복잡도는 O(1)이다. 첫 번째 데이터를 지우는 데에도 동일한 작업이 수행되기 때문에 시간 복잡도는 O(1)입니다. 데이터를 검색할 때 시간 복잡도 에)오전.
프로그래밍 프로젝트 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;
}