자료구조 <큐,원형큐의 삽입 삭제 검색 출력 구현>

큐 구현

#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)

큐 오퍼레이션 다이어그램