큐 구현
#include <iostream>
#include <string>
using namespace std;
template <class T>
class Queue {
int front, rear;
T *queue;
int max;
public:
Queue() {
front=-1, rear = -1;
}
void create_queue(int max) {
this->max = max;
queue = new T[max];
}
void enque(T element) {
if (!is_full())queue[++rear] = element;
else cout << "큐가 가득찬 상태입니다" << endl;
}
T dequeue() {
if (!is_empty())return queue[++front];
cout << "큐에는 어떤 원소도 들어있지 않습니다. " << endl;
return NULL;
}
bool is_full() {
if (rear == max - 1)return true;
return false;
}
bool is_empty() {
if (rear == front)return true;
return false;
}
void is_clear() {
if (!is_empty()) {
delete[]queue;
}
rear, front = -1;
}
};
int main() {
int num;
Queue<int> v;
v.create_queue(3);
for (int i = 1; i <= 5; i+=2)
{
v.enque(i);
}
for (int i = 0; i < 3; i++)
{
num = v.dequeue();
cout << num;
} //135출력
v.is_clear();
}
queue의 크기는 동적배열 할당으로 생성하고 어떤 자료형이 들어가는 지 알수없으므로 템플릿클래스로 구현하였다.
#include <iostream>
#include <string>
using namespace std;
template <class T>
class Queue {
int front, rear;
T *queue;
int max;
int count;
public:
Queue() {
front=-1, rear = -1;
count = 0;
}
void create_queue(int max) {
this->max = max;
queue = new T[max];
}
void enque(T element) {
if (!is_full()) {
rear = (rear + 1) % max;
queue[rear] = element;
count++;
}
else cout << "큐가 가득찬 상태입니다" << endl;
}
T dequeue() {
if (!is_empty()) {
front = (front + 1) % max;
count--;
return queue[front];
}
cout << "큐에는 어떤 원소도 들어있지 않습니다. " << endl;
return NULL;
}
bool is_full() {
if (count==max)return true;
return false;
}
bool is_empty() {
if (count==0)return true;
return false;
}
void quePrint() {
int start = front + 1;
for (int i = start; i < start + count; i++)
{
cout << queue[i%max];
}
cout << endl;
}
void queSearch(T element)
{
int eval=0;
int start = front + 1;
for (int i = start; i < start + count; i++)
{
if (queue[i%max] == element) {
cout << "데이터가 존재합니다" << endl; eval = 1;
}
}
if (eval == 0) cout << "검색한 데이터가 없음 " << endl;
}
};
int main() {
Queue<int> v;
v.create_queue(4);
v.enque(1); v.enque(3); v.enque(5); v.enque(7);
v.quePrint(); //1357
v.dequeue();
v.quePrint();//357
v.dequeue();
v.dequeue();
v.quePrint();//7
v.enque(9);
v.enque(11);
v.quePrint();//7911
v.queSearch(11);
}
삽입 삭제 오퍼레이션 : 시간복잡도는 O(1)
검색 출력 오퍼레이션 : 시간복잡도는 O(n)
'Algorithm > 자료구조' 카테고리의 다른 글
해시 테이블의 A부터 Z까지 (1) | 2024.02.09 |
---|---|
우선순위 큐 (0) | 2022.05.18 |
트리(이진 탐색 트리) 삽입연산,삭제연산 (1) | 2022.05.10 |
자료구조 <트리> (0) | 2022.05.07 |
자료구조 <스택, 응용:괄호검사, 후위표기수식계산> (0) | 2022.04.10 |