개요

큐(queue)란 자료구조 중 하나로
FIFO(First In, First Out)방식이다.

말 그대로 먼저 큐에 들어간 원소가
먼저 나오는 방식으로
LIFO(Last In, First Out)방식인
스택(stack) 자료구조와는 반대다.

(배열을 이용한)코드

#include<iostream>

using namespace std;

template <typename T>

class queue {
private:
	T* arr;								//큐 원소 넣는 배열
	int q_size;							//큐의 사이즈
	int frontCursor;					//큐의 front가리키는 커서
	int rearCursor;						//큐의 back가리키는 커서

public:
	queue() {							//초기화
		q_size = 0;
		arr = new T[10'000];
		frontCursor = 5'000;
		rearCursor = 5'000;
	}
	~queue() {
		delete[] arr;
	}

	void push(T elem){						//원소 넣기
		arr[rearCursor] = elem;
		rearCursor++;
        q_size++;

	}
	void pop(T elem){						//원소 빼기
		if (q_size!=0) {						//비어있지 않을 때
			arr[frontCursor] = 0;
			frontCursor++;
            q_size--;
		}
		else {
			cout << "큐가 비어있습니다." << '\n';
		}
	}
	T front(){								//큐의 제일 앞 값(먼저 빠짐)
		return arr[frontCursor];
	}
	T back(){								//큐의 제일 뒷 값
		return arr[rearCursor-1];
	}
	bool empty(){							//큐가 비어있는지 여부
		if (q_size==0)
			return true;
		else return false;
	}
	int size(){								//큐의 크기
		return q_size;
	}
};

맨 앞 위치를 나타내는 frontCursor와
맨 뒤 위취를 나타내는 rearCursor을 이용해 구현했다.

연결리스트를 이용한 구현

#include<iostream>

using namespace std;

template <typename T>

struct Node {
	T data;
	Node* prev;
	Node* next;
};

template <typename T>
class queue {
private:
	int q_size;							//큐의 사이즈
	Node<T>* head;							//큐의 앞부분 가리키는 노드포인터
	Node<T>* tail;							//큐의 뒷 노드 가리키는 노드포인터

public:
	//생성자
	queue() {						
		q_size = 0;
		Node<T>* tmpHead = new Node<T>;		
		Node<T>* tmpTail = new Node<T>;
		tmpHead->data = T();
		tmpTail->data = T();
		tmpHead->next = tmpTail;
		tmpHead->prev = tmpHead;
		tmpTail->next = tmpTail;
		tmpTail->prev = tmpHead;

		head = tmpHead;
		tail = tmpTail;

	}
	//소멸자
	~queue() {
		Node<T>* tmp = head;
		Node<T>* delNode = tmp;
		while (tmp != tail) {
			delNode = tmp;
			tmp = tmp->next;
			delete delNode;
		}
		//반복문빠져나왔다면 tmp는 tail노드이므로
		delete tmp;

	}
	//원소 넣기
	void push(T elem) {				
		//새로운 노드 생성
		Node<T>* newNode = new Node<T>;
		newNode->data = elem;
		//연결작업
		newNode->next = tail;
		newNode->prev = tail->prev;
		tail->prev->next = newNode;
		tail->prev = newNode;
		q_size++;

	}
	void pop() {							//원소 빼기
		if (!empty()) {						//비어있지 않을 때
			Node<T>* delNode = head->next;
			delNode->next->prev = head;
			head->next = delNode->next;
			delete delNode;
			q_size--;
		}
		else {
			cout << "큐가 비어있습니다." << '\n';
		}
	}
	T front() {								//큐의 제일 앞 값(먼저 빠짐)
		return head->next->data;
	}
	T back() {								//큐의 제일 뒷 값
		return tail->prev->data;
	}
	bool empty() {							//큐가 비어있는지 여부
		if (q_size == 0)
			return true;
		else return false;
	}
	int size() {								//큐의 크기
		return q_size;
	}
};

노드 구조체를 구현한 후, 해당 노드를 이용한 이중연결리스트 queue클래스를 짜서
큐의 멤버함수들을 구현하였다.