큐(Queue) 구현

stack에 이어 queue도 구현해보았습니다.

queue는 stack과 반대로 선입선출의 원리를 사용하고 있는 자료구조입니다.

 

이전에 [stack]에서 달라진 점 위주로 쓰도록 하겠습니다.

 

0. 선언

	int s_size = 100;
	T* my_queue= (T*)malloc(sizeof(T)*s_size);
	int top = 0;
	int floor = 0;

s_size 변수는 배열의 capacity, my_queue는 

top과 floor 변수는 각각 제일 나중에 입력된 data와 다음에 입력될 data의 위치를 나타냅니다.

 

1. empty / full 함수

	bool check_empty() {
		if (top == floor) return true;
		else return false;
	}
	bool check_full() {
		if (top == s_size) {
			return true;
		}
		else return false;
	}

stack과 달라진 점은 empty인지 알아보는 방법이 top과 floor가 같은 지 확인하는 것이다.

 

2. push 함수

	void push(T a) {
		if (check_full()) {
			resize();
			my_queue[top++] = a;
		}
		else {
			my_queue[top++] = a;
		}
	}

queue가 가득찼는 지 확인하고 queue에 data를 입력해줍니다.

top을 증가시켜 다음 data의 위치를 지정해줍니다.

 

3. pop 함수

	void pop() {
		if (check_empty()) return;
		else {
			my_queue[floor++] = NULL;
		}
	}

stack과 반대로 floor에서 data를 뽑아옵니다.

 

4. front / back 함수

	T front() {
		if (check_empty())return -1;
		else return my_queue[top-1];
	}
	T back() {
		if (check_empty())return -1;
		else return my_queue[floor];
	}

top이 다음 data의 위치를 가르키므로 top에서 1을 뺀 값을 index로 사용합니다.

 

5. size 함수

	int size() {
		return top-floor;
	}

입력된 data의 개수를 나타내야하므로 다음 data의 위치에서 가장 먼저 입력된 data의 위치를 빼주면 됩니다.

 

6. 전체 코드

#include <iostream>
using namespace std;


template <class T>
class queue {
private:
	int s_size = 100;
	T* my_queue= (T*)malloc(sizeof(T)*s_size);
	int top = 0;
	int floor = 0;
public:
	void resize() {
		s_size += 100;
		realloc(my_queue, sizeof(T) * s_size);
	}
	bool check_empty() {
		if (top == floor) return true;
		else return false;
	}
	bool check_full() {
		if (top == s_size) {
			return true;
		}
		else return false;
	}
	void push(T a) {
		if (check_full()) {
			resize();
			my_queue[top++] = a;
		}
		else {
			my_queue[top++] = a;
		}
	}
	void pop() {
		if (check_empty()) return;
		else {
			my_queue[floor++] = NULL;
		}
	}
	T front() {
		if (check_empty())return -1;
		else return my_queue[top-1];
	}
	T back() {
		if (check_empty())return -1;
		else return my_queue[floor];
	}
	int size() {
		return top-floor;
	}
};